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;
    }
}

思考

雖然上述代碼中只考慮了加減運算符，但是由此可以將其擴展到同時包含乘除運算符的表達式求解中。在包含乘除符號時，代碼的實現邏輯是很像的，只不過在將數值入棧時，因為乘除的運算優先順序大於加減，所以需要將前一個元素出棧並與當前元素運算後再進棧。這樣做，可以保證乘除的優先順序更高。