目标：
1、输入中缀表达式，输出后缀表达式
2、输入后缀表达式，输出计算结果
3、输入中缀表达式，转换成后缀表达式计算结果并输出
第三个目标是前两个的合并，它们之间微小的差异只是输出位置不同：
对于1，操作数在压栈前输出，操作符在弹栈时输出。
辅助函数：（1）构建优先级（2）四则运算
map<char,int>isp;//栈顶字符的优先级 map<char,int>icp;//扫描字符的优先级 void buildPriority(){ isp[‘+‘]=2;icp[‘+‘]=1; isp[‘-‘]=2;icp[‘-‘]=1; isp[‘*‘]=4;icp[‘*‘]=3; isp[‘/‘]=4;icp[‘/‘]=3; isp[‘(‘]=0;icp[‘(‘]=5; isp[‘)‘]=5;icp[‘)‘]=0; }
int calculate(int a,int b,char c){ switch(c){ case‘+‘: return a+b; break; case‘-‘: return a-b; break; case‘*‘: return a*b; break; case‘/‘: return a/b; break; default: break; } return 0; }
1、输入中缀表达式，输出后缀表达式
void convertToPost(const string &s){ stack<char>operators; int len=s.length(); for(int i=0;i<len;++i){ if(s[i]>=‘0‘&&s[i]<=‘9‘){ cout<<s[i]; }else{ if(operators.empty()){ operators.push(s[i]); }else{ char top=operators.top(); if(isp[top]<icp[s[i]]){ operators.push(s[i]); }else{ while(!operators.empty()&&isp[top]>icp[s[i]]){ cout<<top; operators.pop(); if(!operators.empty()) top=operators.top();//对一个空栈取top会导致error } if(!operators.empty()&&isp[top]==icp[s[i]]){ operators.pop(); } else{ operators.push(s[i]); } } } } } while(!operators.empty()){//一定要记得把栈中剩余的操作符全部弹完 char top; top=operators.top(); cout<<top; operators.pop(); } }
2、输入后缀表达式，输出计算结果
int calculatePost(const string &s){ int len=s.length(); stack<int> operands; for(int i=0;i<len;++i){ if(s[i]>=‘0‘&&s[i]<=‘9‘){ operands.push(s[i]-‘0‘); }else{ int a,b; b=operands.top(); operands.pop(); a=operands.top(); operands.pop(); operands.push(calculate(a,b,s[i])); } } return operands.top(); }
3、输入中缀表达式，通过转换为后缀表达式输出计算结果
int calculateInByPost(const string &s){ int len=s.length(); stack<char>operators; stack<int>operands; for(int i=0;i<len;++i){ if(s[i]>=‘0‘&&s[i]<=‘9‘){ operands.push(s[i]-‘0‘); }else{ if(operators.empty()){ operators.push(s[i]); }else{ char top=operators.top(); if(isp[top]<icp[s[i]]){ operators.push(s[i]); }else{ while(!operators.empty()&&isp[top]>icp[s[i]]){ int a,b; b=operands.top(); operands.pop(); a=operands.top(); operands.pop(); operands.push(calculate(a,b,top)); operators.pop(); if(!operators.empty())//取top之前先确定栈不空 top=operators.top(); } if(!operators.empty()&&isp[operators.top()]==icp[s[i]]) operators.pop(); else operators.push(s[i]); } } } } while(!operators.empty()){//记得把操作符栈弹干净 char top=operators.top(); int a,b; b=operands.top(); operands.pop(); a=operands.top(); operands.pop(); operands.push(calculate(a,b,top)); operators.pop(); } return operands.top(); }
测试：
#include<iostream> #include<string> #include<stack> #include<map> using namespace std; int main(){ buildPriority(); string inExpression,postExpression; cout<<"input the in-order expression:"<<endl; cin>>inExpression; cout<<"input the post-order expression:"<<endl; cin>>postExpression;
cout<<"\nthe in-order expression converted to post-order:"<<endl; convertToPost(inExpression);
cout<<"\nthe post-order expression equals to "; cout<<calculatePost(postExpression);
cout<<"\nthe in-order expression calculated as post-order equals to "; cout<<calculateInByPost(inExpression); } //5+(6-3)*7-4/2 //563-7*+42/-
原文：https://www.cnblogs.com/NoerForest/p/14609960.html