棧的應用很廣泛，原書只講解了表達式求值，那我也就只寫這些。其實，棧的最大的用途是解決回溯問題，這也包含了消解遞歸；而當你用棧解決回溯問題成了習慣的時候，你就很少想到用遞歸了，比如迷宮求解。另外，人的習慣也是先入為主的，比如樹的遍歷，從學的那天開始，就是遞歸算法，雖然書上也教了用棧實現的方法，但應用的時候，你首先想到的還是遞歸；當然了，如果語言本身不支持遞歸（如BASIC），那棧就是唯一的選擇了——好像現在的高級語言都是支持遞歸的。
如下是表達式類的定義和實現，表達式可以是中綴表示也可以是后綴表示，用頭節點數據域里的type區分，這里有一點說明的是，由于單鏈表的賦值函數，我原來寫的時候沒有復制頭節點的內容，所以，要是在兩個表達式之間賦值，頭節點里存的信息就丟了。你可以改寫單鏈表的賦值函數來解決這個隱患，或者你根本不不在兩個表達式之間賦值也行。
#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<ExpNode<Type> >
{
public:
void Input()
{
MakeEmpty(); Get()->type =INFIX;
cout << endl << "輸入表達式，以＝結束輸入" << endl;
Type opnd; char optr = ' ';
while (optr != '=')
{
cin >> opnd;
if (opnd != 0)
{
ExpNode<Type> newopnd(opnd);
LastInsert(newopnd);
}
cin >> optr;
ExpNode<Type> newoptr(optr);
LastInsert(newoptr);
}
}
void Print()
{
First();
cout << endl;
for (ExpNode<Type> *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() //將中綴表達式轉變為后綴表達式
{
First();
if (Get()->type == POSTFIX) return *this;
Stack<char> s; s.Push('=');
Expression temp;
ExpNode<Type> *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<Type> 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<Type> s; Type left, right;
for (ExpNode<Type> *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
幾點說明
l 表達式用單鏈表儲存，你可以看到這個鏈表中既有操作數又有操作符，如果你看過我的《如何在一個鏈表中鏈入不同類型的對象》，這里的方法也是對那篇文章的補充。
l 輸入表達式時，會將原來的內容清空，并且必須按照中綴表示輸入。如果你細看一下中綴表達式，你就會發現，除了括號，表達式的結構是“操作數”、“操作符”、“操作數”、……“操作符（＝）”，為了統一這個規律，同時也為了使輸入函數簡單一點，規定括號必須這樣輸入“0（”、“）0”；這樣一來，“0”就不能作為操作數出現在表達式中了。因為我沒有在輸入函數中增加容錯的語句，所以一旦輸錯了，那程序就“死”了。
l 表達式求值的過程是，先變成后綴表示，然后用后綴表示求值。因為原書講解的是這兩個算法，并且用這兩個算法就能完成中綴表達式的求值，所以我就沒寫中綴表達式的直接求值算法。具體算法說明參見原書，我就不廢話了。
l Calculate()注釋掉的兩行，“％”是因為只對整型表達式合法，“^”的Power()函數沒有完成。