中缀表达式的转化---zoj_2483,zoj_3025

     在我们的日常生活中，中缀表达式是最常用的计算表达方式3*（-2+4），这种表达方式的优点就是表达的意义容易理解，一目了然。然而，这种表达方式在计算机识别方面缺十分不方便，其原因主要是，括号对于优先级的限制给编写识别程序造成了不便。

     然而后缀表达式对于计算机的解析有这很大的遍历，它不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：21+3*,即(2 + 1) * 3。

     那么，如何将中缀表达式转化为后缀表达式呢，从本质上来说，中缀表达式是对于一颗计算树的中序遍历，同理，后缀表达式则是对它的后顺序遍历。那么其中的一种思路是首先根据中缀表达式构造计算树，然后对之后序遍历即可。

     具体过程可以通过一个栈和一个后缀列表来完成：

1.       从左到右读取中缀表达式中的一项

2.       如果是操作数直接进入后缀列表.

 

3.       读到左括号时总是将它压入栈中.

4.       读到右括号, 将最近栈顶的第一个左括号上面的操作符全部依次弹出, 送至输出队列后, 再丢弃左括号.

5.       当读到操作符时,将该操作符与栈顶操作符比较，如果栈顶操作符优先级大于等于该操作符，那么将栈顶元素弹出到列表，重复次操作，直到遇到括号，或者是优先级小于该操作符，最后将该操作符，压入栈顶

6.       中缀表达式全部读完后，若栈中仍然有运算符，将其送到输出队列中.

其中值得注意的是单目运算符，如-,!等，!!!!false这中情况需要特殊处理