题解 | #四则运算# 先去括号，递归优先计算()里的表达式

不断递归优先计算()里的表达式，核心代码: String newExp = exp.substring(0, j) + calculate(exp.substring(j+1, i)) + exp.substring(i+1);

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    // 先将[]和{}替换成(), 递归
    public static int calculate(String exp) {
        exp = exp.replaceAll("\\{", "(").replaceAll("\\}", ")");
        exp = exp.replaceAll("\\[", "(").replaceAll("\\]", ")");
        // System.out.println("expStart: " + exp);
        for (int i = 0; ;) {
            if(i >= exp.length()){
                break;
            }
            char ch = exp.charAt(i);
            if(ch != ')') {
                i++;
                continue;
            }
            for(int j = i-1; j >= 0; j--){
                if(exp.charAt(j) == '('){
                    String newExp = exp.substring(0, j) + calculate(exp.substring(j+1, i));
                    if(i+1 < exp.length()){
                        newExp += exp.substring(i+1);
                    }
                    exp = newExp;
                    i = j;
                    // System.out.println("newExp: " + exp + ", i=" + i + ", j=" + j);
                    break;
                }
            }
        }

        // 开始计算，此时已经无括号了，eg: 1+2*2-3
        LinkedList<String> stack = new LinkedList<>();
        for (int i = 0; i < exp.length(); i++) {
            char ch = exp.charAt(i);
            // 解析数值
            // System.out.println("stack: " + stack);
            if (Character.isDigit(ch) || (ch == '-')) {
                int sign = 1;
                if (ch == '-') {
                    if (i - 1 >= 0 && Character.isDigit(exp.charAt(i - 1))) { // eg: 8-6, 看做8+-6
                        stack.addLast("+");
                    }
                    sign = -1;
                    i++;
                }
                int num = 0;
                for (; i < exp.length() && Character.isDigit(exp.charAt(i)); i++) {
                    num = num * 10 + (exp.charAt(i) - '0');
                }
                if(!stack.isEmpty() && (stack.getLast().equals("*"))){
                    stack.removeLast();
                    num *= Integer.parseInt(stack.removeLast());;
                }
                if(!stack.isEmpty() && (stack.getLast().equals("/"))){
                    stack.removeLast();
                    num = Integer.parseInt(stack.removeLast()) / num;
                }
                stack.addLast(String.valueOf(num * sign));
                i--; // for循环里有个i++;
            } else {
                stack.addLast(String.valueOf(ch));
            }
        }
        // 剩余全是加法
        int num  = 0;
        while(!stack.isEmpty()){
            String s = stack.removeLast();
            if(!s.equals("+")){
                num += Integer.parseInt(s);
            }
        }
        return num;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println(calculate(in.next()));
    }
}