栈的经典运用

中缀表达式：
a*b+c*d-e/f
后缀表达式：
ab*cd*+ef/-

从上面的表达式可以知道后缀表达式相对来说比较容易判断计算的基本过程，而且不存在括号的烦恼。采用栈实现转换的基本思路如下：
对一个中缀表达式进行遍历，当遇到非操作符的字符直接保存到后缀表达式的存储空间中，如果遇到左括号，则将左括号压入栈中,因为优先级最高，只有遇到右括号才会被弹出。如果遇到右括号，则将左括号之前的操作符全部弹出，并保存到后缀表达式的存储空间中，当然这种存储的顺序和出栈的顺序是一致的，括号操作符在后缀表达式中是不存在的，因此不需要将括号保存到后缀表达式的存储空间中。如果遇到乘除操作符（*/），则判断栈中的操作符优先级是否低于当前的操作符也就是判断是否是加减操作符，如果不是则将栈中的操作符（也就是*、/），并保存到后缀表达式存储空间中，然后将当前的操作符压入栈中，如果是则直接将操作符入栈。如果操作符是加减操作符，则弹出栈中左括号之前的所有操作符，并保存到后缀表达式存储空间中，然后将操作符本身压入栈中。当字符串遍历完成以后，依次弹出操作符，并保存到后缀表达式存储区中。

通过上面处理的中缀表达式就能完成后缀的转换，但是由于需要比较操作符的优先级问题，因此可能需要出栈以后，直接将对象又压栈的问题，这是实现这类转换时需要注意的。基本的实现如下：

/*****************************************
* 实现表达式中缀到表达式后缀的转换
*****************************************/
bool midtolast(string &src, string &dst)
{
string::size_type len = src.size();

/*用来保存栈中弹出的对象*/
char temp = ;

Stack 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 = ;
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 = ;
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 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();
}