224.Basic_Calculator(Hard).md

224. Basic Calculator (Hard)

Date and Time: Oct 12, 2024, 11:28 (EST)

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

Question:

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 * 10^5

• 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.

Walk-through:

For each operation, we save the previous operation into three variables, then when we have a new operation, we update res with the previous operation with sign, num.

1. Use three variables num, sign, res to keep track of values, and stack[] for "(".

2. Four cases to consider:

   i. when i.isdigit(), we want to add this number to num since this variable keep track of a number before any operation, and we also need to consider a case that a number has more than one digit (23).

   ii. when i in "+-", we need to first update res += sign * num (process the operation before this new operation from sign, num), then we change the sign to be -1 or 1 depends on i == "-" or not, and we need to reset num = 0, so we can take next number into num.

   iii. when i == "(", we need to append stack[res, sign] into stack, so after we process all the operations within (), we can add or subtract the previous res.

   iv. when i == ")", we can pop res, sign from stack[] and update res accordingly. Lastly, reset num = 0 so we can retake new value into res.

3. Finally, return res + sign * num just in case we have cases like s = "1 + 1".

Python Solution:

class Solution:
    def calculate(self, s: str) -> int:
        # use res, sign, curr to keep track of current operation
        # When we encounter a new sign, update res with prev operation, then update sign
        # When encounter "(", save res, sign, into stack[], reset all variables
        # When encounter ")", update the last operation result, pop sign, res from stack[], then reset variables

        # TC: O(n), n = len(s), SC: O(n)
        stack = []
        res, sign, curr = 0, 1, 0
        for i in s:
            if i.isdigit():
                curr = curr * 10 + int(i)
            elif i in "+-":
                res += sign * curr
                sign = 1 if i == '+' else -1
                curr = 0
            elif i == "(":
                stack.append(res)
                stack.append(sign)
                res, sign, curr = 0, 1, 0
            elif i == ")":
                res += sign * curr
                res *= stack.pop()
                res += stack.pop()
                sign, curr = 1, 0
        return res + sign * curr

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