先看题目：
读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。
测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。
对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。
在遇到这种模拟计算器的题目中，最常用的手段就是将中缀表达式转化为后缀表达式，再进行计算。假设读入一串字符，建立一个栈临时存操作符，再建立一个队列存后缀表达式那么转化方式如下：
1.如果是数字入队列
2.如果是操作符，a.与栈顶比较优先级，优先级高入栈;b.反之，栈顶元素出栈入队，继续比较。
优先级+、-小于*、/,本题没有括号，如果有遇见“（”入栈，遇到“）”一直出栈直到遇到“（”
3.串完后，将栈中剩余操作符入后缀表达式
由此我们可以写出中缀变后缀的函数：
#include<iostream> #include<stack> #include<queue> #include<string> #include<algorithm> #include<map> using namespace std; struct node{ //结点放操作数或操作符 double num; char op; bool flag; }; string str; queue<node>q; //后缀表达式的队列 stack<node>s; //临时存放操作符的栈 map<char,int>op; //用其次建来表名优先级 void change(){ //中缀转后缀 node temp; for(int i=0;i<str.length();){ if(str[i]>='0'&&str[i]<='9'){ temp.num=str[i++]-'0'; //操作数的第一个数 temp.flag=true; while(i<str.length()&&str[i]>='0'&&str[i]<='9'){ //更新操作数 temp.num=temp.num*10+(str[i]-'0'); i++; } q.push(temp); } else{ //如果是操作符 temp.flag=false; temp.op=str[i]; while(!s.empty()&&op[str[i]]<=op[s.top().op]){ //出栈至符合temp入栈 ； q.push(s.top());s.pop(); } s.push(temp); i++; } } while(!s.empty()){ q.push(s.top());s.pop(); } }
转化为后缀表达式之后，只需要计算即可
计算方法，顺序读取后缀表达式，如果是操作数入栈，如果是操作符，栈分别弹出第二、第一操作数，计算后入栈；最后栈里只剩一个元素为结果。
最后附完整代码：
#include<iostream> #include<stack> #include<queue> #include<string> #include<algorithm> #include<map> using namespace std; struct node{ //结点放操作数或操作符 double num; char op; bool flag; }; string str; queue<node>q; //后缀表达式的队列 stack<node>s; //临时存放操作符的栈 map<char,int>op; void change(){ //中缀转后缀 node temp; for(int i=0;i<str.length();){ if(str[i]>='0'&&str[i]<='9'){ temp.num=str[i++]-'0'; //操作数的第一个数 temp.flag=true; while(i<str.length()&&str[i]>='0'&&str[i]<='9'){ //更新操作数 temp.num=temp.num*10+(str[i]-'0'); i++; } q.push(temp); } else{ //如果是操作符 temp.flag=false; temp.op=str[i]; while(!s.empty()&&op[str[i]]<=op[s.top().op]){ //出栈至符合temp入栈 q.push(s.top());s.pop(); } s.push(temp); i++; } } while(!s.empty()){ q.push(s.top());s.pop(); } } double caculate(){ node temp; while(!q.empty()){ //遍历后缀表达式 temp=q.front();q.pop(); if(temp.flag)s.push(temp); else{ double n2=s.top().num;s.pop(); //先弹第二操作数 double n1=s.top().num;s.pop(); //后弹第一操作数 if(temp.op=='*')temp.num=n1*n2; else if(temp.op=='/')temp.num=n1/n2; else if(temp.op=='-')temp.num=n1-n2; else temp.num=n1+n2; temp.flag=true; s.push(temp); } } return s.top().num; } int main(){ op['+']=op['-']=1; op['*']=op['/']=2; while(getline(cin,str),str !="0"){ for(string::iterator it=str.end();it!=str.begin();it--){ if(*it==' ')str.erase(it); } while(!s.empty())s.pop(); change(); printf("%.2f\n",caculate()); } return 0; }
最后提醒，使用cin.getline在while循环中可能会吃掉回车符，这里面解决方案我不太清楚。
