C++ 使用棧求解中綴、後綴表達式的值

1. 前言

表達式求值對於有知識積累的你而言，可以通過認知，按運算符的優先順序進行先後運算。

但對電腦而言，表達式僅是一串普通的資訊而已，需要通過編碼的方式告訴電腦運演算法則，這個過程中棧起到了至關重要的作用。

表達式由 2 部分組成：

  • 操作數。
  • 運算符。

在一個複雜的表達式中，操作數和運算符可以有多個，運算符之間存在優先順序，且不同運算符所需要的操作數的數量也有差異。這時，表達式的計算過程就變得較複雜。為了簡化問題，本文只限於討論基於常量操作數和雙目運算符的表達式。

在電腦中，表達式的描述可以有以下 3 種：

  • 後綴表達式：操作數，操作數，運算符。
  • 中綴表達式：操作數，運算符，操作數。數學上最常見的描述方式。
  • 前綴表達式：運算符，操作數，操作數。

本文將討論後綴表達式和中綴表達式的計算過程。

2. 中綴表達式

平常所見最多的表達式是中綴表達式，如下所示：

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

對中綴表達式求值時需要創建 2 個棧。

13.png

  • 一個用來存儲運算符的棧 optStack。
  • 一個用來存儲操作數的棧numStack。
stack<int> numStack;
stack<char> optStack;

2.1 求值流程

掃描整個表達式，對不同類型（操作數和運算符）的字元採用不同的處理方案。

  • 遇到操作數時的處理方案

直接將其壓入numStack中，如上述表達式中的第一個字元是 4，壓入numStack棧中。

14.png

  • 掃描到運算符時的處理方案

如果運算符比optStack棧頂運算符的優先順序高，則入棧。如果比optStack棧頂的運算符的優先順序低，則彈出運算符，再從numStack棧中彈出 2 個操作數，對其進行運算，且把運算結果壓入到numStack棧中。

這裡就有一個問題，如何判斷運算符的優先順序？

