在C++數(shù)據(jù)結(jié)構(gòu)中，棧的應(yīng)用很廣泛，棧的***的用途是解決回溯問題，這也包含了消解遞歸；而當(dāng)你用棧解決回溯問題成了習(xí)慣的時(shí)候，你就很少想到用遞歸了，比如迷宮求解。另外，人的習(xí)慣也是先入為主的，比如樹的遍歷，從學(xué)的那天開始，就是遞歸算法，雖然書上也教了用棧實(shí)現(xiàn)的方法，但應(yīng)用的時(shí)候，你首先想到的還是遞歸;當(dāng)然了，如果語言本身不支持遞歸(如BASIC)，那棧就是唯一的選擇了——好像現(xiàn)在的高級語言都是支持遞歸的。

　　如下是表達(dá)式類的定義和實(shí)現(xiàn)，表達(dá)式可以是中綴表示也可以是后綴表示，用頭節(jié)點(diǎn)數(shù)據(jù)域里的type區(qū)分，這里有一點(diǎn)說明的是，由于單鏈表的賦值函數(shù)，我原來寫的時(shí)候沒有復(fù)制頭節(jié)點(diǎn)的內(nèi)容，所以，要是在兩個(gè)表達(dá)式之間賦值，頭節(jié)點(diǎn)里存的信息就丟了。你可以改寫單鏈表的賦值函數(shù)來解決這個(gè)隱患，或者你根本不不在兩個(gè)表達(dá)式之間賦值也行。

#ifndef Expression_H  
#define Expression_H  
#include "List.h"  
#include "Stack.h"  
#define INFIX 0  
#define POSTFIX 1  
#define OPND 4  
#define OPTR 8  
 
template <class Type> class ExpNode  
{  
　public:  
　　int type;  
　　union { Type opnd; char optr;};  
　　ExpNode() : type(INFIX), optr('=') {}  
　　ExpNode(Type opnd) : type(OPND), opnd(opnd) {}  
　　ExpNode(char optr) : type(OPTR), optr(optr) {}  
};  
 
template <class Type> class Expression : List >  
{  
　public:  
　　void Input()  
　　{  
　　　MakeEmpty(); Get()->type =INFIX;  
　　　cout << endl << "輸入表達(dá)式，以＝結(jié)束輸入" << endl;  
　　　Type opnd; char optr = ' ';  
　　　while (optr != '=')  
　　　{  
　　　　cin >> opnd;   
　　　　if (opnd != 0)  
　　　　{  
　　　　　ExpNode newopnd(opnd);  
　　　　　LastInsert(newopnd);  
　　　　}  
　　　　cin >> optr;  
　　　　ExpNode newoptr(optr);  
　　　　LastInsert(newoptr);  
　　　}  
　　}  
　　void Print()  
　　{  
　　　First();  
　　　cout << endl;  
　　　for (ExpNode *p = Next(); p != NULL; p = Next() )  
　　　{  
　　　　switch (p->type)  
　　　　{  
　　　　　case OPND:  
　　　　　　cout << p->opnd; break;  
　　　　　case OPTR:  
　　　　　　cout << p->optr; break;  
　　　　　default: break;  
　　　　}  
　　　　cout << ' ';  
　　　}  
　　　cout << endl;  
　　}  
　　Expression & Postfix() //將中綴表達(dá)式轉(zhuǎn)變?yōu)楹缶Y表達(dá)式  
　　{  
　　　First();  
　　　if (Get()->type == POSTFIX) return *this;  
　　　Stack<char> s; s.Push('=');  
　　　Expression temp;  
　　　ExpNode *p = Next();  
　　　while (p != NULL)  
　　　{  
　　　　switch (p->type)  
　　　　{  
　　　　　case OPND:  
　　　　　　　temp.LastInsert(*p); p = Next(); break;  
　　　　　case OPTR:  
　　　　　　　while (isp(s.GetTop()) > icp(p->optr) )  
　　　　　　　{  
　　　　　　　　ExpNode newoptr(s.Pop());  
　　　　　　　　temp.LastInsert(newoptr);  
　　　　　　　}  
　　　　　　　if (isp(s.GetTop()) == icp(p->optr) )  
　　　　　　　{  
　　　　　　　　s.Pop(); p =Next(); break;  
　　　　　　　}  
　　　　　　　s.Push(p->optr); p = Next(); break;  
　　　　　default: break;  
　　　　}  
　　　}  
　　　*this = temp;  
　　　pGetFirst()->data.type = POSTFIX;  
　　　return *this;  
　　}  
 
　　Type Calculate()  
　　{  
　　　Expression temp = *this;  
　　　if (pGetFirst()->data.type != POSTFIX) temp.Postfix();  
　　　Stack s; Type left, right;  
　　　for (ExpNode *p = temp.Next(); p != NULL; p = temp.Next())  
　　　{  
　　　　switch (p->type)  
　　　　{  
　　　　　case OPND:  
　　　　　　s.Push(p->opnd); break;  
　　　　　case OPTR:  
　　　　　　right = s.Pop(); left = s.Pop();  
　　　　　　switch (p->optr)  
　　　　　　{  
　　　　　case '+': s.Push(left + right); break;  
　　　　　case '-': s.Push(left - right); break;  
　　　　　case '*': s.Push(left * right); break;  
　　　　　case '/': if (right != 0) s.Push(left/right); else return 0; break;  
　　　　　　// case '%': if (right != 0) s.Push(left%right); else return 0; break;  
　　　　　　// case '^': s.Push(Power(left, right)); break;  
　　　　　default: break;  
　　　　}  
　　　　default: break;  
　　　}  
　　}  
　　return s.Pop();  
}  
 
private:  
　int isp(char optr)  
　{  
　　switch (optr)  
　　{  
　　　case '=': return 0;  
　　　case '(': return 1;  
　　　case '^': return 7;  
　　　case '*': return 5;  
　　　case '/': return 5;  
　　　case '%': return 5;  
　　　case '+': return 3;  
　　　case '-': return 3;  
　　　case ')': return 8;  
　　　default: return 0;  
　　}  
　}  
 
　int icp(char optr)  
　{  
　　switch (optr)  
　　{  
　　　case '=': return 0;  
　　　case '(': return 8;  
　　　case '^': return 6;  
　　　case '*': return 4;  
　　　case '/': return 4;  
　　　case '%': return 4;  
　　　case '+': return 2;  
　　　case '-': return 2;  
　　　case ')': return 1;  
　　　default: return 0;  
　　}  
　}  
};  
 
