227. Basic Calculator II

逻辑

Implement a basic calculator to evaluate a simple expression string.

The expression string contains onlynon-negativeintegers,+,-,*,/operators and empty spaces. The integer division should truncate toward zero.

Example 1:

Input: 
"3+2*2"

Output:
 7

Example 2:

Input:
 " 3/2 "

Output:
 1

Example 3:

Input:
 " 3+5 / 2 "

Output:
 5

分析

计算机的题目好像都是op在前，数字带着op走，或者入栈，或者入expression带着走。

注意这里2个陷阱：最后一个数也要加入栈，所以ii == n-1 不是else

/的时候 3/2和-3/2要额外处理。用ceil和floor

--------2025 update-----

总体思路就是遍历时候，遇到时op候，开始计算前一个op操作，因为说明前一个op所有条件到位，为此需要track前一个op的所有操作数， prevnum +op+num

栈的话就是记录prev_num

不用栈的话，多个res不断更新。记得最后结果加入res。

不用栈的做法：

当前若是OP，则可以开始处理之前的OP

对于+- op前的全部加入res， OP后的设为新的prev_num

对于*/ 更新当前prev_num即可。prev_num *=num

class Solution:
    def calculate(self, s: str) -> int:
        op = '+'
        res = prev_num = num = 0
        for i,c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c)
            if c in '+-*/' or i == len(s) - 1:
                if op == '+':
                    res += prev_num
                    prev_num = num
                if op == '-':
                    res += prev_num
                    prev_num = -num
                if op == '*':
                    prev_num *= num
                if op == '/':
                    prev_num = int(prev_num/num)
                num = 0
                op = c
        res+=prev_num
        return res

栈的做法

1. 遇到数字只负责记录

遇到op时开始处理前面的op，因为说明前面op所需要的所有元素都齐全，第一个数字来自stack，第二个数字来自cur_num。

1. 每个操作符触发处理前一个操作

   OP +-只负责压数字， OP */弹栈处理后再压数字。

栈做法的debug代码，帮助理解

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        op = '+'
        num = 0
        for i, c in enumerate(s):
            print(f'---------when char is {c}----------------------------------------------')
            if c.isdigit():
                num = num * 10 + int(c)
                print(f'Deal with char, the current number {num}')
            if c in "+-/*" or i == len(s) - 1:
                # print(f'Deal with op, the current op is {op}, now we are doing:')
                if op == '+':
                    print(f'op is {op}, push {num} into stack')
                    stack.append(num)
                if op == '-':
                    print(f'op is {op}')
                    print(f'push - {num} into stack')
                    stack.append(-num)
                if op == '*':
                    pop = stack.pop()
                    print(f'op is {op}, pop {pop} from stack,push {num} * {pop} into stack')
                    stack.append(pop * num)
                if op == '/':
                    print(f'push {num} / {stack.pop()} into stack')
                    stack.append(stack.pop() // num)
                print(f'set {num} to 0, set {op} to {c}')
                num = 0
                op = c


        return sum(stack)

s = Solution()
s.calculate("1+2*3*4")

class Solution:
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        op ='+'
        snum =''
        n = len(s)
        res = 0
        for ii,i in enumerate(s):
            if i.isdigit():
                snum += i
            if i in "+-*/" or ii == n-1:
                if op == '+':
                    stack.append(int(snum))
                elif op == '-':
                    stack.append(-int(snum))
                elif op == '*':
                    cur = stack.pop()
                    stack.append(cur*int(snum))
                elif op == '/':
                    cur = stack.pop()/int(snum)
                    stack.append(math.floor(cur)) if cur >= 0 else stack.append(math.ceil(cur))
                snum =''
                op = i

        for i in stack :
            res += i


        return res