0224-basic-calculator

Try it on leetcode

Description

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

 

Example 1:

Input: s = "1 + 1"
Output: 2

Example 2:

Input: s = " 2-1 + 2 "
Output: 3

Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

 

Constraints:

  • 1 <= s.length <= 3 * 105
  • s consists of digits, '+', '-', '(', ')', and ' '.
  • s represents a valid expression.
  • '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
  • '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
  • There will be no two consecutive operators in the input.
  • Every number and running calculation will fit in a signed 32-bit integer.

Solution(Python)

class Solution:
    def calculate(self, s: str) -> int:
        # num , output, sign , stack
        # 123 ;   nums = 10* num + token
        # +,- ; res += (sign * num) ; num = 0 ; sign = token
        # ( ; stack = [sign, num]
        # ) ; sign = stack.pop(); num = st.pop(),  res += (sign * num) ;    num = 0 ; sign = token
        # skip spaces
        # 22 +  (1 + 2 -3) + (3-22) = 5
        # 2
        #  num = 2
        #  out = 0
        #  sign = +1
        #   stack = []
        # 2; num = 22
        # +;  sign = +1 ; out = 22; num = 0
        # (; stack = [+1, 0]
        # 1; num = 1
        # + ; sign = + 1 out = 23, num = 0
        # 2 ; num = 2
        # -; out = 25; num = 0; sign = -1
        # 3; out = 22; 
        
        num , out , sign, stk = 0,0,1,[]

        for token in s:
            if not token:
                continue
            
            if token.isdigit():
                num = (10 * num) + int(token)
            elif token in  "+-":
                out  += (sign * num)
                num = 0
                sign = -1 if token == "-" else 1 
            elif token == "(":
                stk.append(out)
                stk.append(sign)
                out = 0
                sign = 1
            elif token == ")":
                out += (sign * num) 
                num = 0
                out *= stk.pop()
                out += stk.pop()

        return out + (num * sign)

Dry Run