中缀表达式就是我们正常工作中写的表达式，如 a+(b-c)*d ，编译系统将中缀表达式改写 abc-d*+ ，这种运算符在操作数后面称为后缀表达式(也称逆波兰表达式)。
如何实现转换的呢？这里做一下自己的理解及记录。
利用栈来实现
转换过程需要用到栈，这里用两个栈，stack 栈用来存放运算符，post 栈用来存放最后的后缀表达式。具体规则如下：
从左到右扫描中缀表达式，若是操作数，直接存入 post 栈；
若是运算符：
(1)该运算符是左括号 ( , 则直接存入 stack 栈。
(2)该运算符是右括号 )，则将 stack 栈中 ( 前的所有运算符出栈，存入 post 栈。
(3)若该运算符为非括号，则将该运算符和 stack 栈顶运算符作比较：若高于栈顶运算符，则直接存入 stack 栈，否则将栈顶运算符出栈(从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止)，存入 post 栈。
(4)当扫描完后，stack 栈中还有运算符时，则将所有运算符出栈，存入 post 栈。
例子：中缀表达式 a + b * c + (d * e + f) * g，其转换成后缀表达式则为a b c * + d e * f + g * +。
扫描
stack 栈
post 栈
a
空
a
a+
+
a
a+b
+
ab
a+b*
+*
ab
a+b*c
+*
abc
a+b*c+
+
abc*+
a+b*c+(
+(
abc*+
a+b*c+(d
+(
abc*+d
a+b*c+(d*
+(*
abc*+d
a+b*c+(d*e
+(*
abc*+de
a+b*c+(d*e+
+(+
abc*+de*
a+b*c+(d*e+f
+(+
abc*+de*f
a+b*c+(d*e+f)
+
abc*+de*f+
a+b*c+(d*e+f)*
+*
abc*+de*f+
a+b*c+(d*e+f)*g
+*
abc*+de*f+g
a+b*c+(d*e+f)*g#
空
abc*+de*f+g*+
注意：表格中第6步，读到+,因为栈顶元素*的优先级高，所以*出栈，栈中下一个元素+优先级与读到的操作符+一样，所以也要弹出。然后再将读到的+压入栈中。
第13步，读到)，则直接将栈中元素弹出直到遇到(为止。这里左括号前只有一个操作符+被弹出。
代码实现
import java.util.Stack;
public class InToPost {
private Stack opStack;
private Stack outStack;
private String input;
public InToPost(String in) {
input = in;
opStack = new Stack();
outStack = new Stack();
}
public Stack doTrans() { //其他类型自行转换
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);
switch (ch) {
case '+':
case '-':
operationOpStack(ch, 1);
break;
case '*':
case '/':
operationOpStack(ch, 2);
break;
case '(':
opStack.push(ch);
break;
case ')':
operationParen();
break;
default:
outStack.push(ch);
break;
}
}
while (!opStack.isEmpty()) {
outStack.push(opStack.pop());
}
return outStack;
}
public void operationOpStack(char opThis, int prec1) {//运算符栈操作
while (!opStack.isEmpty()) {
char opTop = opStack.pop();
if (opTop == '(') {
opStack.push(opTop);
}
else {
int prec2;
if (opTop == '+' || opTop == '-')
prec2 = 1;
else
prec2 = 2;
if (prec2 < prec1) {
opStack.push(opTop);
break;
}
else
outStack.push(opTop);
}
}
opStack.push(opThis);
}
public void operationParen() {
while (!opStack.isEmpty()) {
char c = opStack.pop();
if (c == '(')
break;
else
outStack.push(c);
}
}
public static void main(String[] args) {
String input = "1+2*4/5-7+3/6";
InToPost theTrans = new InToPost(input);
Stack output = theTrans.doTrans();
System.out.println("Postfix is " + output + '\n');
}
}
利用语法树
先将中缀表达式用二叉树表示出来，再后序遍历该二叉树，就得到其相应的后缀表达式。
加括号法
加括号法先将中缀表达式每步要计算的表达式加上括号，然后将每个运算符移到其所在括号的外面，最后，从左到右去掉括号后就是后缀表达式。
例子： a+(b-c)*d
加括号 (a+((b-c)d))
移运算符 (a((bc)-d))+
去括号 abc-d*+
后缀表达式求值
求值过程可用栈来辅助存储。假定待求值的后缀表达式为：6 5 2 3 + 8 * + 3 + *，则其求值过程如下：
遍历表达式，遇到数字首先放入栈，此时栈如下 6 5 2 3
接着读到+，则弹出3和2，执行3+2，将结果5压栈 6 5 5
读到8，压栈 6 5 5 8
读到 *, 弹出8和5，执行8*5，将结果40压栈 6 5 40
读到 +,弹出40和5，执行40+5，将结果45压栈 6 45
读到 3,压栈 6 45 3
读到 +,弹出3和45，执行3+45，将结果48压栈 6 48
读到 *,弹出48和6，执行48*6，将结果288压栈 288
最后结果288
