如何利用棧實現表示式求值
前言
假如要你實現一個可以識別表示式的簡易計算器，你會怎麼實現？例如使用者輸入：
3 + 5 * （2 - 4）
可以直接得出計算結果：-7。對於人類來說，我們很容易計算出來，因為我們從左往右看，看到後面括號時，知道括號內的計算優先順序最高，因此可以先計算括號內的，然後反過來計算乘法，最後計算加法，得到最終結果。
字尾表示式
而對於計算機來說，實際也可以採用類似的順序，先記錄儲存3為a，然後儲存5為b，計算2-4結果存入c，再然後計算b*c儲存d，最終計算a+d得到最終結果。而這種計算過程的操作順序可描述如下（把運算子號放在運算元後面）：
3 5 2 4 - * +
這種記法叫做字尾或逆波蘭記法（而我們平常見到的叫中綴記法），它的特點是
不需要用括號就能表示出整個表示式哪部分運算先進行，也就是說不需要考慮優先順序，這非常符合計算機的處理方式。
這種記法很容易使用我們前面介紹的棧來求值，但是前提是需要將中綴表示式先轉換為字尾表示式。對於這種轉換，我們也可以使用前面介紹的棧-C語言實現或者將要介紹的樹來完成，因篇幅有限，本文不準備介紹。
接下來將會介紹如何利用中綴表示式進行求值。
利用棧實現中綴表示式求值
前面也說到，所謂中綴表示式，就是我們能看到的正常表示式，中綴表示式求值，也就是直接對輸入的表示式進行求值。為簡單起見，我們這裡假設
只涉及加減乘除和小括號，並且運算元都是正整數，不涉及更加複雜的資料或運算。
計算思路：
使用兩個棧，stack0用於儲存運算元，stack1用於儲存運算子
從左往右掃描，遇到運算元入棧stack0
遇到運算子時，如果優先順序低於或等於棧頂運算子優先順序，則從stack０彈出兩個元素進行計算，並壓入stack0，繼續與棧頂運算子的比較優先順序
如果遇到運算子高於棧頂運算子優先順序，則直接入棧stack1
遇到左括號，直接入棧stack1，遇到右括號，則直接出棧並計算，直到遇到左括號
上面的思路可能看起來不是很明確，我們舉一個簡單的例子，假如要對下面的表示式求值：
6 * （2 + 3 ）* 8 + 5
我們從左往右開始掃描。首先遇到運算元‘6’，和運算子‘*’，分別入棧
stack0：
棧頂
6
stack1：
棧頂
*
繼續往後掃描，遇到‘（’直接入棧，‘2’入棧，棧頂是左括號，’+‘入棧，‘3’入棧
stack0：
棧頂
623
stack1：
棧頂
*（+
繼續往後掃描，遇到右括號，它與棧頂運算子‘+’相比，優先順序要高，因此，將‘+’出棧，彈出兩個運算元‘3’，‘2’，計算結果得到‘5’，併入棧：
stack0：
棧頂
65
stack1：
棧頂
*（
繼續出棧，直到遇到左括號
stack0：
棧頂
65
stack1：
棧頂
*
繼續往後掃描，遇到運算子‘
’，優先順序與棧頂‘
’優先順序相同，因此彈出運算元並計算得到30入棧，最後‘*’入棧
stack0：
棧頂
30
stack1：
棧頂
*
繼續掃描，‘8’入棧，運算子‘+’優先順序小於‘*’，彈出運算元計算得到結果‘240’，並將其入棧，最後‘+’也入棧
stack0：
棧頂
240
stack1：
棧頂
+
最後‘5’入棧，發現運算子棧不為空，彈出運算子‘+’和兩個運算元，並進行計算，得到‘245’，入棧，得到最終結果。
stack0
棧頂
245
stack1：
程式碼實現
#include
#include
#define STACK_SIZE 64 /*棧大小*/
#define TOP_OF_STACK -1 /*棧頂位置*/
typedef int ElementType； /*棧元素型別*/
#define SUCCESS 0
#define FAILURE -1
/*定義棧結構*/
typedef struct StackInfo
{
int topOfStack； /*記錄棧頂位置*/
ElementType stack［STACK_SIZE］； /*棧陣列，也可以使用動態陣列實現*/
}StackInfo_st；
/*函式宣告*/
int stack_push（StackInfo_st *s，ElementType value）；
int stack_pop（StackInfo_st *s，ElementType *value）；
int stack_top（StackInfo_st *s，ElementType *value）；
int stack_is_full（StackInfo_st *s）；
int stack_is_empty（StackInfo_st *s）；
/*入棧，0表示成，非0表示出錯*/
int stack_push（StackInfo_st *s，ElementType value）
{
if（stack_is_full（s））
return FAILURE；
/*先增加topOfStack，再賦值*/
s->topOfStack++；
s->stack［s->topOfStack］ = value；
return SUCCESS；
}
/*出棧*/
int stack_pop（StackInfo_st *s，ElementType *value）
{
/*首先判斷棧是否為空*/
if（stack_is_empty（s））
return FAILURE；
*value = s->stack［s->topOfStack］；
s->topOfStack——；
return SUCCESS；
}
/*訪問棧頂元素*/
int stack_top（StackInfo_st *s，ElementType *value）
{
/*首先判斷棧是否為空*/
if（stack_is_empty（s））
{
printf（“stack is empty”）；
return FAILURE；
}
*value = s->stack［s->topOfStack］；
return SUCCESS；
}
/*判斷棧是否已滿，滿返回1，未滿返回0*/
int stack_is_full（StackInfo_st *s）
{
return s->topOfStack == STACK_SIZE - 1；
}
/*判斷棧是否為空，空返回1，非空返回0*/
int stack_is_empty（StackInfo_st *s）
{
return s->topOfStack == - 1；
}
/*用於記錄符號的優先順序，這裡浪費了一些記憶體，可以最佳化*/
static char priority［128］ = {0}；
void priorityInit（）
{
/*初始化優先順序，值越小，優先順序越高*/
priority［‘+’］ = 4；
priority［‘-’］ = 4；
priority［‘*’］ = 3；
priority［‘/’］ = 3；
priority［‘（’］ = 1；
priority［‘）’］ = 1；
}
/*比較運算子的優先順序，op1優先順序大於op2時，返回大於0的值*/
int priorityCompare（char op1，char op2）
{
return priority［op2］ - priority［op1］；
}
/*出棧運算子和運算元進行計算*/
int calcOp（StackInfo_st *nums，StackInfo_st *ops，int nowOp）
{
int a ，b，op；
stack_pop（ops，&op）；
printf（“op %c is <= %c\n”，nowOp，op）；
printf（“get op from stack %c\n”，op）；
if（SUCCESS ！= stack_pop（nums，&b））
{
printf（“pop failed\n”）；
return -1；
}
if（SUCCESS ！= stack_pop（nums，&a））
{
printf（“pop failed\n”）；
return 0；
}
printf（“get b from stack %d\n”，b）；
printf（“get a from stack %d\n”，a）；
switch（op）
{
case ‘+’：
{
printf（“push %d into stack\n”，a+b）；
stack_push（nums，a+b）；
break；
}
case ‘-’：
{
stack_push（nums，a-b）；
break；
}
case ‘*’：
{
printf（“push %d into stack\n”，a*b）；
stack_push（nums，a*b）；
break；
}
case ‘/’：
{
printf（“push %d into stack\n”，a/b）；
stack_push（nums，a/b）；
break；
}
}
return 1；
}
int calc（const char* exp，int *result）
{
if（NULL == exp || NULL == result）
return FAILURE；
/*建立棧，用於儲存數*/
StackInfo_st nums；
nums。topOfStack = TOP_OF_STACK；
/*用於儲存運算子*/
StackInfo_st ops；
ops。topOfStack = TOP_OF_STACK；
int index = 0；
/*用於標記，判斷上一個是否為數字*/
int flag = 0；
int temp = 0；
int op ；
while（0 ！= *exp）
{
/*如果是數字*/
if（isdigit（*exp））
{
printf（“char is %c\n”，*exp）；
/*如果上一個還是數字，則取出棧頂資料*/
if（1 == flag）
{
stack_pop（&nums，&temp）；
printf（“pop from stack num %d\n”，temp）；
}
else
temp = 0；
flag = 1；
temp = 10 * temp + *exp-‘0’；
printf（“push %d to stack\n”，temp）；
stack_push（&nums，temp）；
}
/*如果是運算子*/
else if（‘/’ == *exp || ‘*’ == *exp || ‘+’ == *exp || ‘-’ == *exp）
{
flag = 0；
printf（“OP is %c\n”，*exp）；
while（（ops。topOfStack > TOP_OF_STACK ）&&（SUCCESS == stack_top（&ops，&op））&&‘（’ ！= op && ‘）’！=op&&（priorityCompare（*exp，op） < 0））
{
calcOp（&nums， &ops，*exp）；
}
printf（“push %c to stack ops\n”，*exp）；
stack_push（&ops，*exp）；
}
/*左括號直接入棧*/
else if（‘（’ == *exp ）
{
printf（“push （ to stack ops\n”）；
flag = 0；
stack_push（&ops，*exp）；
}
/*右括號，計算*/
else if（‘）’ ==*exp ）
{
printf（“deal with ） in ops\n”）；
flag = 0；
/*右括號時，不斷計算，直到遇見左括號*/
while（SUCCESS == stack_top（&ops，&op） && ‘（’ ！= op）
{
calcOp（&nums， &ops，*exp）；
}
stack_pop（&ops，&op）；
}
else
{
flag=0；
}
printf（“flag is %d\n\n”，flag）；
exp++；
}
/*計算剩餘兩個棧的內容*/
while（（！stack_is_empty（&ops）） && （！stack_is_empty（&nums）））
{
if（！calcOp（&nums， &ops，0））
printf（“exp is error\n”）；
}
stack_pop（&nums，&temp）；
/*如果棧中還有內容，說明表示式錯誤*/
if（（！stack_is_empty（&ops）） || （！stack_is_empty（&nums）））
printf（“\n\nexp is ok\n\n”）；
if（SUCCESS == stack_pop（&nums，&temp））
printf（“result is %d\n”，temp）；
*result = temp；
return 0；
}
int main（int argc ，char *argv［］）
{
int result；
priorityInit（）；
char exp［］ = “6 * （2 + 3 * 3）* 8 + 5”；
calc（exp，&result）；
printf（“result is %d\n”，result）；
return 0；
}
總結
本文介紹了利用棧對中綴表示式進行求值，而程式碼實現還有很多不足之處，例如對錶達式的正確性校驗不足，只能處理正整數等等，歡迎在此基礎上完善補充。儘管如此，整個過程對使用棧進行中綴表示式的求值做了一個較為完整的介紹，因此具有一定的參考性。
微信公眾號【程式設計珠璣】：專注但不限於分享計算機程式設計基礎，Linux，C語言，C++，資料結構與演算法，工具，資源等程式設計相關［原創］技術文章，號內包含大量經典電子書和影片學習資源。歡迎一起交流學習，一起修煉計算機“內功”，知其然，更知其所以然。
上一篇:去見那片粉霧海
