<题目链接>
题目大意:
读入一个只包含 +, -, *, / 的非负整数计算表达式,计算该表达式的值。
Input测试输入包含若干测试用例,每个测试用例占一行,每行不超过200个字符,整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束,相应的结果不要输出。
Output对每个测试用例输出1行,即该表达式的值,精确到小数点后2位。
Sample Input
1 + 2 4 + 2 * 5 - 7 / 11 0
Sample Output
3.00 13.36
解题分析:
表达式求值简单题,只涉及四则运算,我们只需要借助栈,将中缀表达式转化为后缀表达式进行计算即可。
#include <cstdio> #include <cstring> #include <stack> #include <algorithm> using namespace std; ]; int change(char c){ //将每个运算符都转化为数字,方便比较和区分 ; ; ; ; ; } int cmp(int a,int b){ //比较运算符的优先级 ||a==)a=; ; ||b==)b=; ; ; ; } void solve(){ stack<double>a; //后缀数字栈 stack<int>b; //运算符栈 int len=strlen(str); //将中缀表达式借助栈转化为后缀表达式 ;i<len;i++){ if(str[i]==' ')continue; //遇到空格,跳过 '){ //将连续的数字字符转化为数字 ; '){ cal=cal*+str[i]-'; i++; } a.push(cal); } if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'){ int temp=change(str[i]); if(b.empty())b.push(temp); //如果开始栈空,则无需比较 else{ int res=b.top(); while(cmp(res,temp)){ //运算符栈里的优先级大于当前的,就先运算栈顶优先级大的,最后再将当前操作符(temp)压入栈内 double a1=a.top();a.pop(); //弹出2个操作数 double b1=a.top();a.pop(); int c=b.top();b.pop(); //弹出运算符栈里的运算符 switch(c){ : a.push(a1+b1); break; : a.push(b1-a1); //这里为什么是b1-a1? break; : a.push(a1*b1); break; : a.push(b1/a1); break; } if(b.empty())break; //如果栈空,就终止 else res=b.top(); //否则继续比较运算符栈顶和当前运算符的优先级 } b.push(temp); //将这个运算符压入栈内 } } } while(!b.empty()){ //当栈b内仍然有运算符时,说明运算还未结束 double a1=a.top();a.pop(); double b1=a.top();a.pop(); int c=b.top();b.pop(); switch(c){ : a.push(a1+b1); break; : a.push(b1-a1); break; : a.push(a1*b1); break; : a.push(b1/a1); break; } } printf("%.2lf\n",a.top()); } int main(){ ")){ solve(); } ; }
2018-10-04