题解 | #表达式求值#

看起来好像很基本的一个题目，但是想要通过也不是很简单，太多逻辑上的处理； 核心的话就是栈处理呗，一个操作数栈，一个操作符号栈

• 如果是乘除号，就直接压栈
• 如果是加减号，就对符号栈的栈顶进行判断，如果符号栈是+-*/的运算，就弹栈进行处理，直到栈顶不在是+-*/符号
• 如果是(，直接压栈
• 如果是),直接对符号栈进行弹栈，并对操作数栈进行相应处理，直到符号栈中，该)对应的(被弹出

import java.util.*;
public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String line = sc.nextLine();
            int ans = compute(line);
            System.out.println(ans);
        }
    }
    
    public static int compute(String line){
        int n = line.length(), p = 0;
        Deque<Character> operators = new LinkedList<>();//计算符号栈
        Deque<Integer> nums = new LinkedList<>();//操作数栈
        String numStr = "";
        while(p <= n){
            char c;
            if(p < n){
                c = line.charAt(p);
            }else{
                //在字符串后加一个结尾符号，如果不加，当最后一个元素时数字是就处理不到，因为数字只有在下一个字符的之后才会受到处理
                c = '$';
            }
            if(Character.isDigit(c)){
                //如果遍历到的字符是数字，则将字符加入到数字字符串中
                numStr += c;
            }else{
                //1+2
                //1*2+3
                //(1*2)+3
                //如果遍历到的字符不是数字，那么就先处理一下数字字符串
                if(numStr.length()>0){//如果数字字符串不为空，就像操作数栈中压栈
                    nums.push(Integer.valueOf(numStr));
                    numStr = "";
                }
                //接着处理当前的字符
                if(c == '+' || c == '-'){
                    if(c == '-'){
                        // 此时 -表示负号
                        if(p==0 || line.charAt(p-1) == '('){
                            numStr = "-";
                            p++;
                            continue;
                        }
                    }
                    while(!operators.isEmpty() && (operators.peek() == '*' || operators.peek() == '/' || operators.peek() == '+' || operators.peek() == '-')){
                        char top = operators.pop();
                        int num2 = nums.pop();
                        int num1 = nums.pop();
                        nums.push(doCompute(top, num1, num2));
                    }
                    operators.push(c);
                }else if(c == '*' || c == '/'){
                    operators.push(c);
                }else if(c == '('){
                    operators.push(c);
                }else if(c == ')'){
                    while(operators.peek() != '('){
                        char top = operators.pop();
                        int num2 = nums.pop();
                        int num1 = nums.pop();
                        nums.push(doCompute(top, num1, num2));
                    }
                    operators.pop();
                }
            }
            p++;
        }
        while(!operators.isEmpty()){
            char top = operators.pop();
            int num2 = nums.pop();
            int num1 = nums.pop();
            nums.push(doCompute(top, num1, num2));
        }
        return nums.peek();
    }
    
    public static int doCompute(char op,int num1, int num2){
        switch(op){
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            case '*':
                return num1 * num2;
            case '/':
                return num1 / num2;
        }
        return 0;
    }
    
}