Basic Calculator

Problem 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().

Examples:

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

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

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

Naive Approach

A naive approach would be to try to directly parse the string and perform calculations as we encounter operators and numbers. However, this becomes complex with parentheses and operator precedence. Using eval() is obviously not allowed. Thus, this makes this problem quite tricky.

Optimal Approach: Stack-Based Solution

The most efficient way to solve this is using a stack. The stack will help us keep track of the sign and intermediate results when we encounter parentheses. Here's how the algorithm works:

1. Iterate through the string character by character.
2. If the character is a digit, construct the number.
3. If the character is + or -, update the sign.
4. If the character is (, push the current result and sign onto the stack and reset the result and sign for the subexpression.
5. If the character is ), pop the sign and previous result from the stack and use them to calculate the result of the subexpression.

Edge Cases

• Empty string
• String with only spaces
• String starting with a negative sign
• Nested parentheses
• Consecutive operators (not allowed by constraints, but good to consider)
• Large numbers that could cause integer overflow (handled by constraint saying everything fits in a 32-bit signed int.)

Code (Python)

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        result = 0
        sign = 1
        i = 0
        while i < len(s):
            if s[i].isdigit():
                num = 0
                while i < len(s) and s[i].isdigit():
                    num = num * 10 + int(s[i])
                    i += 1
                result += sign * num
                i -= 1 # Correct the index after the inner loop
            elif s[i] == '+':
                sign = 1
            elif s[i] == '-':
                sign = -1
            elif s[i] == '(':                
                stack.append(result)
                stack.append(sign)
                result = 0
                sign = 1
            elif s[i] == ')':
                result = stack.pop() * result + stack.pop()  # sign * result + prev_result
            i += 1
        return result

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the string s. We iterate through the string once.
• Space Complexity: O(n) in the worst case, where n is the depth of nested parentheses. This is because, in the worst case, we might push all the intermediate results and signs onto the stack.