棧是計(jì)算機(jī)術(shù)語(yǔ)中比較重要的概念，實(shí)質(zhì)上棧就是一段內(nèi)存區(qū)域，但是棧滿足一定的特性，那就是只有一個(gè)口，具有先入后出的特性，這種特性在計(jì)算機(jī)中有很廣泛的運(yùn)用。其實(shí)在程序員無(wú)時(shí)無(wú)刻不在運(yùn)用棧，函數(shù)的調(diào)用是我們間接使用棧的最好例子，因此可以說(shuō)棧的一個(gè)最重要的運(yùn)用就是函數(shù)的調(diào)用。但是棧的運(yùn)用還不止這些，還有很多，其中幾個(gè)典型的運(yùn)行如下：判斷平衡符號(hào)，實(shí)現(xiàn)表達(dá)式的求值（也就是中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的問(wèn)題以及后綴表達(dá)式求值問(wèn)題），在路勁探索中實(shí)現(xiàn)路勁的保存也可以說(shuō)是棧的經(jīng)典運(yùn)用之一。具體的問(wèn)題具體分析，只要滿足先入后出特性的問(wèn)題都能找到現(xiàn)成的數(shù)據(jù)結(jié)構(gòu)---棧。
本文采用C++中的vector實(shí)現(xiàn)棧結(jié)構(gòu)，然后利用棧實(shí)現(xiàn)判斷平衡符號(hào)，實(shí)現(xiàn)中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換，并依據(jù)棧實(shí)現(xiàn)簡(jiǎn)單的整數(shù)加減乘除運(yùn)算。
首先棧的實(shí)現(xiàn)，由于在C++中采用了vector來(lái)代替原始的數(shù)組操作，這種比較方便的容器能較好的實(shí)現(xiàn)數(shù)組的功能，當(dāng)然棧也可以采用鏈表實(shí)現(xiàn)，但是我認(rèn)為鏈表沒(méi)有數(shù)組直觀，而且在實(shí)際的計(jì)算機(jī)里也是采用連續(xù)的存儲(chǔ)空間作為棧空間的，因此選擇Vector。主要實(shí)現(xiàn)三個(gè)操作，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
實(shí)現(xiàn)了簡(jiǎn)單的棧類，接下來(lái)采用棧實(shí)現(xiàn)一些簡(jiǎn)單的運(yùn)用。
符號(hào)的平衡問(wèn)題
在語(yǔ)言中往往需要判斷一些符號(hào)是否是成對(duì)出現(xiàn)的，比如<>,{},[],()，通常在C++中也只有這幾種對(duì)稱問(wèn)題，如何讓判斷符號(hào)的對(duì)稱也是很多代碼判斷的首要任務(wù)。當(dāng)然實(shí)現(xiàn)的方式是多種多樣的，采用棧的實(shí)現(xiàn)會(huì)相對(duì)更加簡(jiǎn)單。基本的實(shí)現(xiàn)思路如下：
假設(shè)在讀入一串字符串以后，如果遇到對(duì)稱符號(hào)的左邊部分，則將其壓入棧中，當(dāng)遇到對(duì)稱符號(hào)的右邊部分，則彈出棧中的一個(gè)對(duì)象，實(shí)現(xiàn)比對(duì)，如果是對(duì)稱的，則說(shuō)明當(dāng)前的符號(hào)是平衡的，如果不對(duì)稱，則說(shuō)明當(dāng)前字符串是不平衡的，當(dāng)字符串讀完以后，如果所有的符號(hào)都是平衡的，棧中此時(shí)應(yīng)該就是為空，通過(guò)判斷棧中是否為空，說(shuō)明字符串是否是符號(hào)平衡的。
依據(jù)上面實(shí)現(xiàn)的棧類，實(shí)現(xiàn)符號(hào)平衡判斷的過(guò)程比較簡(jiǎn)單，如下所示：
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]);
}
/*如果是對(duì)稱的符號(hào)，則從棧中彈出*/
if(str[i] == ']' || str[i] == '}' ||
str[i] == ')' || str[i] == '>')
{
/*如果棧中沒(méi)有對(duì)象，則說(shuō)明不平衡*/
if(stack.isempty())
{
cout << "the string is Unblanced" << endl;
return false;
}
/*采用switch-case語(yǔ)句判斷*/
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;
}
/*一般的非對(duì)稱字符*/
default:
break;
}
}
}
/************************************************
*當(dāng)所有對(duì)象遍歷完成以后，需要判斷棧中是否存在對(duì)象
*棧中為空說(shuō)明是平衡的，非空則說(shuō)明是非空的對(duì)象
************************************************/
if(stack.isempty())
{
cout << "string is blanced!!" << endl;
return true;
}
else/*沒(méi)有正確的匹配,并輸出具體不匹配的符號(hào)*/
{
cout << stack.pop() << " " << "Unblance string!!" << endl;
return false;
}
}
采用上面的代碼能夠符號(hào)是否平衡的判斷。
接下來(lái)說(shuō)明一下表達(dá)式的求值問(wèn)題，表達(dá)式的求值問(wèn)題主要設(shè)計(jì)到操作符的優(yōu)先級(jí)問(wèn)題，比如（）、*/、+-這幾種符號(hào)的優(yōu)先級(jí)是不一樣的，其中括號(hào)的優(yōu)先級(jí)最好，乘除其次，加減最低，我們通常看到的表達(dá)式都是中綴表達(dá)式，也就是在操作符的兩邊都有對(duì)象，當(dāng)然括號(hào)除外啦，這種中綴表達(dá)式是不便于在程序中處理的，因?yàn)榇嬖诤芏嗟膬?yōu)先級(jí)差別，很難把握從那個(gè)位置先計(jì)算。
如果在表達(dá)式中沒(méi)有了優(yōu)先級(jí)的問(wèn)題，求值問(wèn)題也就變得相對(duì)來(lái)說(shuō)更加簡(jiǎn)單了，后綴表達(dá)式是一種非優(yōu)先級(jí)的表達(dá)式表示方式，但是如何實(shí)現(xiàn)中綴表達(dá)式到后綴表達(dá)式的切換也是很難實(shí)現(xiàn)的。
中綴表達(dá)式到后綴表達(dá)式的實(shí)現(xiàn)如下:
中綴表達(dá)式：
a*b+c*d-e/f
后綴表達(dá)式：
ab*cd*+ef/-
從上面的表達(dá)式可以知道后綴表達(dá)式相對(duì)來(lái)說(shuō)比較容易判斷計(jì)算的基本過(guò)程，而且不存在括號(hào)的煩惱。采用棧實(shí)現(xiàn)轉(zhuǎn)換的基本思路如下：
對(duì)一個(gè)中綴表達(dá)式進(jìn)行遍歷，當(dāng)遇到非操作符的字符直接保存到后綴表達(dá)式的存儲(chǔ)空間中，如果遇到左括號(hào)，則將左括號(hào)壓入棧中,因?yàn)閮?yōu)先級(jí)最高，只有遇到右括號(hào)才會(huì)被彈出。如果遇到右括號(hào)，則將左括號(hào)之前的操作符全部彈出，并保存到后綴表達(dá)式的存儲(chǔ)空間中，當(dāng)然這種存儲(chǔ)的順序和出棧的順序是一致的，括號(hào)操作符在后綴表達(dá)式中是不存在的，因此不需要將括號(hào)保存到后綴表達(dá)式的存儲(chǔ)空間中。如果遇到乘除操作符（*/），則判斷棧中的操作符優(yōu)先級(jí)是否低于當(dāng)前的操作符也就是判斷是否是加減操作符，如果不是則將棧中的操作符（也就是*、/），并保存到后綴表達(dá)式存儲(chǔ)空間中，然后將當(dāng)前的操作符壓入棧中，如果是則直接將操作符入棧。如果操作符是加減操作符，則彈出棧中左括號(hào)之前的所有操作符，并保存到后綴表達(dá)式存儲(chǔ)空間中，然后將操作符本身壓入棧中。當(dāng)字符串遍歷完成以后，依次彈出操作符，并保存到后綴表達(dá)式存儲(chǔ)區(qū)中。
通過(guò)上面處理的中綴表達(dá)式就能完成后綴的轉(zhuǎn)換，但是由于需要比較操作符的優(yōu)先級(jí)問(wèn)題，因此可能需要出棧以后，直接將對(duì)象又壓棧的問(wèn)題，這是實(shí)現(xiàn)這類轉(zhuǎn)換時(shí)需要注意的。基本的實(shí)現(xiàn)如下：
/*****************************************
* 實(shí)現(xiàn)表達(dá)式中綴到表達(dá)式后綴的轉(zhuǎn)換
*****************************************/
bool midtolast(string &src, string &dst)
{
string::size_type len = src.size();
/*用來(lái)保存棧中彈出的對(duì)象*/
char temp = '\0';
Stack<char> stack;
for(string::size_type i = 0; i != len; ++ i)
{
switch(src[i])
{
/*如果是'(',則將左括號(hào)壓入棧中*/
case '(':
{
stack.push(src[i]);
break;
}
/*如果是')',則將棧中左括號(hào)之前的對(duì)象彈出*/
case ')':
{
/*如果為空，則說(shuō)明表達(dá)式不準(zhǔn)確*/
if(stack.isempty())
{
return false;
}
/*非空，彈出對(duì)象*/
temp = stack.pop();
/*只要不是左括號(hào)，則全部彈出*/
while('(' != temp )
{
/*并輸出到后綴表達(dá)式中*/
dst += temp;
/*保證棧為非空*/
if(stack.isempty())
break;
/*彈出新的對(duì)象*/
temp = stack.pop();
}
/*如果彈出的是左括號(hào)，則不用輸出到后綴表達(dá)式*/
break;
}
/***************************************
乘除法操作實(shí)質(zhì)上是一致的
在壓入棧中之前，需要彈出非左括號(hào)的同優(yōu)先級(jí)對(duì)象
遇到左括號(hào)或者低優(yōu)先級(jí)的對(duì)象就停止，直接入棧
****************************************/
case '*':
case '/':
{
/*判斷非空的棧，為空則直接入棧即可*/
if(!stack.isempty())
{
temp = stack.pop();
while(temp != '+' && temp != '-' && temp != '(')
{
dst += temp;
if(stack.isempty())
{
/*保證temp不影響后面的壓棧操作*/
temp = '\0';
break;
}
temp = stack.pop();
}
}
/*如果當(dāng)前的temp是+-(,則返回到棧中*/
if(temp == '+' || temp == '-' || temp == '(')
{
stack.push(temp);
}
/*將當(dāng)前操作符壓棧*/
stack.push(src[i]);
break;
}
case '-':
case '+':
{
/*判斷非空*/
if(!stack.isempty())
{
/*加減操作的優(yōu)先級(jí)最低，因此需要彈出所有非左括號(hào)的操作符*/
temp = stack.pop();
while(temp != '(' )
{
/*將操作符輸出到后綴表達(dá)式中*/
dst += temp;
if(stack.isempty())
{
temp = '\0';
break;
}
temp = stack.pop();
}
}
/*如果當(dāng)前彈出的對(duì)象是’(‘,則重新壓入棧中*/
if(temp == '(')
{
stack.push(temp);
}
/*將操作符本身壓入棧中*/
stack.push(src[i]);
break;
}
default:
{
/*針對(duì)字符而言直接輸出到后綴表達(dá)式*/
dst += src[i];
break;
}
}
}
/*將棧中非空的操作符輸出到后綴表達(dá)式中*/
while(!stack.isempty())
{
temp = stack.pop();
dst += temp;
}
return true;
}
后綴表達(dá)式求值的問(wèn)題，實(shí)現(xiàn)了后綴表達(dá)式的轉(zhuǎn)換，實(shí)現(xiàn)表達(dá)式的求值問(wèn)題也就比較簡(jiǎn)單了，實(shí)現(xiàn)的基本思路如下：
遍歷后綴表達(dá)式，遇到非操作符的字符則直接壓入棧中，如果遇到操作符則從棧中彈出兩個(gè)對(duì)象，進(jìn)行對(duì)應(yīng)的操作，然后將計(jì)算的結(jié)果又壓入棧中。繼續(xù)遍歷，直到表達(dá)式被遍歷完成，此時(shí)棧中保存的值也就是當(dāng)前表達(dá)式的值，需要注意除法和減法的操作數(shù)順序問(wèn)題以及除數(shù)不能為0的。為了說(shuō)明該方法的準(zhǔn)確性，我采用0-9以內(nèi)的數(shù)作為操作數(shù)，進(jìn)行4則運(yùn)算，目前我還只能實(shí)現(xiàn)這些計(jì)算，對(duì)于復(fù)雜的多位數(shù)還需要另外的處理。實(shí)現(xiàn)的代碼如下：
/*后綴表達(dá)式求值問(wèn)題*/
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])
{
/*遇到數(shù)值直接壓入棧中*/
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;
}
/*********************************************
* 遇到操作符彈出兩個(gè)數(shù)值進(jìn)行操作
* 需要注意減法和除法的壓棧順序
* 操作完成以后將得到的結(jié)果壓入到棧中
* 最后棧中的值就是計(jì)算的結(jié)果
**********************************************/
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();
}
為了分析上面的代碼準(zhǔn)確性，寫了如下的測(cè)試代碼：
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;
}
測(cè)試結(jié)果：
[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
從上面的測(cè)試結(jié)果基本上實(shí)現(xiàn)符號(hào)平衡測(cè)試、表達(dá)式的求值問(wèn)題，但是當(dāng)前的表達(dá)式只能計(jì)算0-9為操作數(shù)的四則運(yùn)算，復(fù)雜的多位數(shù)還不能進(jìn)行測(cè)試。
以上的三個(gè)例子是棧的經(jīng)典運(yùn)用，對(duì)棧的特性先入后出有更深層次的理解才能更好的運(yùn)用。
在函數(shù)調(diào)用中，如果不保存調(diào)用程序的狀態(tài)，在被調(diào)用程序中就會(huì)修改程序的狀態(tài)，這時(shí)候也就不能還原到之前的狀態(tài)，只有將當(dāng)前的狀態(tài)保存起來(lái)，壓入棧中，當(dāng)被調(diào)用程序執(zhí)行完成以后，將當(dāng)前程序棧中的內(nèi)容彈出就能實(shí)現(xiàn)任務(wù)狀態(tài)的還原，當(dāng)前函數(shù)執(zhí)行完成以后，調(diào)用該函數(shù)的狀態(tài)也需要還原。這時(shí)候就實(shí)現(xiàn)了先調(diào)用的函數(shù)最后執(zhí)行，所以說(shuō)函數(shù)調(diào)用是典型的先入后出問(wèn)題。這也說(shuō)明為什么棧如此的重要。