经验总结

  1. 首页 > 生活 > >

C++ 使用栈求解中缀、后缀表达式的值( 二 )

生活百科


  • 因 -(减法)运算符优先级低于optStack栈顶的*运算符 。这时从optStack栈中弹出*，再从numStack中弹出3和3 两个操作数，进行乘法运算3*3=9，并把结果压入numStack栈中 。

C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • 计算完成后，因-（减法）和+（加法）的优先级相同，栈内优先 。此时，把+从optStack栈中弹出，并从numStack中相继弹出9和3，计算3+9=12，并把结果压入numStack栈中 。

C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • 因-(减法)优先级大于栈中(的优先级，-入栈 。

C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • 继续扫描，直到遇到右括号 。

C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • 因右括号的优先级最低，或者说表示子表达式到此结束，此时从optStack栈中依次弹出运算符，从numStack中相应弹出 2 个操作数，计算后把结果压入numStack中，直到在optStack栈中遇到左括号 。
弹出*对3和2进行计算 。并把结果6压入numStack中 。
C++ 使用栈求解中缀、后缀表达式的值

文章插图
弹出-运算符，并对numStack栈中的12和6进行计算 。
C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • (出栈，表示由括号表示的子表达式计算结束 。继续扫描到第二个-

C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • 因-优先级小于^，先做6^6=46656乘方运算。

C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • -优先级小于*，继续做乘法运算，46656*4=186624 。

C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • -入栈，最后一个数字 8入栈 。

C++ 使用栈求解中缀、后缀表达式的值

文章插图
  • 因整个表达式结束，弹出-，做最后的减法运算186624-8=186616 。整个表达式结束，numStack栈顶的结果为表达式的最后结果 。

C++ 使用栈求解中缀、后缀表达式的值

文章插图
2.3 编码实现中缀表达式求值的完整代码，仅针对只包括加、减、乘、除、括号常规运算符的表达式 。
#include <iostream>#include <stack>#include <map>#include <cmath>#include <cstring>using namespace std;//运算符对象struct Opt { //运算符名字 char name; //栈内级别 int stackInJb; //栈外级别 int stackOutJb;//构造 Opt(char name,int in,int out) {this->name=name;this->stackInJb=in;this->stackOutJb=out; } /* *栈外运算符和栈内运算比较 */ bool compare(Opt* opt) {return this->stackOutJb > opt->stackInJb; } //显示 void desc() {cout<<this->name<<"-"<<this->stackInJb<<"-"<<this->stackOutJb<<endl; }};//关联容器map<char,Opt*> maps;//初始化关联容器，本文限定表达式中只包括如下几种运算符void mapOpt() { maps['^']=new Opt('^',3,4); maps['*']=new Opt('*',2,2); maps['+']=new Opt('+',1,1); maps['-']=new Opt('-',1,1); maps['(']=new Opt('(',0,4); maps[')']=new Opt(')',-1,-1);}int main(int argc, char** argv) { mapOpt();//操作数栈 stack<int> numStack;//运算符栈 stack<char> optStack;//以字符描述的表达式，最外层的括号用来标志表达式的开始和结束 char exps[20]="(4*6^(3+3*3-2*3)-8)";//初始压入 ( optStack.push(exps[0]); //栈内运算符 Opt* opt; //栈外运算符 Opt* opt_; for(int i=1; exps[i]!='\0' ; ) {if( !(exps[i]>='0' && exps[i]<='9')) {//栈内最初是 ) 运算符opt=maps[optStack.top()];//栈外运算符opt_=maps[exps[i]];//如果左右括号相遇if(opt_->name==')' && opt->name=='(') {//子表达式结束optStack.pop();i++;continue;}//比较bool com=opt_->compare(opt);if (com) {//入栈optStack.push(opt_->name);i++;} else{//运算char n=opt->name;optStack.pop();int res;int optNum1=numStack.top();numStack.pop();int optNum2=numStack.top();numStack.pop();if(n=='*') {res=optNum2*optNum1;} else if(n=='+') {res=optNum2+optNum1;} else if(n=='-') {res=optNum2-optNum1;} else if(n=='^') {res= pow(optNum2,optNum1);}numStack.push(res);}} else {//数字字符numStack.push( exps[i]-'0' );i++;} } cout<<numStack.top()<<endl; return 0;}

经验总结扩展阅读


上一篇：CentOS 7.9 安装 kafka_2.13

下一篇：为什么开空调要关门关窗