栈的经典运用

采用上面的代码能够符号是否平衡的判断。

接下来说明一下表达式的求值问题，表达式的求值问题主要设计到操作符的优先级问题，比如（）、*/、+-这几种符号的优先级是不一样的，其中括号的优先级最好，乘除其次，加减最低，我们通常看到的表达式都是中缀表达式，也就是在操作符的两边都有对象，当然括号除外啦，这种中缀表达式是不便于在程序中处理的，因为存在很多的优先级差别，很难把握从那个位置先计算。

如果在表达式中没有了优先级的问题，求值问题也就变得相对来说更加简单了，后缀表达式是一种非优先级的表达式表示方式，但是如何实现中缀表达式到后缀表达式的切换也是很难实现的。

中缀表达式到后缀表达式的实现如下:

中缀表达式：
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;
}