Leetcode - Basic Calculator II

Leetcode : Basic Calculator II

Description

Given a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero.

Example 1

Input

 s = "3+2*2"

Ouput

7

Example 2

Input

 s = " 3/2 "

Ouput

1

Example 3

Input

s = " 3+5 / 2 "

Ouput

5

Approach

When manipulating series of string in sequence, stack is an effective data-structure to apply. However, arithmetic sequence must be taken into account (i.e. - multiplication and division occur prior to addition and subtraction)

Solution (Python)

class Solution:
    def calculate(self, s: str) -> int:
        s = s.replace(" ", "")
        
        stack = []
        ops = ["+", "-", "*", "/"]
        
        op = "+"
        temp = 0 
        
        for i in range(len(s)):
            curr = s[i]
            
            if curr not in ops:
                temp = temp * 10 + int(curr)
            if curr in ops or i == len(s) - 1:
                if op == "+":
                    stack.append(temp)
                elif op == "-":
                    stack.append(-temp)
                elif op == "*":
                    temp = temp * stack.pop()
                    stack.append(temp)
                else:
                    div = stack.pop()
                    
                    if div > 0:
                        stack.append(div // temp)
                    else:
                        stack.append(-1 * (-div // temp))
            
                op = curr
                temp = 0 
                
        return sum(stack)

Result

Runtime : 84ms
Memory Usage : 15.7MB
Runtime Beats 69.08% of Python Submission