算法笔记 栈的应用 简单计算器 中缀和后缀表达式

思路

将输入的中缀表达式转后缀表达式 遇到数字，则算出数值，直接放入队列（注意数据非仅有一位，需要计算出整个数的值）遇到运算符先判断优先级是否小于栈中top的运算符 如果是，将栈中的运算符pop到队列中，直到栈中没有运算符优先级更大为止如果不是，则直接将运算符放入栈中 最后如果栈中剩余运算符，则直接放入队列中 计算后缀表达式，遍历队列 如果为数值，则放入栈中如果为运算符 从栈中pop出两个数（注意是先第二个后第一个，后进先出嘛）随后运算最后把计算完成的数放入栈中

代码

#include <iostream> #include <stdio.h> #include <stack> #include <queue> #include <map> using namespace std; struct node{ int flag;//区别操作数和操作符 double num; char op;//操作符 }; stack<node> opers; queue<node> behind; string middle; map<char,int> op; void Change(){//把中缀表达式转后缀表达式 for(int i=0;i<middle.length();){ node temp; temp.flag=1; if(middle[i]>='0'&&middle[i]<='9'){ temp.num=middle[i]-'0'; i++; while(i<middle.length()&&middle[i]>='0'&&middle[i]<='9'){ temp.num=temp.num*10+middle[i]-'0'; i++; } behind.push(temp); } else{ temp.flag=0; while(!opers.empty()&&op[middle[i]]<=op[opers.top().op]){//如果操作符优先级低于操作符栈 behind.push(opers.top()); opers.pop(); } temp.op=middle[i]; opers.push(temp); i++; } } //如果最后栈中还有操作符，直接压入 while(!opers.empty()){ behind.push(opers.top()); opers.pop(); } } double Cal(){//计算后缀表达式 double temp1,temp2; node cur,temp; while(!behind.empty()){ cur=behind.front();//记录队首元素 behind.pop(); if(cur.flag==1)//是数 opers.push(cur); else{ temp2=opers.top().num; opers.pop(); temp1=opers.top().num; opers.pop(); temp.flag=1; if(cur.op=='+') temp.num=temp1+temp2; else if(cur.op=='-') temp.num=temp1-temp2; else if(cur.op=='*') temp.num=temp1*temp2; else temp.num=temp1/temp2; opers.push(temp); } } return opers.top().num; } int main(){ op['+']=op['-']=1; op['*']=op['/']=2; while(getline(cin,middle)&&middle!="0"){ //注意从右到左遍历 for(string::iterator it=middle.end(); it!=middle.begin();it--){ if(*it==' ')//忽略空格键 middle.erase(it); } while(!opers.empty()) opers.pop();//初始化栈 Change(); printf("%.2lf\n",Cal()); } return 0; }