题解 | #四则运算#

思路

1. '-'比较麻烦，有时为减号操作符，有时为负号，比如-10*-10、-(8+4+10)，需要判断；
2. 为了避免复杂的判断，'-'只用作负号，不用作减号操作符，减号改为加号操作即可。比如a-b，改为a+(-b)。
3. 表达式的优先规则是从左到右，乘法除法优先，因此加号操作不能先算，先进栈，碰到乘法除法就可以用栈顶计算。最后从左到右，从栈底到栈顶将所有数相加即可。
4. 括号里的子表达式也是一个表达式，使用递归计算返回结果，再作为一个操作数加入计算即可。

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        char[] chars = s.toCharArray();
        int ans = dfs(chars, '$');
        System.out.println(ans);
    }
    // 作为表达式的全局指针
    private static int p = 0;
    /**
     * @param right 代表的是右括号，碰到右括号则停止计算，返回结果
     */
    private static int dfs(char[] chars, char right) {
        Deque stack = new ArrayDeque();
        // 默认的操作符为+
        char oper = '+';
        // 操作的数字
        int num = 0;
        // -不作为操作符，作为负号，碰到-设为true，其他符号则设为false
        boolean negative = false;
        for (; p < chars.length; p++) {
            // 碰到右括号，子表达式计算完毕，退出循环返回结果
            if (chars[p] == right) {
                break;
            } else if (chars[p] == '(') {
                // 计算子表达式，子表达式从下一个指针开始，因此++p
                ++p;
                // 递归计算出子表达式的结果作为操作数
                num = dfs(chars, ')');
            } else if (chars[p] == '[') {
                ++p;
                num = dfs(chars, ']');
            } else if (chars[p] == '{') {
                ++p;
                num = dfs(chars, '}');
            } else if (chars[p] == '+' || chars[p] == '*' || chars[p] == '/') {
                // 如果是-之外的操作符则更新
                oper = chars[p];
                negative = false;
                continue;
            } else if (chars[p] == '-') {
                // -作为负号
                negative = true;
                continue;
            } else {
                // 如果是数字，则转换为整数
                while (p < chars.length && Character.isDigit(chars[p])) {
                    num = num * 10 + chars[p++] - '0';
                }
                // 注意指针要回退
                p--;
            }
            // 根据负号更新操作数的值
            num = negative ? -num : num;
            switch (oper) {
                case '+':
                    // 加法先进栈
                    stack.push(num);
                    break;
                case '*':
                    // 乘法优先，可以直接算
                    stack.push(stack.pop() * num);
                    break;
                case '/':
                    // 除法优先，可以直接算
                    stack.push(stack.pop() / num);
                    break;
            }
            // 注意操作符和操作数要恢复默认值，再进入下一轮计算
            oper = '+';
            num = 0;
        }
        int res = 0;
        while (!stack.isEmpty()) {
            // 注意表达式要从左到右算
            res += stack.pollLast();
        }
        return res;
    }
}