LeetCode——224. 基本電腦[Basic Calculator][困難]——分析及代碼[Java]

• 一、題目
• 二、分析及代碼
• • 1. 棧
  • • （1）思路
    • （2）代碼
    • （3）結果
• 三、其他

一、題目

實作一個基本的電腦來計算一個簡單的字元串表達式 s 的值。

示例 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 * 10^5
• s 由數字、’+’、’-’、’(’、’)’、和 ’ ’ 組成
• s 表示一個有效的表達式

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/basic-calculator

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二、分析及代碼

1. 棧

（1）思路

設計 2 個棧，分别存儲符号和數字，當遇到右括号時處理目前括号内的計算，直至得到最終答案。

（2）代碼

class Solution {
    public int calculate(String s) {
        String newS = "(" + s + ")";//首尾添加括号，使其處理一般化
        char[] c = newS.toCharArray();
        int n = c.length;
        Stack<Character> signs = new Stack<>();//存儲符号
        Stack<Integer> nums = new Stack();//存儲數字
        
        for (int i = 0; i < n; i++) {
            if (c[i] == '+' || c[i] == '-' || c[i] == '(')//符号及左括号，入符号棧
                signs.add(c[i]);
            else if (c[i] == ')') {//遇到右括号，處理目前括号範圍内的計算
                int res = 0;
                while (signs.peek() != '(') //括号範圍内的加減法
                    res = (signs.pop() == '+') ? res + nums.pop() : res - nums.pop();
                int lastNum = (nums.empty()) ? 0 : nums.pop();//若括号開頭是+或-，添加0使其一般化為0+或0-
                nums.push(res + lastNum);//放入目前括号範圍内的計算結果
                signs.pop();//彈出左括号
            }
            else if (c[i] >= '0' && c[i] <= '9') {//處理數字
                int num = (int)c[i] - '0';
                while (i + 1 < n && c[i + 1] >= '0' && c[i + 1] <= '9')
                    num = num * 10 + (int)(c[++i] - '0');
                nums.add(num);
            }
        }
        return nums.pop();//數字棧中最後剩下的就是計算結果
    }
}
           

（3）結果

執行用時 ：15 ms，在所有 Java 送出中擊敗了 42.05% 的使用者；

記憶體消耗 ：38.4 MB，在所有 Java 送出中擊敗了 88.84% 的使用者。

三、其他

因為本題隻涉及加減法，可結合棧結構，在周遊過程中對各個數字前的正負号進行判斷，在此基礎上直接計算。