1.中缀表达式，前缀，后缀表达式

**表达式树的生成规则:按照优先级(括号在计算时去处理)叶子节点为数值,父节点为操作符,表达式自左到右生成树**
中缀表达式：(3+4)*5-6   (树的中序遍历)
前缀表达式: -*+3456     (树的前序遍历)
后缀表达式: 34+5*6-     (树的后序遍历)

2.中缀表达式转换为前后缀表达式

3.表达式求值

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class Test01_ExpressionResult {
    static Stack<Character> opCharStk = new Stack<>();
    static Stack<Integer> opNumStk = new Stack<>();
    public static void eval(){
        int result;
        Integer a = opNumStk.pop();
        Integer b = opNumStk.pop();
        Character opChar = opCharStk.pop();
        if (opChar == '+'){
            result =  a + b;
        }else if (opChar == '-'){
            result = b - a;
        }else if(opChar == '*'){
            result = a * b;
        }else{
            result = b / a;
        }
        opNumStk.push(result);
    }

    public static Map opCharMap(){
        Map opCharMap = new HashMap();
        opCharMap.put('+',1);
        opCharMap.put('-',1);
        opCharMap.put('*',2);
        opCharMap.put('/',2);
        return opCharMap;
    }


    public static void preOrder(){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char[] chars = str.toCharArray();
        for (int i = chars.length - 1; i >= 0; i--) {
            char c = chars[i];
            if(Character.isDigit(c)){
               /* int x = 0, j = i;
                while(j < chars.length && Character.isDigit(chars[j++]))
                    x = x * 10 + chars[j] - '0';
                i = j - 1;*/
                opNumStk.push(c - '0');
            }else{
                int temp;
                int a = opNumStk.pop();
                int b = opNumStk.pop();
                if (c == '+'){
                    temp =  a + b;
                }else if (c == '-'){
                    temp = a - b;
                }else if(c == '*'){
                    temp = a * b;
                }else{
                    temp = a / b;
                }
                opNumStk.push(temp);
            }
        }
        System.out.println(opNumStk.pop());

    }

    public static void postOrder(){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (Character.isDigit(c)){
                opNumStk.push(c - '0');
            }else{
                int temp;
                int a = opNumStk.pop();
                int b = opNumStk.pop();
                if (c == '+'){
                    temp =  a + b;
                }else if (c == '-'){
                    temp = b - a;
                }else if(c == '*'){
                    temp = a * b;
                }else{
                    temp = b / a;
                }
                opNumStk.push(temp);
            }
        }
        System.out.println(opNumStk.pop());
    }

    public static void inOrder(){
        Map opCharMap = opCharMap();
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (Character.isDigit(c)){
                int x = 0, j = i;
                while (j < chars.length && Character.isDigit(chars[j]))
                    x = x * 10 + chars[j++] - '0';
                i = j - 1;
                opNumStk.push(x);
            }else if ('(' == c)
                opCharStk.push(c);
            else if(')' == c) {
                while(opCharStk.peek() != '(') eval();
                opCharStk.pop();
            }else{
                while (opCharStk.size() > 0 
                && opCharStk.peek() != '('
                &&  Integer.parseInt(opCharMap.get(opCharStk.peek()) + "")  
                >= Integer.parseInt( opCharMap.get(c) + "")) eval();
                opCharStk.push(c);
            }
        }
        while (opCharStk.size() > 0){
            eval();
        }
        System.out.println(opNumStk.peek());
    }

    public static void main(String[] args) {
        //preOrder();
        inOrder();
        //postOrder();
    }
}