【每日算法Day 90】基本计算器II

由浅入深、循序渐进地解决基本计算器问题，用栈和递归将复杂问题化解为简单问题。

LeetCode 227. 基本计算器 II/III (opens new window)

题目描述

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符、括号和空格。 整数除法仅保留整数部分。你可以假设所给定的表达式都是有效的。

示例

输入: "3+2*2"
输出: 7

输入: " 3+5 / 2 "
输出: 5

输入: "(3+ 2)*  (1-2) "
输出: -5

解题思路

和上一题相比新增了乘除法的情况，其实考虑下遇到操作符为乘除的情况，num为运算符右边的数，而运算符左边的数就在栈顶，我们只需要弹出栈顶和num做相应运算再压入栈顶即可。时间复杂度：扫描一遍括号下标对应关系O(n)，每个数字只会在处理过程中入栈出栈1次O(n)，总时间复杂度为O(n)；空间复杂度：不考虑括号导致的递归调用栈深度的话，用到了map和处理过程中的栈为O(n)空间大小。

Map<Integer, Integer> brackets = new HashMap<>();

public int calculate(String s) {
    //将左右括号的对应关系存入map，避免后面重复计算
    findMatchingBrackets(s);
    return calculate(s, 0, s.length() - 1);
}

private int calculate(String s, int start, int end) {
    Deque<Integer> stack = new LinkedList<>();
    int num = 0;
    char sign = '+';
    for (int i = start; i <= end; i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) { //如果是数字就转化并暂存到num中
            num = num * 10 + (c - '0');
        } else if (c == '(') { //如果是左括号，那么查找对应右括号的位置并递归计算左右括号间表达式的值
            int rightBracket = brackets.get(i);
            num = calculate(s, i + 1, rightBracket - 1);
            //把处理到的位置设为右括号的位置
            i = rightBracket;
        }
        if ((!Character.isDigit(c) && c != ' ') || i == end) {//如果是运算符或者到了结尾就将已经得到的num入栈，跳过空格等不相关字符
            switch (sign) {
                case '+':
                    stack.push(num);
                    break;
                case '-':
                    stack.push(-num);
                    break;
                case '*':
                    stack.push(stack.pop() * num);
                    break;
                case '/':
                    stack.push(stack.pop() / num);
                    break;
            }
            //重置num并更新sign为当前运算符，到了结尾运算符就不会再用了
            sign = c;
            num = 0;
        }
    }
    int answer = 0;
    while (!stack.isEmpty())
        answer += stack.pop();
    return answer;
}

private void findMatchingBrackets(String s) {
    Deque<Integer> stack = new LinkedList<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            stack.push(i);
        } else if (c == ')') {
            brackets.put(stack.pop(), i);
        }
    }
}