1. 前言

表達(dá)式求值對(duì)于有知識(shí)積累的你而言，可以通過(guò)認(rèn)知，按運(yùn)算符的優(yōu)先級(jí)進(jìn)行先后運(yùn)算。

但對(duì)計(jì)算機(jī)而言，表達(dá)式僅是一串普通的信息而已，需要通過(guò)編碼的方式告訴計(jì)算機(jī)運(yùn)算法則，這個(gè)過(guò)程中棧起到了至關(guān)重要的作用。

表達(dá)式由 2 部分組成：

• 操作數(shù)。
• 運(yùn)算符。

在一個(gè)復(fù)雜的表達(dá)式中，操作數(shù)和運(yùn)算符可以有多個(gè)，運(yùn)算符之間存在優(yōu)先級(jí)，且不同運(yùn)算符所需要的操作數(shù)的數(shù)量也有差異。這時(shí)，表達(dá)式的計(jì)算過(guò)程就變得較復(fù)雜。為了簡(jiǎn)化問(wèn)題，本文只限于討論基于常量操作數(shù)和雙目運(yùn)算符的表達(dá)式。

在計(jì)算機(jī)中，表達(dá)式的描述可以有以下 3 種：

• 后綴表達(dá)式：操作數(shù)，操作數(shù)，運(yùn)算符。
• 中綴表達(dá)式：操作數(shù)，運(yùn)算符，操作數(shù)。數(shù)學(xué)上最常見(jiàn)的描述方式。
• 前綴表達(dá)式：運(yùn)算符，操作數(shù)，操作數(shù)。

本文將討論后綴表達(dá)式和中綴表達(dá)式的計(jì)算過(guò)程。

2. 中綴表達(dá)式

平常所見(jiàn)最多的表達(dá)式是中綴表達(dá)式，如下所示：

4*6^(3+3*3-2*3)-8

對(duì)中綴表達(dá)式求值時(shí)需要?jiǎng)?chuàng)建 2 個(gè)棧。

• 一個(gè)用來(lái)存儲(chǔ)運(yùn)算符的棧 optStack。
• 一個(gè)用來(lái)存儲(chǔ)操作數(shù)的棧numStack。

stack<int> numStack;
stack<char> optStack;

2.1 求值流程

掃描整個(gè)表達(dá)式，對(duì)不同類型（操作數(shù)和運(yùn)算符）的字符采用不同的處理方案。

• 遇到操作數(shù)時(shí)的處理方案

直接將其壓入numStack中，如上述表達(dá)式中的第一個(gè)字符是 4，壓入numStack棧中。

• 掃描到運(yùn)算符時(shí)的處理方案

如果運(yùn)算符比optStack棧頂運(yùn)算符的優(yōu)先級(jí)高，則入棧。如果比optStack棧頂?shù)倪\(yùn)算符的優(yōu)先級(jí)低，則彈出運(yùn)算符，再?gòu)?code>numStack棧中彈出 2 個(gè)操作數(shù)，對(duì)其進(jìn)行運(yùn)算，且把運(yùn)算結(jié)果壓入到numStack棧中。

這里就有一個(gè)問(wèn)題，如何判斷運(yùn)算符的優(yōu)先級(jí)？

基于數(shù)學(xué)常識(shí)，在常規(guī)的加減乘除四則運(yùn)算表達(dá)式中：

