224. Basic Calculator

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

solution

class Solution:
    def calculate(self, s: str) -> int:
        stack= []
        res = 0
        sign = 1
        i = 0
        while i < len(s):  # 使用while是因为遇到数字本该计算 res += sign * num, 但num可能是多位数字
            if s[i].isdigit():
                tmp = int(s[i])
                i += 1
                while i < len(s) and s[i].isdigit():
                    tmp = tmp * 10 + int(s[i])
                    i += 1
                res += sign * tmp  # 没有括号的加减通过sign在这里实现
            elif s[i] == '+':
                sign = 1
                i += 1
            elif s[i] == '-':
                sign = -1
                i += 1
            elif s[i] == '(':
                stack.append(res)
                stack.append(sign)
                res, sign = 0, 1
                i += 1
            elif s[i] == ')':
                res *= stack.pop()  # 符号, 和decoder string一样保存多信息在stack
                res += stack.pop()  # 数字
                i += 1
            else:  # 字符串，总会遇到空格等其他问题字符
                i += 1
        return res

时间复杂度：O(n) 空间复杂度：O(n)

follow-up

227. Basic Calculator II

# 空间可以进一步优化为O(1)

class Solution:
    def calculate(self, s: str) -> int:
        s += "+"  # 注意trick, 符号会触发上一个符号的运算, 所以 sum(stack) + num结果. 另一种思路是else那里多加一个条件
        num = 0  # num和op的含义非常重要，num代表了本次的数，入栈了则代表之前的数
        last_op = '+'
        stack = []
        for char in s:
            if '0' <= char <= '9':
                num = num * 10 + int(char)  # 类型
            elif char == ' ':  # 重要corner case, 除了数字、字母还存在空格
                pass
            else:
                # 注意判断的是last_op (上一个运算). 遇到本次运算符，上个运算需要的元素才备齐(一个元素在stack, 一个是num, 以及last_op)
                # 由此也导致了最后一个元素没有入栈
                if last_op == '+':
                    stack.append(num)
                elif last_op == '-':
                    stack.append(-num)
                elif last_op == '*':
                    stack[-1] *= num
                elif last_op == '/':  # python负数向下取整
                    stack[-1] = int(stack[-1] / num)

                num = 0  # 注意num的更新
                last_op = char
        return sum(stack)

时间复杂度：O(n) 空间复杂度：O(n)

* 772. Basic Calculator III

# 遇到左括号时，进入递归，遇到右括号时退出.

class Solution:
    def __init__(self) :
        self.i = 0
    
    def calculate(self, s):
        return self.parse_expr(s)
    
    def parse_expr(self ,s) :
        nums = []
        op = '+'
        while self.i < len(s) and op != ')':  # 遇到右括号退出递归
            if s[self.i] == ' ' :
                self.i += 1
                continue
            
            if s[self.i] == '(': # 遇到左括号进入递归
                self.i += 1         
                n = self.parse_expr(s)
            
            else:
                # 字符串转化数字
                n = 0
                while self.i < len(s) and s[self.i] >= '0' and s[self.i] <='9' :
                    n = ord(s[self.i]) - ord('0') + 10 * n
                    self.i += 1
        
            if op == '+' : 
                nums.append(n)		
            elif op == '-' :
                nums.append(-n)		
            elif op == '*' :
                nums[-1] *= n			
            elif op == '/' :
                nums[-1] //= n	
            if self.i >= len(s) :
                break
            op = s[self.i]
            self.i += 1
        
        res = 0
        for n in nums:							
            res += n
        return res

时间复杂度：O() 空间复杂度：O()

*408. Valid Word Abbreviation

# follow up: 2060. Check if an Original String Exists Given Two Encoded Strings

class Solution:
    def valid_word_abbreviation(self, word: str, abbr: str) -> bool:
        i = 0
        j = 0
        while i < len(word) and j < len(abbr):
            if word[i] == abbr[j]:
                i += 1
                j += 1

            elif abbr[j].isdigit() and abbr[j] != '0':  # 注意j的条件, 以及j是代表的数字, j不等于字符串0
                start = j
                while j < len(abbr) and abbr[j].isdigit():
                    j += 1
                i += int(abbr[start:j])
            else:
                return False
        return i == len(word) and j == len(abbr)

时间复杂度：O(m+1) 空间复杂度：O(1)

class Solution:
    def valid_word_abbreviation(self, word: str, abbr: str) -> bool:
        i = 0
        j = 0

        num = 0
        while i < len(word) and j < len(abbr):
            if not abbr[j].isdigit():
                if abbr[j] != word[i]:
                    return False
                i += 1
                j += 1
            else:
                if abbr[j] == '0':
                    return False

                while j < len(abbr) and abbr[j].isdigit():
                    num = num * 10 + int(abbr[j])
                    j += 1

                i += num
                num = 0  # num重置

        return i == len(word) and j == len(abbr)