227.Basic_Calculator_II(Medium).md

227. Basic Calculator II (Medium)

Date and Time: Nov 22, 2024, 13:11 (EST)

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

Question:

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2^31, 2^31 - 1].

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

Example 1:

Input: s = "3+2*2"

Output: 7

Example 2:

Input: s = " 3/2 "

Output: 1

Example 3:

Input: s = " 3+5 / 2 "

Output: 5

Constraints:

• 1 <= s.length <= 3 * 10^5

• s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.

• s represents a valid expression.

• All the integers in the expression are non-negative integers in the range [0, 2^31 - 1].

• The answer is guaranteed to fit in a 32-bit integer.

Walk-through:

1. We use stack[] to keep track of all previous result. Use sign to keep track of the previou sign.

2. We only append new element into stack[] when we encounter a new operator. For '+', '-' signs, we just append either num or -num into stack. When we have '*', '/' signs, we need to pop the previous result from stack[] then perform the operation with num and append the result to stack[].

3. Lastly, we return the sum of all elements with sign from stack.

Note: we use int(-3/2) to handle the case of integer division.

Python Solution:

class Solution:
    def calculate(self, s: str) -> int:
        # For each num, we check sign, and perform corresponding operation
        # if sign = +, append (+num) into stack
        # if sign == -, append(-num) into stack
        # if sign = *, pop the prev, append(prev * num) into stack
        # if sign = /, pop the prev, append(prev // num) into stack
        # return the sum of stack

        # TC: O(n), n = len(s), SC: O(n)
        num, sign, stack = 0, "+", []
        for char in s + "+":
            if char.isdigit():
                num = num * 10 + int(char)
            elif char in '+-*/':
                # Update stack with sign and num for each operation
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    stack.append(-num)
                elif sign == '*':
                    prev = stack.pop()
                    stack.append(prev * num)
                elif sign == '/':
                    prev = stack.pop()
                    stack.append(int(prev / num))
                # Update sign and num
                sign = char
                num = 0
        return sum(stack)

Time Complexity: $O(n)$
Space Complexity: $O(n)$