栈的经典运用
加入技术交流群
后缀表达式求值的问题，实现了后缀表达式的转换，实现表达式的求值问题也就比较简单了，实现的基本思路如下：
遍历后缀表达式，遇到非操作符的字符则直接压入栈中，如果遇到操作符则从栈中弹出两个对象，进行对应的操作，然后将计算的结果又压入栈中。继续遍历，直到表达式被遍历完成，此时栈中保存的值也就是当前表达式的值，需要注意除法和减法的操作数顺序问题以及除数不能为0的。为了说明该方法的准确性，我采用0-9以内的数作为操作数，进行4则运算，目前我还只能实现这些计算，对于复杂的多位数还需要另外的处理。实现的代码如下：本文引用地址：https://www.eepw.com.cn/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])
{
/*遇到数值直接压入栈中*/
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}
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为操作数的四则运算，复杂的多位数还不能进行测试。
以上的三个例子是栈的经典运用，对栈的特性先入后出有更深层次的理解才能更好的运用。
在函数调用中，如果不保存调用程序的状态，在被调用程序中就会修改程序的状态，这时候也就不能还原到之前的状态，只有将当前的状态保存起来，压入栈中，当被调用程序执行完成以后，将当前程序栈中的内容弹出就能实现任务状态的还原，当前函数执行完成以后，调用该函数的状态也需要还原。这时候就实现了先调用的函数最后执行，所以说函数调用是典型的先入后出问题。这也说明为什么栈如此的重要。
评论