题解 | #表达式求值#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    //使用map维护一个运算符优先级
    Map<Character, Integer> map = new HashMap<Character, Integer>() {
        {
            put('+', 1);
            put('-', 1);
            put('*', 2);
        }
    };

    public int solve(String s) {
        //去掉字符串中的空格
        String str = s.replaceAll(" ", "");

        char[] chars = str.toCharArray();
        int len = str.length();

        //存放操作数
        Deque<Integer> nums = new ArrayDeque<>();
        //以防第一个数是负数，首先在nums里加入0; 减少边界判断
        nums.push(0);
        //存放运算符及括号
        Deque<Character> ops = new ArrayDeque<>();

        for (int i = 0; i < len; i++) {
            char c = chars[i];
            //如果是"("直接加入ops
            if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                //遇到")"ops持续出栈直到遇到"("
                while (!ops.isEmpty()) {
                    if (ops.peek() != '(') {
                        calc(nums, ops);
                    } else {
                        ops.pop();
                        break;
                    }
                }

            } else if (isNumber(c)) {
                int k = 0;
                int j = i;
                // 将从 i 位置开始后面的连续数字整体取出，加入 nums
                while (j < len && isNumber(chars[j])) {
                    k = 10 * k + (chars[j++]-'0');
                }
                nums.push(k);
                i = j - 1;
            } else {
                //(-i+j)>>>(0-i+j)
                if (i > 0 && (chars[i - 1] == '(' || chars[i - 1] == '+' ||  chars[i - 1] == '-')) {
                    nums.push(0);
                }
                // 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
                while (!ops.isEmpty() && ops.peek() != '(') {
                    char pre = ops.peek();
                    if (map.get(pre) >= map.get(c)) {
                        calc(nums, ops);
                    } else {
                        break;
                    }
                }
                ops.push(c);
            }
        }
        // 将剩余的计算完 针对最后栈中只剩一个非"("的操作符  例i*j
        while (!ops.isEmpty()&& ops.peekLast() != '(') {
            calc(nums, ops);
        }
        //下方加注释针对空字符串有空指针异常
        //return nums.pop();
        return nums.peek();
    }

    private boolean isNumber(char c) {
        return Character.isDigit(c);
    }

    // 计算逻辑：从 nums 中取出两个操作数，从 ops 中取出运算符，然后根据运算符进行计算
    private void calc(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) return;
        if (ops.isEmpty()) return;
        int b = nums.pop();
        int a = nums.pop();
        char c = ops.pop();
        int k = 0;
        if (c  == '+') k = a + b;
        else if (c == '-') k = a - b;
        else if (c == '*') k = a * b;
        nums.push(k);
    }
}