leetcode-227. 基本電腦 II

題目

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

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

示例 1:

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

示例 2:

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

示例 3:

輸入: " 3+5 / 2 "
輸出: 5
           

解題思路

說是棧的經典應用，結果好難做，哭哭

最基本的題目，參考了這篇題解：https://leetcode-cn.com/problems/basic-calculator-ii/solution/chai-jie-fu-za-wen-ti-shi-xian-yi-ge-wan-zheng-ji-/

首先讨論隻有

+, -

的情況，對于每個數，用

sign

來表示這個數字之前的符号，然後碰到新的符号後，就把之前的帶符号數字入棧，然後根據字元串中的符号，更新每個數字前的符号。這樣做的意義是，把減法變成了數字内部的，最後可以直接求所有棧内數字的總和

如果增加了

*, /

符号，那麼上面的做法有一點就不行了，不能在最後求棧内數字的總和了。又因為，

*, /

的優先級比

+, -

要高，是以可以稍作修改：當發現目前數字前面的符号是

*, /

時，就先運算一下（用此時棧頂的元素和目前元素做運算），然後把運算結果加入到棧裡面。最後同樣地求棧内總和即可。

代碼

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        op, sign = 0, '+'
        s += '+0'
        for ch in s:
            if ch.isdecimal():
                op = op * 10 + int(ch)
            elif ch == '+' or ch == '-' or ch == '*' or ch == '/':
                if sign == '+' or sign == '-':
                    stack.append(op * (1 if sign == '+' else -1))
                elif sign == '*':
                    stack[-1] *= op
                elif sign == '/':
                    stack[-1] = int(stack[-1] / op)
                op = 0
                sign = ch
        return sum(stack)
           

擴充

如果是帶括号的電腦的話，就用遞歸計算括号内的内容。遞歸的時候需要對原輸入做改變，比如計算

"3 * (1 - 2) + 3 / (2 - 1)"

時，對

(1 - 2)

遞歸後，下一次應該從

+

開始了，是以傳入一個

list

并且用

pop

的方式來通路

list

内的元素

加了對括号的處理，代碼如下：

class Solution:
    def calculate(self, s: str) -> int:
        def helper(s: collections.deque) -> int:
            ans, op = 0, 0
            sign = '+'
            stack = []
            while s:
                ch = s.popleft()
                if ch.isdecimal():
                    op = op * 10 + int(ch)
                elif ch == '+' or ch == '-' or ch == '*' or ch == '/':
                    if sign == '+' or sign == '-':
                        stack.append(op * (1 if sign == '+' else -1))
                    elif sign == '*':
                        stack[-1] *= op
                    elif sign == '/':
                        stack[-1] = int(stack[-1] / op)
                    op = 0
                    sign = ch
                elif ch == '(':
                    op = helper(s)
                elif ch == ')':
                    if sign == '+' or sign == '-':
                        stack.append(op * (1 if sign == '+' else -1))
                    elif sign == '*':
                        stack[-1] *= op
                    elif sign == '/':
                        stack[-1] = int(stack[-1] / op)
                    break
            return sum(stack)
        return helper(collections.deque(s + '+0'))