题解 | #表达式求值#

// mark一下


import java.util.*;

// 操作数栈 和 操作符栈
// 操作符运算优先级：+ - 小于 * /
// （ 直接入栈
// 遇到）双栈出 进行运算 直到遇到（
// 其他情况 数字直接入栈 符号优先级大于操作符栈顶元素入栈 否则进行运算
// 第一个-或者（后紧跟的- 表示负号
// 需要在字符串结尾加一个表示符号 处理当最后一个字符是数字时的情况


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            int length = s.length();
            Stack<Integer> numStack = new Stack<>();
            Stack<Character> opStack = new Stack<>();
            String numStr = "";
            for (int i = 0 ; i <= length; i++) {
                // 需要在字符串结尾加一个表示符号 处理当最后一个字符是数字时的情况
                char c = i == length ? '$' : s.charAt(i);
                if (c >= '0' && c <= '9') {
                    numStr += c;
                } else {
                    // 开始遍历字符了 需要对之前的数字字符串转换并存入数字栈
                    if (numStr.length() > 0) {
                        numStack.push(Integer.valueOf(numStr));
                        numStr = "";
                    }

                    if (c == '+' || c == '-') {
                        if (c == '-') {
                            // 负数的情况
                            if (i == 0 || s.charAt(i - 1) == '(') {
                                numStr = "-";
                                continue;
                            }
                        }
                        while (!opStack.isEmpty() 
                            && ((opStack.peek() == '+') 
                            || (opStack.peek() == '-')
                            || (opStack.peek() == '*')
                            || (opStack.peek() == '/'))) {
                                char curChar = opStack.pop();
                                int num2 = numStack.pop();
                                int num1 = numStack.pop();
                                numStack.push(calc(curChar, num1, num2));
                            }
                        opStack.push(c);
                    } else if (c == '*' || c == '/') {
                        opStack.push(c);
                    } else if (c == '(') {
                        opStack.push(c);
                    } else if (c == ')') {
                        while (!opStack.isEmpty() && opStack.peek() != '(') {
                            char curChar = opStack.pop();
                            int num2 = numStack.pop();
                            int num1 = numStack.pop();
                            numStack.push(calc(curChar, num1, num2));
                        }
                        // 将(弹出
                        opStack.pop();
                    }
                }
            }

            while (!opStack.isEmpty()) {
                char curChar = opStack.pop();
                int num2 = numStack.pop();
                int num1 = numStack.pop();
                numStack.push(calc(curChar, num1, num2));
            }

            // 最终结果保存在操作数栈中
            System.out.println(numStack.peek());
        }
    }

    public static int calc(char c, int num1, int num2) {
        switch(c) {
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            case '*':
                return num1 * num2;
            case '/':
                return num1 / num2;
        }
        return 0;
    }
}