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

+、+运算符。*、+运算符出栈。-入栈。

文章插图

/优先级大于-，入栈。字符直接输出。

文章插图

字符扫描结束，把运算符栈中的运算符全部出栈。

文章插图
4.2 编码实现中缀表达式转后缀表达式的实现过程类似于中缀表达式的求值过程，只是不需要进行计算。或者说中缀表达式的求值过程包括了中缀表达式转换成后缀表达式以及对后缀表达式求值过程。

#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('/',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();	//后缀表达式	char hzExp[20]={'\0'};	int j=0;	stack<char> optStack;	//中缀表达式	char exps[20]="(8+5*(7-1)-8/2)";	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();hzExp[j]=n;j++;}} else {//数字字符hzExp[j]=exps[i];j++;i++;}	}	//hzExp[j]='\0';	cout<<hzExp<<endl;	return 0;}

执行后输入结果：