【每日算法Day 89】基本计算器

LeetCode 224. 基本计算器 (opens new window)

题目描述

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

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格。你可以假设所给定的表达式都是有效的。

示例

输入: " 2-1 + 12 "
输出: 13

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

解题思路

如果不考虑括号，那么我们可以很方便地用一个栈来计算加减法。遇到数字时就连续尝试把字符串转为数字存储在变量num中，当遇到运算符或处理到字符串结尾时，就把当前已经转换的数值根据其前面的符号（之前已经记录）压入栈中，再更新这次的运算符。最后将栈中所有元素取出相加即可。

现在我们来考虑括号，括号中的表达式可以看作一个整体，运算后依然得到的是一个数。遇到的左括号对应的右括号后面要么是运算符，要么是字符串结尾，那么我们可以递归调用自身去求括号内这部分的字串计算出的数值，将该值存储到num中，然后将下一个处理位置设为右括号右边，下面依然按照之前的逻辑入栈即可。

一开始，我写了一个方法对于每次遇到的左括号都找一遍与之对应的右括号的位置，并且根据该位置创建字串作为递归调用的参数。这样，如果有大量的嵌套括号会有很多重复的计算，并且创建了大量的字符串对象，运行时间和内存消耗都非常高。针对第一个问题，开始先扫描一遍字符串并使用一个map存储左右括号的位置对应关系，后面遇到左括号时就能快速知道右括号的位置；针对第二个问题，不创建字串，而是重载递归方法，传入处理的开始位置和结束位置，调整入栈的条件为处理到结束位置就入栈。

class Solution {
    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 (c == '+' || c == '-' || i == end) {//如果是运算符或者到了结尾就将已经得到的num入栈，跳过空格等不相关字符
                switch (sign) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-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);
            }
        }
    }
}