中缀表达式求值

算法思想

1. 借助栈处理表达式
   1. 数字压栈
   2. 左括号压栈
   3. 右括号出栈，直至遇到左括号
   4. 算数运算符根据其优先级进行栈的操作

记忆口诀

1. 素质呀
2. 座号呀
3. 有好处
4. 优先吗

算法模板

import java.util.*;
public class Main {
    static int N = 100010;
    static Stack<Integer> num = new Stack<>();
    static Stack<Character> op = new Stack<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String exp = sc.next();

        for(int i = 0; i < exp.length(); i ++ ){
            char ch = exp.charAt(i);

            if(Character.isDigit(ch)){
                int x = 0, j = i;
                while(j < exp.length() && Character.isDigit(exp.charAt(j))){
                    x = x * 10 +  exp.charAt(j ++) - '0';
                }

                num.push(x);
                i = j - 1;
            } else if(ch == '('){
                op.push(ch);
            } else if(ch == ')'){
                while(op.peek() != '(') eval();
                op.pop();
            } else {
	            // 根据优先级，采用二分法处理算数运算符
                while(!op.empty() && op.peek() != '(' && getPrecedence(op.peek()) >= getPrecedence(ch))
                    eval();
                op.push(ch);
            }
        }

        while(!op.empty()) eval();
        System.out.println(num.peek());
    }


    public static void eval(){
        int y = num.pop();
        int x = num.pop();
        char ch = op.pop();

        int s;
        if(ch == '+') s = x + y;
        else if(ch == '-') s = x - y;
        else if(ch == '*') s = x * y;
        else s = x / y;
        num.push(s);
    }

    public static int getPrecedence(char op){
        switch(op){
            case '+': case '-': return 1;
            case '*': case '/': return 2;
            default: return -1;
        }
    }
}