C++?如何使用棧求解中綴、后綴表達式的值
更新時間：2022年10月13日 10:22:52 作者：一枚大果殼
這篇文章主要介紹了C++?使用棧求解中綴、后綴表達式的值,本文講解了中綴、后綴表達式的求值過程以及如何將一個中綴表達式轉換成后綴表達式，需要的朋友可以參考下
1. 前言
表達式求值對于有知識積累的你而言，可以通過認知，按運算符的優(yōu)先級進行先后運算。
但對計算機而言，表達式僅是一串普通的信息而已，需要通過編碼的方式告訴計算機運算法則，這個過程中棧起到了至關重要的作用。
表達式由 2 部分組成：
- 操作數(shù)。
- 運算符。
在一個復雜的表達式中，操作數(shù)和運算符可以有多個，運算符之間存在優(yōu)先級，且不同運算符所需要的操作數(shù)的數(shù)量也有差異。這時，表達式的計算過程就變得較復雜。為了簡化問題，本文只限于討論基于常量操作數(shù)和雙目運算符的表達式。
在計算機中，表達式的描述可以有以下 3 種：
- 后綴表達式：操作數(shù)，操作數(shù)，運算符。
- 中綴表達式：操作數(shù)，運算符，操作數(shù)。數(shù)學上最常見的描述方式。
- 前綴表達式：運算符，操作數(shù)，操作數(shù)。
本文將討論后綴表達式和中綴表達式的計算過程。
2. 中綴表達式
平常所見最多的表達式是中綴表達式，如下所示：
4*6^(3+3*3-2*3)-8
對中綴表達式求值時需要創(chuàng)建 2 個棧。
- 一個用來存儲運算符的棧
optStack。 - 一個用來存儲操作數(shù)的棧
numStack。
stack<int> numStack; stack<char> optStack;
2.1 求值流程
掃描整個表達式，對不同類型（操作數(shù)和運算符）的字符采用不同的處理方案。
- 遇到操作數(shù)時的處理方案
直接將其壓入numStack中，如上述表達式中的第一個字符是 4，壓入numStack棧中。
- 掃描到運算符時的處理方案
如果運算符比optStack棧頂運算符的優(yōu)先級高，則入棧。如果比optStack棧頂?shù)倪\算符的優(yōu)先級低，則彈出運算符，再從numStack棧中彈出 2 個操作數(shù)，對其進行運算，且把運算結果壓入到numStack棧中。
這里就有一個問題，如何判斷運算符的優(yōu)先級？
基于數(shù)學常識，在常規(guī)的加減乘除四則運算表達式中：
- 其運算符的優(yōu)先級為:
() > ^ > *、/、%> +、-`。 - 有括號時，先算括號內的，后算括號外的，對于多層括號，由內向外進行。
- 乘方連續(xù)出現(xiàn)時先算最右邊的。
但是，這里需要知道， 因為使用到了出棧、入棧操作，運算符在棧外和棧內的優(yōu)先級是不一樣的。
如左括號(運算符，在棧外優(yōu)先級是最高的，進棧后優(yōu)先級則變得最低。這個很好理解，括號的本質是界限符號（ 界限了一個子表達式的范圍，它并不具有運算能力），為了保證左括號后面的表達式中的運算符能正常入棧，就必須降低優(yōu)先級別。當左括號遇到右括號時，表示由這一對括號所標識的子表達式運算結束。
Tips： 棧內、棧外優(yōu)先級相同的運算符，棧內優(yōu)先。
- 一直反復上述過程，直到表達式掃描結束。
2.2 演示表達式4*6^(3+3*3-2*3)-8 的求值過程當
- 一直掃描到第一個減號（
-）時，兩個棧都是在進行入棧操作。
- 因
-(減法)運算符優(yōu)先級低于optStack棧頂?shù)?code>*運算符。這時從optStack棧中彈出*，再從numStack中彈出3和3兩個操作數(shù)，進行乘法運算3*3=9，并把結果壓入numStack棧中。
- 計算完成后，因
-（減法）和+（加法）的優(yōu)先級相同，棧內優(yōu)先。此時，把+從optStack棧中彈出，并從numStack中相繼彈出9和3，計算3+9=12，并把結果壓入numStack棧中。
- 因
-(減法)優(yōu)先級大于棧中(的優(yōu)先級，-入棧。
- 繼續(xù)掃描，直到遇到右括號。
- 因右括號的優(yōu)先級最低，或者說表示子表達式到此結束，此時從
optStack棧中依次彈出運算符，從numStack中相應彈出2個操作數(shù)，計算后把結果壓入numStack中，直到在optStack棧中遇到左括號。
彈出*對3和2進行計算。并把結果6壓入numStack中。
彈出-運算符，并對numStack棧中的12和6進行計算。
(出棧，表示由括號表示的子表達式計算結束。繼續(xù)掃描到第二個-
- 因
-優(yōu)先級小于^，先做6^6=46656乘方運算 。
-優(yōu)先級小于*，繼續(xù)做乘法運算，46656*4=186624。
-入棧，最后一個數(shù)字8入棧。
- 因整個表達式結束，彈出
-，做最后的減法運算186624-8=186616。整個表達式結束，numStack棧頂?shù)慕Y果為表達式的最后結果。
2.3 編碼實現(xiàn)
中綴表達式求值的完整代碼，僅針對只包括加、減、乘、除、括號常規(guī)運算符的表達式。
#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;
}
};
//關聯(lián)容器
map<char,Opt*> maps;
//初始化關聯(liá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;
//運算符棧
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 {
//數(shù)字字符
numStack.push( exps[i]-'0' );
i++;
}
}
cout<<numStack.top()<<endl;
return 0;
}輸出結果：
186616
3.后綴表達式
后綴表達式也稱為逆波蘭式，其求解過程比中綴表達式要簡單，整個過程只需要一個操作數(shù)棧。所以往往會把中綴表達式轉換成后綴表達式后再求解。
后綴表達式的求解流程：
- 創(chuàng)建一個棧。
- 把后綴表達式當成一個字符串，對字符串進行逐字符掃描。
- 遇到操作數(shù)入棧，遇到運算符則從棧中取出
2個操作數(shù)，運算后把結果壓入棧。 - 重復上述過程，直到掃描結束。則棧中的值為最終結果。
如下是求解后綴表達式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;
}
執(zhí)行后的輸出結果：
34
4. 中綴轉后綴表達式
雖然后綴表達式的計算過程要比中綴表達式簡單很多，前提條件是要先把中綴表達式轉換成后綴表達式。
轉換流程：
- 初始化一個運算符棧。
- 自左向右掃描中綴表達式，當掃描到操作數(shù)時直接連接到后綴表達式上。
- 當掃描到操作符時，和運算符棧棧頂?shù)牟僮鞣M行比較。如果比棧頂運算符高，則入棧。如果比棧頂運算符低，則把棧頂?shù)倪\算符出棧后連接到中綴表達式上。
- 若運算符是右括號，棧頂是左括號時，刪除棧頂運算符（清除括號。后綴表達式中是沒有括號的，操作數(shù)后面的運算符的優(yōu)先級由左向右降低）。
- 重復以上過程直到遇到結束符。
問題的關鍵在于運算符優(yōu)先級的比較，并且要考慮同一個運算符在棧內和棧外的級別。和前文計算中綴表達式時對運算符的優(yōu)先級認定是一樣的。
4.1 流程演示
如下把8+5*(7-1)-8/2 中綴表達式轉換成后綴表達式。
- 初始化運算符棧。
- 掃描中綴表達式，字符
8直接輸出，+是第一個操作數(shù)，因可能后續(xù)有更高的運算符，入棧。
- 字符
5直接輸出，*優(yōu)先級大于棧頂+優(yōu)先級，入棧。
(運算符在棧外優(yōu)先級最高，入棧。
- 字符
7直接輸出，因(運算符在棧內優(yōu)先級最低，-運算符入棧。
- 字符
1直接輸出，)棧外優(yōu)先級最低。運算符出棧，一直碰到(。
-運算符小于棧中的+、+運算符。*、+運算符出棧。-入棧。
/優(yōu)先級大于-，入棧。字符直接輸出。
- 字符掃描結束，把運算符棧中的運算符全部出棧。
4.2 編碼實現(xiàn)
中綴表達式轉后綴表達式的實現(xiàn)過程類似于中綴表達式的求值過程，只是不需要進行計算。或者說中綴表達式的求值過程包括了中綴表達式轉換成后綴表達式以及對后綴表達式求值過程。
#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 {
//數(shù)字字符
hzExp[j]=exps[i];
j++;
i++;
}
}
//hzExp[j]='\0';
cout<<hzExp<<endl;
return 0;
}執(zhí)行后輸入結果：
當然，知道了如何把中綴表達式轉成后綴表達式后，需要時，可以直接給出后綴表達式。
5. 總結
本文講解了中綴、后綴表達式的求值過程以及如何將一個中綴表達式轉換成后綴表達式。
到此這篇關于C++ 使用棧求解中綴、后綴表達式的值的文章就介紹到這了,更多相關C++中綴、后綴表達式的值內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++結構體用法,實例分析了默認構造函數(shù),復制構造函數(shù),運算符重載等使用技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-01-01
本篇文章主要介紹了八大排序算法，詳細的介紹了八個算法思想，實現(xiàn)代碼，穩(wěn)定性，時間復雜度等，具有一定的參考價值，有需要的可以了解一下。2016-11-11
C++任意線程通過hwnd實現(xiàn)將操作發(fā)送到UI線程執(zhí)行
做Windows界面開發(fā)時,經(jīng)常需要在多線程環(huán)境中將操作拋到主線程執(zhí)行,下面我們就來學習一下如何在不需要重新定義消息以及接收消息的情況下實現(xiàn)這一要求,感興趣的可以了解下2024-03-03
XML文件可以用來存儲項目中的數(shù)據(jù),它相當于一個簡單的數(shù)據(jù)庫,下面這篇文章主要給大家介紹了關于Qt讀寫XML文件(含源碼+注釋)的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-10-10
本文主要介紹了C#桌面應用開發(fā)實現(xiàn)番茄定時器,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-07-07
Qt?Creator配置opencv環(huán)境的全過程記錄
最近在PC端QT下配置opencv,想著以后應該會用到,索性記錄下,這篇文章主要給大家介紹了關于Qt?Creator配置opencv環(huán)境的相關資料,需要的朋友可以參考下2022-05-05
這篇文章主要介紹了C++編程中的const關鍵字常見用法總結,const關鍵字的使用是C++入門學習中的基礎知識,需要的朋友可以參考下2015-11-11
這篇文章主要為大家詳細介紹了OpenGL實現(xiàn)貝塞爾曲線或曲面，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
這篇文章主要介紹了C++簡單輸出鉆石菱形圖效果,涉及C++簡單的數(shù)組操作與圖形打印技巧,需要的朋友可以參考下2016-05-05
opencv 人臉識別通過級聯(lián)分類器對特征的分級篩選來確定是否是人臉，每個節(jié)點的正確識別率很高，但正確拒絕率很低，任一節(jié)點判斷沒有人臉特征則結束運算，宣布不是人臉2012-11-11