棧是計算機術語中比較重要的概念，實質上棧就是一段內存區域，但是棧滿足一定的特性，那就是只有一個口，具有先入后出的特性，這種特性在計算機中有很廣泛的運用。其實在程序員無時無刻不在運用棧，函數的調用是我們間接使用棧的最好例子，因此可以說棧的一個最重要的運用就是函數的調用。但是棧的運用還不止這些，還有很多，其中幾個典型的運行如下：判斷平衡符號，實現表達式的求值（也就是中綴表達式轉后綴表達式的問題以及后綴表達式求值問題），在路勁探索中實現路勁的保存也可以說是棧的經典運用之一。具體的問題具體分析，只要滿足先入后出特性的問題都能找到現成的數據結構---棧。
本文采用C++中的vector實現棧結構，然后利用棧實現判斷平衡符號，實現中綴表達式到后綴表達式的轉換，并依據棧實現簡單的整數加減乘除運算。
首先棧的實現，由于在C++中采用了vector來代替原始的數組操作，這種比較方便的容器能較好的實現數組的功能，當然棧也可以采用鏈表實現，但是我認為鏈表沒有數組直觀，而且在實際的計算機里也是采用連續的存儲空間作為棧空間的，因此選擇Vector。主要實現三個操作，push、pop以及為空判斷。基本的形式如下：
#ifndef __MYSTACK_H_H_
#define __MYSTACK_H_H_
#include "myvector.h"
namespace myspace
{
template<typename Object>
class Stack
{
public:
Stack(){}
void push(const Object &x)
{
objects.push_back(x);
}
const Object &pop()
{
int len;
if(!isempty())
{
objects.pop_back();
len = objects.size();
return objects[len];
}
}
bool isempty()const
{
return (objects.size() == 0);
}
int size()
{
return objects.size();
}
private:
Vector<Object> objects;
};
}
#endif
實現了簡單的棧類，接下來采用棧實現一些簡單的運用。
符號的平衡問題
在語言中往往需要判斷一些符號是否是成對出現的，比如<>,{},[],()，通常在C++中也只有這幾種對稱問題，如何讓判斷符號的對稱也是很多代碼判斷的首要任務。當然實現的方式是多種多樣的，采用棧的實現會相對更加簡單。基本的實現思路如下：
假設在讀入一串字符串以后，如果遇到對稱符號的左邊部分，則將其壓入棧中，當遇到對稱符號的右邊部分，則彈出棧中的一個對象，實現比對，如果是對稱的，則說明當前的符號是平衡的，如果不對稱，則說明當前字符串是不平衡的，當字符串讀完以后，如果所有的符號都是平衡的，棧中此時應該就是為空，通過判斷棧中是否為空，說明字符串是否是符號平衡的。
依據上面實現的棧類，實現符號平衡判斷的過程比較簡單，如下所示：
bool isbalance(const string &str)
{
string::size_type len = str.size();
Stack<char> stack;
for(string::size_type i = 0; i < len ; ++ i)
{
/*first selection*/
if(str[i] == '[' || str[i] == '{' ||
str[i] == '(' || str[i] == '<')
{
stack.push(str[i]);
}
/*如果是對稱的符號，則從棧中彈出*/
if(str[i] == ']' || str[i] == '}' ||
str[i] == ')' || str[i] == '>')
{
/*如果棧中沒有對象，則說明不平衡*/
if(stack.isempty())
{
cout << "the string is Unblanced" << endl;
return false;
}
/*采用switch-case語句判斷*/
switch(str[i])
{
case ']':
{
/*判斷是否是匹配的*/
if('[' != stack.pop())
{
cout << "Can not blanced with ]" << endl;
return false;
}
break;
}
case ')':
{
if('(' != stack.pop())
{
cout << "Can not blanced with )" << endl;
return false;
}
break;
}
case '}':
{
if('{' != stack.pop())
{
cout << "Can not blanced with }" << endl;
return false;
}
break;
}
case '>':
{
if('<' != stack.pop())
{
cout << "Can not blanced with >" << endl;
return false;
}
break;
}
/*一般的非對稱字符*/
default:
break;
}
}
}
/************************************************
*當所有對象遍歷完成以后，需要判斷棧中是否存在對象
*棧中為空說明是平衡的，非空則說明是非空的對象
************************************************/
if(stack.isempty())
{
cout << "string is blanced!!" << endl;
return true;
}
else/*沒有正確的匹配,并輸出具體不匹配的符號*/
{
cout << stack.pop() << " " << "Unblance string!!" << endl;
return false;
}
}
采用上面的代碼能夠符號是否平衡的判斷。
接下來說明一下表達式的求值問題，表達式的求值問題主要設計到操作符的優先級問題，比如（）、*/、+-這幾種符號的優先級是不一樣的，其中括號的優先級最好，乘除其次，加減最低，我們通常看到的表達式都是中綴表達式，也就是在操作符的兩邊都有對象，當然括號除外啦，這種中綴表達式是不便于在程序中處理的，因為存在很多的優先級差別，很難把握從那個位置先計算。
如果在表達式中沒有了優先級的問題，求值問題也就變得相對來說更加簡單了，后綴表達式是一種非優先級的表達式表示方式，但是如何實現中綴表達式到后綴表達式的切換也是很難實現的。
中綴表達式到后綴表達式的實現如下:
中綴表達式：
a*b+c*d-e/f
后綴表達式：
ab*cd*+ef/-
從上面的表達式可以知道后綴表達式相對來說比較容易判斷計算的基本過程，而且不存在括號的煩惱。采用棧實現轉換的基本思路如下：
對一個中綴表達式進行遍歷，當遇到非操作符的字符直接保存到后綴表達式的存儲空間中，如果遇到左括號，則將左括號壓入棧中,因為優先級最高，只有遇到右括號才會被彈出。如果遇到右括號，則將左括號之前的操作符全部彈出，并保存到后綴表達式的存儲空間中，當然這種存儲的順序和出棧的順序是一致的，括號操作符在后綴表達式中是不存在的，因此不需要將括號保存到后綴表達式的存儲空間中。如果遇到乘除操作符（*/），則判斷棧中的操作符優先級是否低于當前的操作符也就是判斷是否是加減操作符，如果不是則將棧中的操作符（也就是*、/），并保存到后綴表達式存儲空間中，然后將當前的操作符壓入棧中，如果是則直接將操作符入棧。如果操作符是加減操作符，則彈出棧中左括號之前的所有操作符，并保存到后綴表達式存儲空間中，然后將操作符本身壓入棧中。當字符串遍歷完成以后，依次彈出操作符，并保存到后綴表達式存儲區中。
通過上面處理的中綴表達式就能完成后綴的轉換，但是由于需要比較操作符的優先級問題，因此可能需要出棧以后，直接將對象又壓棧的問題，這是實現這類轉換時需要注意的。基本的實現如下：
/*****************************************
* 實現表達式中綴到表達式后綴的轉換
*****************************************/
bool midtolast(string &src, string &dst)
{
string::size_type len = src.size();
/*用來保存棧中彈出的對象*/
char temp = '\0';
Stack<char> stack;
for(string::size_type i = 0; i != len; ++ i)
{
switch(src[i])
{
/*如果是'(',則將左括號壓入棧中*/
case '(':
{
stack.push(src[i]);
break;
}
/*如果是')',則將棧中左括號之前的對象彈出*/
case ')':
{
/*如果為空，則說明表達式不準確*/
if(stack.isempty())
{
return false;
}
/*非空，彈出對象*/
temp = stack.pop();
/*只要不是左括號，則全部彈出*/
while('(' != temp )
{
/*并輸出到后綴表達式中*/
dst += temp;
/*保證棧為非空*/
if(stack.isempty())
break;
/*彈出新的對象*/
temp = stack.pop();
}
/*如果彈出的是左括號，則不用輸出到后綴表達式*/
break;
}
/***************************************
乘除法操作實質上是一致的
在壓入棧中之前，需要彈出非左括號的同優先級對象
遇到左括號或者低優先級的對象就停止，直接入棧
****************************************/
case '*':
case '/':
{
/*判斷非空的棧，為空則直接入棧即可*/
if(!stack.isempty())
{
temp = stack.pop();
while(temp != '+' && temp != '-' && temp != '(')
{
dst += temp;
if(stack.isempty())
{
/*保證temp不影響后面的壓棧操作*/
temp = '\0';
break;
}
temp = stack.pop();
}
}
/*如果當前的temp是+-(,則返回到棧中*/
if(temp == '+' || temp == '-' || temp == '(')
{
stack.push(temp);
}
/*將當前操作符壓棧*/
stack.push(src[i]);
break;
}
case '-':
case '+':
{
/*判斷非空*/
if(!stack.isempty())
{
/*加減操作的優先級最低，因此需要彈出所有非左括號的操作符*/
temp = stack.pop();
while(temp != '(' )
{
/*將操作符輸出到后綴表達式中*/
dst += temp;
if(stack.isempty())
{
temp = '\0';
break;
}
temp = stack.pop();
}
}
/*如果當前彈出的對象是’(‘,則重新壓入棧中*/
if(temp == '(')
{
stack.push(temp);
}
/*將操作符本身壓入棧中*/
stack.push(src[i]);
break;
}
default:
{
/*針對字符而言直接輸出到后綴表達式*/
dst += src[i];
break;
}
}
}
/*將棧中非空的操作符輸出到后綴表達式中*/
while(!stack.isempty())
{
temp = stack.pop();
dst += temp;
}
return true;
}
后綴表達式求值的問題，實現了后綴表達式的轉換，實現表達式的求值問題也就比較簡單了，實現的基本思路如下：
遍歷后綴表達式，遇到非操作符的字符則直接壓入棧中，如果遇到操作符則從棧中彈出兩個對象，進行對應的操作，然后將計算的結果又壓入棧中。繼續遍歷，直到表達式被遍歷完成，此時棧中保存的值也就是當前表達式的值，需要注意除法和減法的操作數順序問題以及除數不能為0的。為了說明該方法的準確性，我采用0-9以內的數作為操作數，進行4則運算，目前我還只能實現這些計算，對于復雜的多位數還需要另外的處理。實現的代碼如下：
/*后綴表達式求值問題*/
int retVal(const string &src)
{
Stack<int> stack;
int temp = 0, s = 0;
int len = src.size();
for(string::size_type i = 0; i != len; ++ i)
{
/*本程序只能處理整形的加減乘除操作*/
switch(src[i])
{
/*遇到數值直接壓入棧中*/
case '0':case '1':case '2': case '3': case '4':
case '5':case '6':case '7': case '8': case '9':
{
stack.push(myatoi(src[i]));
break;
}
/*********************************************
* 遇到操作符彈出兩個數值進行操作
* 需要注意減法和除法的壓棧順序
* 操作完成以后將得到的結果壓入到棧中
* 最后棧中的值就是計算的結果
**********************************************/
case '+':
{
temp = stack.pop() + stack.pop();
stack.push(temp);
temp = 0;
break;
}
case '-':
{
s = stack.pop();
temp = stack.pop() - s;
stack.push(temp);
s = 0;
temp = 0;
break;
}
case '*':
{
temp = stack.pop() * stack.pop();
stack.push(temp);
temp = 0;
break;
}
case '/':
{
s = stack.pop();
if(s != 0)
{
temp = stack.pop() / s;
}
stack.push(temp);
s = 0;
temp = 0;
break;
}
}
}
/*獲得最后的值*/
return stack.pop();
}
為了分析上面的代碼準確性，寫了如下的測試代碼：
int main()
{
string s1;
cout << "Input a string to test the balance :" << endl;
cin >> s1;
isbalance(s1);
#if 10
string src;
string dst;
cout << "Input a expression: " << endl;
cin >> src;
midtolast(src,dst);
cout << "After the convertion: " << endl;
cout << dst << endl;
cout << "The result of expression: " << endl;
cout << retVal(dst) << endl;
#endif
return 0;
}
測試結果：
[gong@Gong-Computer data_struct]$ vi testblance.cpp
[gong@Gong-Computer data_struct]$ g++ -g testblance.cpp -o testblance
[gong@Gong-Computer data_struct]$ ./testblance
Input a string to test the balance :
This(is)[a]{te}<st>.
string is
Input a expression:
3*3-(5-2+3*6)*(7-3*1)
After the convertion:
33*52-36*+731*-*-
The result of expression:
-75
從上面的測試結果基本上實現符號平衡測試、表達式的求值問題，但是當前的表達式只能計算0-9為操作數的四則運算，復雜的多位數還不能進行測試。
以上的三個例子是棧的經典運用，對棧的特性先入后出有更深層次的理解才能更好的運用。
在函數調用中，如果不保存調用程序的狀態，在被調用程序中就會修改程序的狀態，這時候也就不能還原到之前的狀態，只有將當前的狀態保存起來，壓入棧中，當被調用程序執行完成以后，將當前程序棧中的內容彈出就能實現任務狀態的還原，當前函數執行完成以后，調用該函數的狀態也需要還原。這時候就實現了先調用的函數最后執行，所以說函數調用是典型的先入后出問題。這也說明為什么棧如此的重要。