#endif 

　　幾點(diǎn)說明

　　1、表達(dá)式用單鏈表儲存，你可以看到這個(gè)鏈表中既有操作數(shù)又有操作符，如果你看過我的另一篇文章如何在C++鏈表中鏈入不同類型對象，這里的方法也是對那篇文章的補(bǔ)充。

　　2、輸入表達(dá)式時(shí)，會將原來的內(nèi)容清空，并且必須按照中綴表示輸入。如果你細(xì)看一下中綴表達(dá)式，你就會發(fā)現(xiàn)，除了括號，表達(dá)式的結(jié)構(gòu)是“操作數(shù)”、“操作符”、“操作數(shù)”、……“操作符(=)”，為了統(tǒng)一這個(gè)規(guī)律，同時(shí)也為了使輸入函數(shù)簡單一點(diǎn)，規(guī)定括號必須這樣輸入“0(”、“)0”;這樣一來，“0”就不能作為操作數(shù)出現(xiàn)在表達(dá)式中了。因?yàn)槲覜]有在輸入函數(shù)中增加容錯(cuò)的語句，所以一旦輸錯(cuò)了，那程序就“死”了。

　　3、表達(dá)式求值的過程是，先變成后綴表示，然后用后綴表示求值。因?yàn)樵瓡v解的是這兩個(gè)算法，并且用這兩個(gè)算法就能完成中綴表達(dá)式的求值，所以我就沒寫中綴表達(dá)式的直接求值算法。

　　4、Calculate()注釋掉的兩行，“%”是因?yàn)橹粚φ捅磉_(dá)式合法，“^”的Power()函數(shù)沒有完成。

　　5、isp()，icp()的返回值，我來多說兩句?！?’(表達(dá)式開始和結(jié)束標(biāo)志)的棧內(nèi)棧外優(yōu)先級都是最低?！?’棧外最高，棧內(nèi)次最低。‘)’棧外次最低，不進(jìn)棧?！甞’棧內(nèi)次最高，棧外比棧內(nèi)低?！痢?’棧內(nèi)比‘^’棧外低，棧外比棧內(nèi)低。‘+-’棧內(nèi)比‘×’棧外低，棧外比棧內(nèi)低。這樣，綜合起來，就有9個(gè)優(yōu)先級。

【編輯推薦】

1. 淺析C++棧使用方法
2. 數(shù)據(jù)庫使用C++數(shù)據(jù)結(jié)構(gòu)
3. 程序員必看 c++筆試題匯總
4. c++編程常用工具
5. C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之棧和隊(duì)列