C++?如何使用棧求解中綴、后綴表達(dá)式的值
1. 前言
表達(dá)式求值對于有知識積累的你而言，可以通過認(rèn)知，按運算符的優(yōu)先級進(jìn)行先后運算。
但對計算機(jī)而言，表達(dá)式僅是一串普通的信息而已，需要通過編碼的方式告訴計算機(jī)運算法則，這個過程中棧起到了至關(guān)重要的作用。
表達(dá)式由 2 部分組成：
- 操作數(shù)。
- 運算符。
在一個復(fù)雜的表達(dá)式中，操作數(shù)和運算符可以有多個，運算符之間存在優(yōu)先級，且不同運算符所需要的操作數(shù)的數(shù)量也有差異。這時，表達(dá)式的計算過程就變得較復(fù)雜。為了簡化問題，本文只限于討論基于常量操作數(shù)和雙目運算符的表達(dá)式。
在計算機(jī)中，表達(dá)式的描述可以有以下 3 種：
- 后綴表達(dá)式：操作數(shù)，操作數(shù)，運算符。
- 中綴表達(dá)式：操作數(shù)，運算符，操作數(shù)。數(shù)學(xué)上最常見的描述方式。
- 前綴表達(dá)式：運算符，操作數(shù)，操作數(shù)。
本文將討論后綴表達(dá)式和中綴表達(dá)式的計算過程。
2. 中綴表達(dá)式
平常所見最多的表達(dá)式是中綴表達(dá)式，如下所示：
4*6^(3+3*3-2*3)-8
對中綴表達(dá)式求值時需要創(chuàng)建 2 個棧。
- 一個用來存儲運算符的棧
optStack。 - 一個用來存儲操作數(shù)的棧
numStack。
stack<int> numStack; stack<char> optStack;
2.1 求值流程
掃描整個表達(dá)式，對不同類型（操作數(shù)和運算符）的字符采用不同的處理方案。
- 遇到操作數(shù)時的處理方案
直接將其壓入numStack中，如上述表達(dá)式中的第一個字符是 4，壓入numStack棧中。
- 掃描到運算符時的處理方案
如果運算符比optStack棧頂運算符的優(yōu)先級高，則入棧。如果比optStack棧頂?shù)倪\算符的優(yōu)先級低，則彈出運算符，再從numStack棧中彈出 2 個操作數(shù)，對其進(jìn)行運算，且把運算結(jié)果壓入到numStack棧中。
這里就有一個問題，如何判斷運算符的優(yōu)先級？
基于數(shù)學(xué)常識，在常規(guī)的加減乘除四則運算表達(dá)式中：
- 其運算符的優(yōu)先級為:
() > ^ > *、/、%> +、-`。 - 有括號時，先算括號內(nèi)的，后算括號外的，對于多層括號，由內(nèi)向外進(jìn)行。
- 乘方連續(xù)出現(xiàn)時先算最右邊的。
但是，這里需要知道， 因為使用到了出棧、入棧操作，運算符在棧外和棧內(nèi)的優(yōu)先級是不一樣的。
如左括號(運算符，在棧外優(yōu)先級是最高的，進(jìn)棧后優(yōu)先級則變得最低。這個很好理解，括號的本質(zhì)是界限符號（ 界限了一個子表達(dá)式的范圍，它并不具有運算能力），為了保證左括號后面的表達(dá)式中的運算符能正常入棧，就必須降低優(yōu)先級別。當(dāng)左括號遇到右括號時，表示由這一對括號所標(biāo)識的子表達(dá)式運算結(jié)束。
Tips： 棧內(nèi)、棧外優(yōu)先級相同的運算符，棧內(nèi)優(yōu)先。
- 一直反復(fù)上述過程，直到表達(dá)式掃描結(jié)束。
2.2 演示表達(dá)式4*6^(3+3*3-2*3)-8 的求值過程當(dāng)
- 一直掃描到第一個減號（
-）時，兩個棧都是在進(jìn)行入棧操作。
- 因
-(減法)運算符優(yōu)先級低于optStack棧頂?shù)?code>*運算符。這時從optStack棧中彈出*，再從numStack中彈出3和3兩個操作數(shù)，進(jìn)行乘法運算3*3=9，并把結(jié)果壓入numStack棧中。
- 計算完成后，因
-（減法）和+（加法）的優(yōu)先級相同，棧內(nèi)優(yōu)先。此時，把+從optStack棧中彈出，并從numStack中相繼彈出9和3，計算3+9=12，并把結(jié)果壓入numStack棧中。
- 因
-(減法)優(yōu)先級大于棧中(的優(yōu)先級，-入棧。
- 繼續(xù)掃描，直到遇到右括號。
- 因右括號的優(yōu)先級最低，或者說表示子表達(dá)式到此結(jié)束，此時從
optStack棧中依次彈出運算符，從numStack中相應(yīng)彈出2個操作數(shù)，計算后把結(jié)果壓入numStack中，直到在optStack棧中遇到左括號。
彈出*對3和2進(jìn)行計算。并把結(jié)果6壓入numStack中。
彈出-運算符，并對numStack棧中的12和6進(jìn)行計算。
(出棧，表示由括號表示的子表達(dá)式計算結(jié)束。繼續(xù)掃描到第二個-
- 因
-優(yōu)先級小于^，先做6^6=46656乘方運算 。
-優(yōu)先級小于*，繼續(xù)做乘法運算，46656*4=186624。
-入棧，最后一個數(shù)字8入棧。
- 因整個表達(dá)式結(jié)束，彈出
-，做最后的減法運算186624-8=186616。整個表達(dá)式結(jié)束，numStack棧頂?shù)慕Y(jié)果為表達(dá)式的最后結(jié)果。
2.3 編碼實現(xiàn)
中綴表達(dá)式求值的完整代碼，僅針對只包括加、減、乘、除、括號常規(guī)運算符的表達(dá)式。
#include <iostream>
#include <stack>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;
//運算符對象
struct Opt {
//運算符名字
char name;
//棧內(nèi)級別
int stackInJb;
//棧外級別
int stackOutJb;
//構(gòu)造
Opt(char name,int in,int out) {
this->name=name;
this->stackInJb=in;
this->stackOutJb=out;
}
/*
*棧外運算符和棧內(nèi)運算比較
*/
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á)式中只包括如下幾種運算符
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;
//以字符描述的表達(dá)式，最外層的括號用來標(biāo)志表達(dá)式的開始和結(jié)束
char exps[20]="(4*6^(3+3*3-2*3)-8)";
//初始壓入 (
optStack.push(exps[0]);
//棧內(nèi)運算符
Opt* opt;
//棧外運算符
Opt* opt_;
for(int i=1; exps[i]!='\0' ; ) {
if( !(exps[i]>='0' && exps[i]<='9') ) {
//棧內(nèi)最初是 ) 運算符
opt=maps[optStack.top()];
//棧外運算符
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 {
//運算
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á)式也稱為逆波蘭式，其求解過程比中綴表達(dá)式要簡單，整個過程只需要一個操作數(shù)棧。所以往往會把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式后再求解。
后綴表達(dá)式的求解流程：
- 創(chuàng)建一個棧。
- 把后綴表達(dá)式當(dāng)成一個字符串，對字符串進(jìn)行逐字符掃描。
- 遇到操作數(shù)入棧，遇到運算符則從棧中取出
2個操作數(shù)，運算后把結(jié)果壓入棧。 - 重復(fù)上述過程，直到掃描結(jié)束。則棧中的值為最終結(jié)果。
如下是求解后綴表達(dá)式8571-*+82/-的代碼。
Tips：此后綴表達(dá)式對應(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();
//運算符
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á)式的計算過程要比中綴表達(dá)式簡單很多，前提條件是要先把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。
轉(zhuǎn)換流程：
- 初始化一個運算符棧。
- 自左向右掃描中綴表達(dá)式，當(dāng)掃描到操作數(shù)時直接連接到后綴表達(dá)式上。
- 當(dāng)掃描到操作符時，和運算符棧棧頂?shù)牟僮鞣M(jìn)行比較。如果比棧頂運算符高，則入棧。如果比棧頂運算符低，則把棧頂?shù)倪\算符出棧后連接到中綴表達(dá)式上。
- 若運算符是右括號，棧頂是左括號時，刪除棧頂運算符（清除括號。后綴表達(dá)式中是沒有括號的，操作數(shù)后面的運算符的優(yōu)先級由左向右降低）。
- 重復(fù)以上過程直到遇到結(jié)束符。
問題的關(guān)鍵在于運算符優(yōu)先級的比較，并且要考慮同一個運算符在棧內(nèi)和棧外的級別。和前文計算中綴表達(dá)式時對運算符的優(yōu)先級認(rèn)定是一樣的。
4.1 流程演示
如下把8+5*(7-1)-8/2 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。
- 初始化運算符棧。
- 掃描中綴表達(dá)式，字符
8直接輸出，+是第一個操作數(shù)，因可能后續(xù)有更高的運算符，入棧。
- 字符
5直接輸出，*優(yōu)先級大于棧頂+優(yōu)先級，入棧。
(運算符在棧外優(yōu)先級最高，入棧。
- 字符
7直接輸出，因(運算符在棧內(nèi)優(yōu)先級最低，-運算符入棧。
- 字符
1直接輸出，)棧外優(yōu)先級最低。運算符出棧，一直碰到(。
-運算符小于棧中的+、+運算符。*、+運算符出棧。-入棧。
/優(yōu)先級大于-，入棧。字符直接輸出。
- 字符掃描結(jié)束，把運算符棧中的運算符全部出棧。
4.2 編碼實現(xiàn)
中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的實現(xiàn)過程類似于中綴表達(dá)式的求值過程，只是不需要進(jìn)行計算?；蛘哒f中綴表達(dá)式的求值過程包括了中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式以及對后綴表達(dá)式求值過程。
#include <iostream>
#include <stack>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;
struct Opt {
//運算符名字
char name;
//棧內(nèi)級別
int stackInJb;
//棧外級別
int stackOutJb;
Opt(char name,int in,int out) {
this->name=name;
this->stackInJb=in;
this->stackOutJb=out;
}
/*
*棧外運算符和棧內(nèi)運算比較
*/
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)運算符
Opt* opt;
//棧外運算符
Opt* opt_;
for(int i=1; exps[i]!='\0' ; ) {
if( !(exps[i]>='0' && exps[i]<='9') ) {
//棧內(nèi)最初是 ) 運算符
opt=maps[optStack.top()];
//棧外運算符
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 {
//運算
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á)式后，需要時，可以直接給出后綴表達(dá)式。
5. 總結(jié)
本文講解了中綴、后綴表達(dá)式的求值過程以及如何將一個中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。
到此這篇關(guān)于C++ 使用棧求解中綴、后綴表達(dá)式的值的文章就介紹到這了,更多相關(guān)C++中綴、后綴表達(dá)式的值內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
給定一個排序數(shù)組,你需要在原地刪除重復(fù)出現(xiàn)的元素,使得每個元素只出現(xiàn)一次,返回移除后數(shù)組的新長度,不要使用額外的數(shù)組空間,你必須在 原地 修改輸入數(shù)組 并在使用O(1)額外空間的條件下完成,故本文介紹了C++原地刪除有序數(shù)組重復(fù)項的N種方法,需要的朋友可以參考下2025-03-03
這篇文章主要介紹了C++ 中placement new 操作符使用方法的相關(guān)資料,需要的朋友可以參考下2017-05-05
這篇文章主要為大家詳細(xì)介紹了如何利用C語言實現(xiàn)手寫多級時間輪定時器，文中的示例代碼講解詳細(xì)，具有一定的借鑒價值，需要的可以參考一下2022-09-09
本篇文章是對VC中預(yù)編譯的頭文件放那里的問題進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
解析如何在C語言中調(diào)用shell命令的實現(xiàn)方法
本篇文章是對如何在C語言中調(diào)用shell命令的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C++中的數(shù)據(jù)內(nèi)存分布，主要從動態(tài)內(nèi)存管理方式，內(nèi)存泄漏等方面介紹的，文中也有相關(guān)的示例代碼,需要的朋友可以參考下2023-05-05
C語言中網(wǎng)絡(luò)地址與二進(jìn)制數(shù)之間轉(zhuǎn)換的函數(shù)小結(jié)
這篇文章主要介紹了C語言中網(wǎng)絡(luò)地址與二進(jìn)制數(shù)之間轉(zhuǎn)換的函數(shù)小結(jié),是C語言入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
這篇文章主要介紹了C++編程中用put輸出單個字符和cin輸入流的用法,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
這篇文章主要介紹了C++中構(gòu)造函數(shù)重載的相關(guān)資料，十分的詳細(xì)，需要的朋友可以參考下2015-06-06
這篇文章主要為大家詳細(xì)介紹了C++STL容器之string類，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03