基於數學常識，在常規的加減乘除四則運算表達式中：

  • 其運算符的優先順序為:() > ^ > *、/、% > +、-`。
  • 有括弧時，先算括弧內的，後算括弧外的，對於多層括弧，由內向外進行。
  • 乘方連續出現時先算最右邊的。

但是，這裡需要知道， 因為使用到了出棧、入棧操作，運算符在棧外和棧內的優先順序是不一樣的。

如左括弧(運算符，在棧外優先順序是最高的，進棧後優先順序則變得最低。這個很好理解，括弧的本質是界限符號（ 界限了一個子表達式的範圍，它並不具有運算能力），為了保證左括弧後面的表達式中的運算符能正常入棧，就必須降低優先順序別。當左括弧遇到右括弧時，表示由這一對括弧所標識的子表達式運算結束。

Tips： 棧內、棧外優先順序相同的運算符，棧內優先。

15.png

  • 一直反覆上述過程，直到表達式掃描結束。

2.2 演示表達式4*6^(3+3*3-2*3)-8 的求值過程

  • 當一直掃描到第一個減號（-）時，兩個棧都是在進行入棧操作。

16.png

  • 因 -(減法)運算符優先順序低於optStack棧頂的*運算符。這時從optStack棧中彈出*，再從numStack中彈出3和3 兩個操作數，進行乘法運算3*3=9，並把結果壓入numStack棧中。

17.png

  • 計算完成後，因-（減法）和+（加法）的優先順序相同，棧內優先。此時，把+從optStack棧中彈出，並從numStack中相繼彈出9和3，計算3+9=12，並把結果壓入numStack棧中。

18.png

  • 因-(減法)優先順序大於棧中(的優先順序，-入棧。

19.png

  • 繼續掃描，直到遇到右括弧。

20.png

  • 因右括弧的優先順序最低，或者說表示子表達式到此結束，此時從optStack棧中依次彈出運算符，從numStack中相應彈出 2 個操作數，計算後把結果壓入numStack中，直到在optStack棧中遇到左括弧。

彈出*對3和2進行計算。並把結果6壓入numStack中。

21.png

彈出-運算符，並對numStack棧中的12和6進行計算。

22.png

  • (出棧，表示由括弧表示的子表達式計算結束。繼續掃描到第二個-

23.png

  • 因-優先順序小於^，先做6^6=46656乘方運算 。

24.png

  • -優先順序小於*，繼續做乘法運算，46656*4=186624。

25.png

  • -入棧，最後一個數字 8入棧。

26.png

  • 因整個表達式結束，彈出-，做最後的減法運算186624-8=186616。整個表達式結束，numStack棧頂的結果為表達式的最後結果。

27.png

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;
}

輸出結果：

186616

3.後綴表達式

後綴表達式也稱為逆波蘭式，其求解過程比中綴表達式要簡單，整個過程只需要一個操作數棧。所以往往會把中綴表達式轉換成後綴表達式後再求解。

後綴表達式的求解流程：

  • 創建一個棧。
  • 把後綴表達式當成一個字元串，對字元串進行逐字元掃描。
  • 遇到操作數入棧，遇到運算符則從棧中取出 2 個操作數，運算後把結果壓入棧。
  • 重複上述過程，直到掃描結束。則棧中的值為最終結果。

如下是求解後綴表達式8571-*+82/-的程式碼。

Tips：此後綴表達式對應的中綴表達式是： 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();
			//運算符
			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;
}

執行後的輸出結果：

34

4. 中綴轉後綴表達式

雖然後綴表達式的計算過程要比中綴表達式簡單很多，前提條件是要先把中綴表達式轉換成後綴表達式。

轉換流程：

  • 初始化一個運算符棧。
  • 自左向右掃描中綴表達式，當掃描到操作數時直接連接到後綴表達式上。
  • 當掃描到操作符時，和運算符棧棧頂的操作符進行比較。如果比棧頂運算符高，則入棧。如果比棧頂運算符低，則把棧頂的運算符出棧後連接到中綴表達式上。
  • 若運算符是右括弧，棧頂是左括弧時，刪除棧頂運算符（清除括弧。後綴表達式中是沒有括弧的，操作數後面的運算符的優先順序由左向右降低）。
  • 重複以上過程直到遇到結束符。

問題的關鍵在於運算符優先順序的比較，並且要考慮同一個運算符在棧內和棧外的級別。和前文計算中綴表達式時對運算符的優先順序認定是一樣的。

15.png

4.1 流程演示

如下把8+5*(7-1)-8/2 中綴表達式轉換成後綴表達式。

  • 初始化運算符棧。

38.png

  • 掃描中綴表達式，字元8直接輸出，+是第一個操作數，因可能後續有更高的運算符，入棧。

29.png

  • 字元5直接輸出，*優先順序大於棧頂+優先順序，入棧。

30.png

  • (運算符在棧外優先順序最高，入棧。

31.png

  • 字元7直接輸出，因(運算符在棧內優先順序最低，-運算符入棧。

32.png

  • 字元1直接輸出，)棧外優先順序最低。運算符出棧，一直碰到(。

33.png

  • -運算符小於棧中的+、+運算符。*、+運算符出棧。-入棧。

34.png

  • /優先順序大於-，入棧。字元直接輸出。

35.png

  • 字元掃描結束，把運算符棧中的運算符全部出棧。

36.png

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;
}

執行後輸入結果：

37.png

當然，知道了如何把中綴表達式轉成後綴表達式後，需要時，可以直接給出後綴表達式。

4. 總結

本文講解了中綴、後綴表達式的求值過程以及如何將一個中綴表達式轉換成後綴表達式。

本文同時收錄在「編程驛站”公眾號。

Tags:

VirMach 便宜 VPS

QNews

QNews