C++ 使用栈求解中缀、后缀表达式的值( 二 ) _生活百科

-入栈。

文章插图

继续扫描，直到遇到右括号。

文章插图

因右括号的优先级最低，或者说表示子表达式到此结束，此时从optStack栈中依次弹出运算符，从numStack中相应弹出 2 个操作数，计算后把结果压入numStack中，直到在optStack栈中遇到左括号。

弹出*对3和2进行计算。并把结果6压入numStack中。

文章插图
弹出-运算符，并对numStack栈中的12和6进行计算。

文章插图

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

文章插图

因-优先级小于^，先做6^6=46656乘方运算。

文章插图

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

文章插图

-入栈，最后一个数字 8入栈。

文章插图

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

文章插图
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;}

输出结果：
1866163.后缀表达式后缀表达式也称为逆波兰式，其求解过程比中缀表达式要简单，整个过程只需要一个操作数栈。所以往往会把中缀表达式转换成后缀表达式后再求解。
后缀表达式的求解流程：