1、前缀表达式

前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
// - × + 3 4 5 6

前缀表达式的计算机求值

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

将中缀表达式转换为前缀表达式

1.初始化两个栈:运算符栈s1，储存中间结果的栈s2
2.从右至左扫描中缀表达式
3.遇到操作数时，将其压入s2
4.遇到运算符时，比较其与s1栈顶运算符的优先级
（4.1）如果s1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈
（4.2）否则，若优先级比栈顶运算符的较高或相等，也将运算符压入s1
（4.3）否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较
5.遇到括号时
（5.1）如果是右括号“)”，则直接压入s1
（5.2）如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃
6.重复步骤2至5，直到表达式的最左边
7.将s1中剩余的运算符依次弹出并压入s2
8.依次弹出s2中的元素并输出，结果即为中缀表达式对应的前缀表达式

2、中缀表达式

中缀表达式就是常见的运算表达式
// (3+4)×5-6

3、后缀表达式

后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
// 3 4 + 5 × 6 -

后缀表达式计算机求值

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

将中缀表达式转换为后缀表达式

1.初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2.从左至右扫描中缀表达式；
3.遇到操作数时，将其压s2；
4.遇到运算符时，比较其与s1栈顶运算符的优先级：
（4.1）如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
（4.2）否则，若优先级比栈顶运算符的高，也将运算符压入s1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
（4.3）否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
5.遇到括号时：
（5.1）如果是左括号“(”，则直接压入s1；
（5.2）如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
6.重复步骤2至5，直到表达式的最右边；
7.将s1中剩余的运算符依次弹出并压入s2；
8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

中缀表达式转换为后缀表达式代码实现

    @Test
    public void convert() {
        String expression = "( 3 + 4 ) * 5 - 6";
        List<String> result = InfillToSuffix.convert(expression);
        System.out.println(result);
    }
//输出：[-, 6, *, 5, +, 4, 3]，其逆序即需要的后缀表达式

public class InfillToSuffix {

    public static List<String> convert(String Infill) {
        Stack<String> s1 = new Stack<String>();
        Stack<String> s2 = new Stack<String>();
        List<String> result = new ArrayList<String>();
        String[] split = Infill.split(" ");
        for (int i = 0; i < split.length; i++) {
            if (split[i].matches("\\d+")) {
                s2.push(split[i]);
            } else if (split[i].equals("(")) {
                s1.push(split[i]);
            } else if (split[i].equals(")")) {
                while (!s1.peek().equals("(")) {
                    s2.push(s1.pop());
                }
                s1.pop();
            } else {
                while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(split[i])) {
                    s2.push(s1.pop());
                }
                s1.push(split[i]);
            }
        }

        while (s1.size() != 0) {
            s2.push(s1.pop());
        }

        while (s2.size() != 0) {
            result.add(s2.pop());
        }
        return result;
    }

}

public class Operation {
    private static int ADDITION = 1;       //加
    private static int SUBTRACTION = 1;    //减
    private static int MULTIPLICATION = 2; //乘
    private static int DIVISION = 2;       //除

    //返回对应优先级
    public static int getValue(String operation) {
        int result;
        switch (operation) {
            case "+":
                result = ADDITION;
                break;
            case "-":
                result = SUBTRACTION;
                break;
            case "*":
                result = MULTIPLICATION;
                break;
            case "/":
                result = DIVISION;
                break;
            default:
                System.out.println("不存在该运算符");
                result = 0;
        }
        return result;
    }
}