棧的經(jīng)典運用
加入技術(shù)交流群
后綴表達式求值的問題，實現(xiàn)了后綴表達式的轉(zhuǎn)換，實現(xiàn)表達式的求值問題也就比較簡單了，實現(xiàn)的基本思路如下：
遍歷后綴表達式，遇到非操作符的字符則直接壓入棧中，如果遇到操作符則從棧中彈出兩個對象，進行對應(yīng)的操作，然后將計算的結(jié)果又壓入棧中。繼續(xù)遍歷，直到表達式被遍歷完成，此時棧中保存的值也就是當(dāng)前表達式的值，需要注意除法和減法的操作數(shù)順序問題以及除數(shù)不能為0的。為了說明該方法的準(zhǔn)確性，我采用0-9以內(nèi)的數(shù)作為操作數(shù)，進行4則運算，目前我還只能實現(xiàn)這些計算，對于復(fù)雜的多位數(shù)還需要另外的處理。實現(xiàn)的代碼如下：本文引用地址：http://cafeforensic.com/article/201612/324510.htm
/*后綴表達式求值問題*/
int retVal(const string &src)
{
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;
}
/*********************************************
* 遇到操作符彈出兩個數(shù)值進行操作
* 需要注意減法和除法的壓棧順序
* 操作完成以后將得到的結(jié)果壓入到棧中
* 最后棧中的值就是計算的結(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)確性，寫了如下的測試代碼：
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;
}
測試結(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}
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
從上面的測試結(jié)果基本上實現(xiàn)符號平衡測試、表達式的求值問題，但是當(dāng)前的表達式只能計算0-9為操作數(shù)的四則運算，復(fù)雜的多位數(shù)還不能進行測試。
以上的三個例子是棧的經(jīng)典運用，對棧的特性先入后出有更深層次的理解才能更好的運用。
在函數(shù)調(diào)用中，如果不保存調(diào)用程序的狀態(tài)，在被調(diào)用程序中就會修改程序的狀態(tài)，這時候也就不能還原到之前的狀態(tài)，只有將當(dāng)前的狀態(tài)保存起來，壓入棧中，當(dāng)被調(diào)用程序執(zhí)行完成以后，將當(dāng)前程序棧中的內(nèi)容彈出就能實現(xiàn)任務(wù)狀態(tài)的還原，當(dāng)前函數(shù)執(zhí)行完成以后，調(diào)用該函數(shù)的狀態(tài)也需要還原。這時候就實現(xiàn)了先調(diào)用的函數(shù)最后執(zhí)行，所以說函數(shù)調(diào)用是典型的先入后出問題。這也說明為什么棧如此的重要。
評論