|
后缀表达式是一种把运算符后置的算术表达式，例如普通的表达式2 + 3的后缀表示法为2 3 +。后缀表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的后缀表示法为?2 3 + 4 *。本题求解后缀表达式的值，其中运算符包括+ - * /四个。
计算后缀表达式，要从前向后遍历字符串。当遇见运算数时，压入栈中。当读到运算符时，将栈中的连续2个运算数弹栈；用当前运算符计算后（注意后缀表达式的先出栈的运算数，放在运算符后面；后出栈的运算数，放在运算符前面），再将结果压栈。最后的栈顶就是后缀表达式的运算结果。
输入
输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。
输出
输出为一行，表达式的值。
可使用以下语句保留固定长度的小数点后尾数
C++：cout<<setiosflags(ios::fixed)<<setprecision(6)<<ans<<endl;
C：printf("%.6lf\n", ans);
输入样例
11.0 12.0 + 24.0 35.0 + *
输出样例
1357.000000
样例解释
从前向后读入数据：
11.0: 11.0入栈? ? ? ? 12.0: 12.0入栈? ? ? ? +: 将栈顶的 12.0 11.0 弹出，将运算结果23.0压入栈内(11.0+12.0=23.0)
24.0: 24.0入栈? ? ? ? 35.0: 35.0入栈? ? ? ? +: 将栈顶的 35.0 24.0 弹出，将运算结果59.0压入栈内(24.0+35.0=59.0)
*: 将栈顶的 59.0 23.0 弹出，将运算结果1357.0压入栈内(23.0*59.0=1357.0)
解析：
波兰式符合递归结构，所以直接递归求解即可，时间复杂度O(字符的的个数)。
然后逆波兰表达式正好是波兰表达式逆过来得到式子，所以只需要先输入式子，然后从后往前递归即可，这里有两点需要注意，减的时候还要取反，除的时候要取倒数，因为递归求得是后面减前面，而正常的是前面减后面。
这里说明一下递归的过程，实际上波兰表达式是一颗二叉树，计算符号的儿子节点是数字，然后这两个数字通过父节点的计算符号计算出结果返回给上一层，最终返回给根节点得到波兰表达式的计算结果。
放代码：
#include<iostream>
#include<string>
#include<stack>
#include<cctype>
using namespace std;
string temp;
double x, a, b;
stack<double> s;
inline double cal(double a, char op, double b) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
default : return 0;
}
}
inline double trans(const string& s) {
double k = 0.0, f = 1.0, frac = 1.0;
bool flag = false;
for(int i = 0; i < s.length(); ++i) {
char c = s[i];
if(c == '+') f = 1.0;
else if(c == '-') f = -1.0;
else if(c == '.') flag = true;
else if(!flag) k = k * 10.0 + (c - 48);
else frac /= 10.0, k += (c - 48) * frac;
}
return k * f;
}
int main() {
while(cin >> temp) {
if(isdigit(temp[0]) || isdigit(temp[1])) {
x = trans(temp);
s.push(x);
}
else {
b = s.top(), s.pop();
a = s.top(), s.pop();
s.push(cal(a, temp[0], b));
}
}
printf("%.6f", s.top());
}
|