[LeetCode] 224. Basic Calculator

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

The expression does not include multiplication and division operator. We can calculate the result directly.

When we encounter left-parenthesis, we push current result to stack and restart calculation of the interim expression.

Time complexity = O ( N )

class Solution:
    def calculate(self, s: str) -> int:
        stackSign = [1]
        stackNum = [0]
 
        i = 0
        sign = 1
      
        while i < len(s):
            if s[i] == ' ':
                i += 1
                continue
            
            if s[i] == '-':
                sign = -1
                i += 1
                continue
                
            if s[i] == '+':
                sign = 1
                i += 1
                continue
                
            if s[i] == '(':
                stackSign.append(sign)
                stackNum.append(0)
                sign = 1 # reset the sign for expression in bracket
                i += 1
                continue
                
            if s[i] == ')':
                tmp = stackSign.pop() * stackNum.pop() 
                stackNum[-1] += tmp
        
                i += 1
                continue
            
            num = 0
            
            while i < len(s) and s[i].isdigit():
                num = num * 10 + int(s[i])
                i += 1
            
            stackNum[-1] += sign * num
        
        return stackSign[-1] * stackNum[-1]

Edited on 09/11/2021. Simplify the stack based solution.