• 其運(yùn)算符的優(yōu)先級(jí)為:() > ^ > *、/、% > +、-`。
• 有括號(hào)時(shí)，先算括號(hào)內(nèi)的，后算括號(hào)外的，對(duì)于多層括號(hào)，由內(nèi)向外進(jìn)行。
• 乘方連續(xù)出現(xiàn)時(shí)先算最右邊的。

但是，這里需要知道， 因?yàn)槭褂玫搅顺鰲！⑷霔２僮鳎\(yùn)算符在棧外和棧內(nèi)的優(yōu)先級(jí)是不一樣的。

如左括號(hào)(運(yùn)算符，在棧外優(yōu)先級(jí)是最高的，進(jìn)棧后優(yōu)先級(jí)則變得最低。這個(gè)很好理解，括號(hào)的本質(zhì)是界限符號(hào)（ 界限了一個(gè)子表達(dá)式的范圍，它并不具有運(yùn)算能力），為了保證左括號(hào)后面的表達(dá)式中的運(yùn)算符能正常入棧，就必須降低優(yōu)先級(jí)別。當(dāng)左括號(hào)遇到右括號(hào)時(shí)，表示由這一對(duì)括號(hào)所標(biāo)識(shí)的子表達(dá)式運(yùn)算結(jié)束。

?

Tips： 棧內(nèi)、棧外優(yōu)先級(jí)相同的運(yùn)算符，棧內(nèi)優(yōu)先。

?

• 一直反復(fù)上述過(guò)程，直到表達(dá)式掃描結(jié)束。

2.2 演示表達(dá)式4*6^(3+3*3-2*3)-8 的求值過(guò)程當(dāng)

• 一直掃描到第一個(gè)減號(hào)（-）時(shí)，兩個(gè)棧都是在進(jìn)行入棧操作。

• 因 -(減法)運(yùn)算符優(yōu)先級(jí)低于optStack棧頂?shù)?code>*運(yùn)算符。這時(shí)從optStack棧中彈出*，再?gòu)?code>numStack中彈出3和3 兩個(gè)操作數(shù)，進(jìn)行乘法運(yùn)算3*3=9，并把結(jié)果壓入numStack棧中。

• 計(jì)算完成后，因-（減法）和+（加法）的優(yōu)先級(jí)相同，棧內(nèi)優(yōu)先。此時(shí)，把+從optStack棧中彈出，并從numStack中相繼彈出9和3，計(jì)算3+9=12，并把結(jié)果壓入numStack棧中。

• 因-(減法)優(yōu)先級(jí)大于棧中(的優(yōu)先級(jí)，-入棧。

• 繼續(xù)掃描，直到遇到右括號(hào)。

• 因右括號(hào)的優(yōu)先級(jí)最低，或者說(shuō)表示子表達(dá)式到此結(jié)束，此時(shí)從optStack棧中依次彈出運(yùn)算符，從numStack中相應(yīng)彈出 2 個(gè)操作數(shù)，計(jì)算后把結(jié)果壓入numStack中，直到在optStack棧中遇到左括號(hào)。

彈出*對(duì)3和2進(jìn)行計(jì)算。并把結(jié)果6壓入numStack中。

彈出-運(yùn)算符，并對(duì)numStack棧中的12和6進(jìn)行計(jì)算。

• (出棧，表示由括號(hào)表示的子表達(dá)式計(jì)算結(jié)束。繼續(xù)掃描到第二個(gè)-

• 因-優(yōu)先級(jí)小于^，先做6^6=46656乘方運(yùn)算 。

• -優(yōu)先級(jí)小于*，繼續(xù)做乘法運(yùn)算，46656*4=186624。

• -入棧，最后一個(gè)數(shù)字 8入棧。

• 因整個(gè)表達(dá)式結(jié)束，彈出-，做最后的減法運(yùn)算186624-8=186616。整個(gè)表達(dá)式結(jié)束，numStack棧頂?shù)慕Y(jié)果為表達(dá)式的最后結(jié)果。

2.3 編碼實(shí)現(xiàn)

中綴表達(dá)式求值的完整代碼，僅針對(duì)只包括加、減、乘、除、括號(hào)常規(guī)運(yùn)算符的表達(dá)式。

#include <iostream>
#include <stack>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;
//運(yùn)算符對(duì)象
struct Opt {
	//運(yùn)算符名字
	char name;
	//棧內(nèi)級(jí)別
	int stackInJb;
	//棧外級(jí)別
	int stackOutJb;
    //構(gòu)造
	Opt(char name,int in,int out) {
		this->name=name;
		this->stackInJb=in;
		this->stackOutJb=out;
	}
	/*
	*棧外運(yùn)算符和棧內(nèi)運(yùn)算比較
	*/
	bool compare(Opt* opt) {
		return this->stackOutJb > opt->stackInJb;
	}
	//顯示
	void desc() {
		cout<<this->name<<"-"<<this->stackInJb<<"-"<<this->stackOutJb<<endl;
	}
};

//關(guān)聯(lián)容器
map<char,Opt*> maps;
//初始化關(guān)聯(lián)容器，本文限定表達(dá)式中只包括如下幾種運(yùn)算符
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();
    //操作數(shù)棧
	stack<int> numStack;
    //運(yùn)算符棧
	stack<char> optStack;
    //以字符描述的表達(dá)式，最外層的括號(hào)用來(lái)標(biāo)志表達(dá)式的開(kāi)始和結(jié)束
	char exps[20]="(4*6^(3+3*3-2*3)-8)";
    //初始?jí)喝?(
	optStack.push(exps[0]);
	//棧內(nèi)運(yùn)算符
	Opt* opt;
	//棧外運(yùn)算符
	Opt* opt_;
	for(int i=1; exps[i]!='\0' ; ) {
		if( !(exps[i]>='0' && exps[i]<='9')  ) {
			//棧內(nèi)最初是 ) 運(yùn)算符
			opt=maps[optStack.top()];
			//棧外運(yùn)算符
			opt_=maps[exps[i]];
			//如果左右括號(hào)相遇
			if(opt_->name==')' && opt->name=='(') {
				//子表達(dá)式結(jié)束
				optStack.pop();
				i++;
				continue;
			}
			//比較
			bool com=opt_->compare(opt);
			if (com) {
				//入棧
				optStack.push(opt_->name);
				i++;
			} else  {
				//運(yùn)算
				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 {
			//數(shù)字字符
			numStack.push( exps[i]-'0' );
			i++;
		}
	}
	cout<<numStack.top()<<endl;
	return 0;
}

輸出結(jié)果：

186616

3.后綴表達(dá)式

后綴表達(dá)式也稱為逆波蘭式，其求解過(guò)程比中綴表達(dá)式要簡(jiǎn)單，整個(gè)過(guò)程只需要一個(gè)操作數(shù)棧。所以往往會(huì)把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式后再求解。

后綴表達(dá)式的求解流程：

• 創(chuàng)建一個(gè)棧。
• 把后綴表達(dá)式當(dāng)成一個(gè)字符串，對(duì)字符串進(jìn)行逐字符掃描。
• 遇到操作數(shù)入棧，遇到運(yùn)算符則從棧中取出?2?個(gè)操作數(shù)，運(yùn)算后把結(jié)果壓入棧。
• 重復(fù)上述過(guò)程，直到掃描結(jié)束。則棧中的值為最終結(jié)果。

如下是求解后綴表達(dá)式8571-*+82/-的代碼。

?

Tips：此后綴表達(dá)式對(duì)應(yīng)的中綴表達(dá)式是： 8+5*(7-1)-8/2

#include <iostream>
#include <stack>
using namespace std;
int main() {
	char exp[20]="8571-*+82/-";
	stack<int> expStack;
	int num1;
	int num2;
	char opt;
	int res;
	for(int i=0; exp[i]!='\0'; i++) {
		if (exp[i]>='0' && exp[i]<='9') {
			//入棧
			expStack.push(exp[i]-'0');
		} else {
			//出棧
			num1=expStack.top();
			expStack.pop();
			//出棧
			num2=expStack.top();
			expStack.pop();
			//運(yùn)算符
			opt=exp[i];
			switch(opt) {
				case '+':
					res=num2+num1;
					break;
				case '-':
					res=num2-num1;
					break;
				case '*':
					res=num2*num1;
					break;
				case '/':
					res=num2/num1;
					break;
			}
			expStack.push(res);
		}
	}
	cout<<expStack.top()<<endl;
	return 0;
}

?

執(zhí)行后的輸出結(jié)果：

34

4. 中綴轉(zhuǎn)后綴表達(dá)式

雖然后綴表達(dá)式的計(jì)算過(guò)程要比中綴表達(dá)式簡(jiǎn)單很多，前提條件是要先把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。

轉(zhuǎn)換流程：

• 初始化一個(gè)運(yùn)算符棧。
• 自左向右掃描中綴表達(dá)式，當(dāng)掃描到操作數(shù)時(shí)直接連接到后綴表達(dá)式上。
• 當(dāng)掃描到操作符時(shí)，和運(yùn)算符棧棧頂?shù)牟僮鞣M(jìn)行比較。如果比棧頂運(yùn)算符高，則入棧。如果比棧頂運(yùn)算符低，則把棧頂?shù)倪\(yùn)算符出棧后連接到中綴表達(dá)式上。
• 若運(yùn)算符是右括號(hào)，棧頂是左括號(hào)時(shí)，刪除棧頂運(yùn)算符（清除括號(hào)。后綴表達(dá)式中是沒(méi)有括號(hào)的，操作數(shù)后面的運(yùn)算符的優(yōu)先級(jí)由左向右降低）。
• 重復(fù)以上過(guò)程直到遇到結(jié)束符。

問(wèn)題的關(guān)鍵在于運(yùn)算符優(yōu)先級(jí)的比較，并且要考慮同一個(gè)運(yùn)算符在棧內(nèi)和棧外的級(jí)別。和前文計(jì)算中綴表達(dá)式時(shí)對(duì)運(yùn)算符的優(yōu)先級(jí)認(rèn)定是一樣的。

4.1 流程演示

如下把8+5*(7-1)-8/2 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。

• 初始化運(yùn)算符棧。

• 掃描中綴表達(dá)式，字符8直接輸出，+是第一個(gè)操作數(shù)，因可能后續(xù)有更高的運(yùn)算符，入棧。

• 字符5直接輸出，*優(yōu)先級(jí)大于棧頂+優(yōu)先級(jí)，入棧。

• (運(yùn)算符在棧外優(yōu)先級(jí)最高，入棧。

• 字符7直接輸出，因(運(yùn)算符在棧內(nèi)優(yōu)先級(jí)最低，-運(yùn)算符入棧。

• 字符1直接輸出，)棧外優(yōu)先級(jí)最低。運(yùn)算符出棧，一直碰到(。

• -運(yùn)算符小于棧中的+、+運(yùn)算符。*、+運(yùn)算符出棧。-入棧。

• /優(yōu)先級(jí)大于-，入棧。字符直接輸出。

• 字符掃描結(jié)束，把運(yùn)算符棧中的運(yùn)算符全部出棧。

4.2 編碼實(shí)現(xiàn)

中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的實(shí)現(xiàn)過(guò)程類似于中綴表達(dá)式的求值過(guò)程，只是不需要進(jìn)行計(jì)算。或者說(shuō)中綴表達(dá)式的求值過(guò)程包括了中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式以及對(duì)后綴表達(dá)式求值過(guò)程。

#include <iostream>
#include <stack>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;
struct Opt {
	//運(yùn)算符名字
	char name;
	//棧內(nèi)級(jí)別
	int stackInJb;
	//棧外級(jí)別
	int stackOutJb;
	Opt(char name,int in,int out) {
		this->name=name;
		this->stackInJb=in;
		this->stackOutJb=out;
	}
	/*
	*棧外運(yùn)算符和棧內(nèi)運(yùn)算比較
	*/
	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();
	//后綴表達(dá)式 
	char hzExp[20]={'\0'};
	int j=0;
	stack<char> optStack;
	//中綴表達(dá)式 
	char exps[20]="(8+5*(7-1)-8/2)";
	optStack.push(exps[0]);
	//棧內(nèi)運(yùn)算符
	Opt* opt;
	//棧外運(yùn)算符
	Opt* opt_;
	for(int i=1; exps[i]!='\0' ; ) {

		if( !(exps[i]>='0' && exps[i]<='9')  ) {
			//棧內(nèi)最初是 ) 運(yùn)算符
			opt=maps[optStack.top()];
			//棧外運(yùn)算符
			opt_=maps[exps[i]];

			if(opt_->name==')' && opt->name=='(') {
				//子表達(dá)式結(jié)束
				optStack.pop();
				i++;
				continue;
			}
			//比較
			bool com=opt_->compare(opt);

			if (com) {
				//入棧
				optStack.push(opt_->name);
				i++;
			} else  {
				//運(yùn)算
				char n=opt->name;
				optStack.pop();
				hzExp[j]=n;
				j++;			
			}

		} else {
			//數(shù)字字符
			hzExp[j]=exps[i];
			j++;
			i++;
		}
	}
	//hzExp[j]='\0';
	cout<<hzExp<<endl;
	return 0;
}

執(zhí)行后輸入結(jié)果：

當(dāng)然，知道了如何把中綴表達(dá)式轉(zhuǎn)成后綴表達(dá)式后，需要時(shí)，可以直接給出后綴表達(dá)式。

5. 總結(jié)

本文講解了中綴、后綴表達(dá)式的求值過(guò)程以及如何將一個(gè)中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。