題目地址(227. 基本計算器 II)

https://leetcode-cn.com/problems/basic-calculator-ii/

題目描述

實現一個基本的計算器來計算一個簡單的字符串表達式的值。

字符串表達式僅包含非負整數，+， - ，*，/ 四種運算符和空格  。 整數除法僅保留整數部分。

示例 1:

輸入: "3+2*2"
輸出: 7
示例 2:

輸入: " 3/2 "
輸出: 1
示例 3:

輸入: " 3+5 / 2 "
輸出: 5
說明：

你可以假設所給定的表達式都是有效的。
請不要使用內置的庫函數 eval。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/basic-calculator-ii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

前置知識

公司

暫無

思路

計算器的題目基本都和棧有關，這道題也不例外。

由題目信息可知，s 中一共包含以下幾種數據：

空格
數字
操作符。這里有 + - * /

而對于操作符來說又可以進一步細分：

一元操作符 + -
二元操作符 * /

對于一元操作符來說，我們只需要知道一個操作數即可。這個操作數就是操作符右邊的數字。為了達到這個效果，我們需要一點小小的 trick。

1 + 2

我們可以在前面補充一個 + 號，變成：

+ 1 + 2
# 可看成
(+1)(+2)

再比如:

(-1)(+2)(+3)(-4)

?

括號只是邏輯分組，實際并不存在。下同，不再贅述。

?

而對于二元操作符來說，我們需要知道兩個操作數，這兩個操作數分別是操作符兩側的兩個數字。

(5) / (2)

再比如

(3) * (4)

簡單來說就是，一元操作符綁定一個操作數。而二元操作符綁定兩個操作數。

算法：

從左到右遍歷 s
如果是數字，則更新數字
如果是空格，則跳過
如果是運算符，則按照運算符規則計算，并將計算結果重新入棧，具體見代碼。最后更新 pre_flag 即可。

為了簡化判斷，我使用了兩個哨兵。一個是 s 末尾的 $，另一個是最開始的 pre_flag。

關鍵點解析

記錄 pre_flag，即上一次出現的操作符
使用哨兵簡化操作。一個是 s 的 $ ，另一個是 pre_flag 的 +

代碼

代碼支持：Python。

Python Code：

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        s += '$'
        pre_flag = '+'
        num = 0

        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == ' ': continue
            else:
                if pre_flag == '+':
                    stack.Append(num)
                elif pre_flag == '-':
                    stack.append(-num)
                elif pre_flag == '*':
                    stack.append(stack.pop() * num)
                elif pre_flag == '/':
                    stack.append(int(stack.pop() / num))
                pre_flag = c
                num = 0
        return sum(stack)

「復雜度分析」

時間復雜度：
空間復雜度：

擴展

基本計算器和這道題差不多，官方難度困難。就是多了個括號而已。所以基本上可以看做是這道題的擴展。題目描述：

實現一個基本的計算器來計算一個簡單的字符串表達式的值。

字符串表達式可以包含左括號 ( ，右括號 )，加號 + ，減號 -，非負整數和空格  。

示例 1:

輸入: "1 + 1"
輸出: 2
示例 2:

輸入: " 2-1 + 2 "
輸出: 3
示例 3:

輸入: "(1+(4+5+2)-3)+(6+8)"
輸出: 23
說明：

你可以假設所給定的表達式都是有效的。
請不要使用內置的庫函數 eval。

拿題目中最難的例子來說 "(1+(4+5+2)-3)+(6+8)"。我們可以將其拆分為：

6+8 (= 14)
4 + 5 + 2 (=11)
(11) - 3 (=8)
1 + (8) (=9)
9 + (14) (=23)

簡單來說就是將括號里面的內容提取出來，提取出來就是上面的問題了。用上面的方法計算出結果，然后將結果作為一個數字替換原來的表達式。

比如我們先按照上面的算法計算出 6 + 8 的結果是 14，然后將 14 替換原來的 (6+8)，那么原問題就轉化為了(1+(4+5+2)-3)+14 。這樣一步一步就可以得到答案。

因此我們可以使用遞歸，每次遇到 ( 則開啟一輪新的遞歸，遇到 )則退出一層遞歸即可。

Python 代碼：

class Solution:
    def calculate(self, s: str) -> int:
        def dfs(s, start):
            stack = []
            pre_flag = '+'
            num = 0
            i = start
            while i < len(s):
                c = s[i]
                if  c == ' ':
                    i += 1
                    continue
                elif c == '(':
                    i, num = dfs(s, i+1)
                elif c.isdigit():
                    num = num * 10 + int(c)
                else:
                    if pre_flag == '+':
                        stack.append(num)
                    elif pre_flag == '-':
                        stack.append(-num)
                    if c == ')': break
                    pre_flag = c
                    num = 0
                i += 1
            return i, sum(stack)
        s += '$'
        return dfs(s, 0)[1]

「復雜度分析」