LeetCode-224. 基本计算器

题目来源

224. 基本计算器

题目详情

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入： s = "1 + 1"
输出： 2

示例 2：

输入： s = " 2-1 + 2 "
输出： 3

示例 3：

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

提示：

• 1 <= s.length <= 3 * 105
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式
• '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
• '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
• 输入中不存在两个连续的操作符
• 每个数字和运行的计算将适合于一个有符号的 32位 整数

相似题目

LeetCode-227. 基本计算器 II

题解分析

与 LeetCode-227. 基本计算器 II 题目类似，本题也是要求计算一个算术等式，等式中可能包含括号，空格，加减符号以及数字等字符。这类题目比较直观的解法是使用双栈，其中，一个栈专门用于存储符号，另一个栈专门用于存储数字。

使用双栈法的好处是直观，易于理解，但是缺点也很明显，比如需要考虑的分支条件很多，需要枚举的情况也很多。通常使用双栈的解法代码量较大，而且极易写错。

本文中采用的一种解法是单栈法。这里的单栈其实值得是数值栈，也就是只存储数字。为什么这里可以使用数值栈呢？原因是对于这里只包含加减运算符的表达式，完全可以把加减运算符的结果写入数值栈中，换句话说，对于正数，直接往数值栈中写入原值即可，对于负数，则往数值栈中写入负值。在最后计算时，只需要将栈中的元素依次相加即可得到运算结果。

然而，本题中的符号不仅包括加减，还包括括号。对于括号中的运算，具备优先一起计算的特点。由于括号的出现，上述单栈法似乎行不通了。其实，当仔细观察带括号的表达式时，我们可以发现，括号内的表达式完全可以作为一个子表达式进行求解，求解完后再将结果作为外层表达式的运算值。所以，基于上述性质，这里可以使用递归的思路完成带括号的表达式运算，也就是每次遇到左括号就调用一次递归函数，遇到右括号就结束递归，计算栈中的结果返回到外层。外层会将该结果入栈，作为中间操作数继续遍历原表达式。

需要注意的是，因为引入了递归，进入递归后的表达式不能重复计算，所以在函数中需要记录当前遍历到的字符串位置，递归返回到外层时需要从新的位置继续遍历。

java代码实现

class Solution {
    // 字符串的长度
    int n;
    // 记录当前遍历的位置
    int pt;
    public int calculate(String s) {
        n = s.length();
        pt = 0;
        return dfs(s, 0);
    }

    public int dfs(String s, int i) {
        Deque<Integer> sta = new LinkedList<>();
        int num = 0;
        char sign = '+';
        while (i<n) {
            char ch = s.charAt(i++);
            pt = i;
            if (Character.isDigit(ch)) {
                num = num * 10 + ch - '0';
            }
            if (ch == '(') {
                num = dfs(s, i);
                i = pt;
            }
            // 当前字符为左括号，也会将计算好的括号内的数字进栈

            if ((!Character.isDigit(ch) && ch != ' ') || (i == n)) {
                switch (sign) {
                    case '+':
                        sta.push(num);
                        break;
                    case '-':
                        sta.push(-num);
                        break;
                }
                num = 0;
                sign = ch;
            }

            // 当前为右括号，也将右括号前的数字进栈了
            if (ch == ')') {
                break;
            }
        }
        int res = 0;
        while(!sta.isEmpty()) {
            res += sta.pop();
        }
        return res;
    }
}

思考

虽然上述代码中只考虑了加减运算符，但是由此可以将其扩展到同时包含乘除运算符的表达式求解中。在包含乘除符号时，代码的实现逻辑是很像的，只不过在将数值入栈时，因为乘除的运算优先级大于加减，所以需要将前一个元素出栈并与当前元素运算后再进栈。这样做，可以保证乘除的优先级更高。