Solution Explanation: Basic Calculator

This problem requires evaluating a mathematical expression string without using built-in evaluation functions like eval(). The expression can contain digits, '+', '-', '(', ')', and spaces. The solution uses a stack-based approach to handle operator precedence and parentheses.

Approach:

The core idea is to process the expression iteratively, keeping track of the current running total (ans), the current sign (sign), and using a stack to manage nested parentheses.

1. Initialization:

   • ans: Stores the cumulative result. Initialized to 0.
   • sign: Represents the current sign (+1 or -1). Initialized to +1.
   • stk: A stack to store intermediate results and signs when encountering parentheses.

2. Iteration: The code iterates through each character in the input string s.

3. Character Handling:

   • Digit: If a digit is encountered, it forms a number. The code reads consecutive digits to construct the complete number and adds it to ans based on the current sign.
   • '+' or '-': These operators change the sign.
   • '(': This indicates the start of a subexpression. The current ans and sign are pushed onto the stack, and ans and sign are reset to start calculating the subexpression.
   • ')': This indicates the end of a subexpression. The top two elements from the stack are popped: the previous sign and the previous ans. The current ans is multiplied by the popped sign and added to the popped ans, effectively incorporating the subexpression's result into the overall calculation.

Time Complexity: O(n), where n is the length of the input string. The algorithm iterates through the string once.

Space Complexity: O(n) in the worst case. The stack can grow up to the maximum depth of nested parentheses, which could be proportional to the length of the string in the worst case.

Code Examples (Python3):

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        result = 0
        sign = 1  # 1 for +, -1 for -
 
        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 += num * sign  # Add the number with the current sign
            elif s[i] == '+':
                sign = 1
                i += 1
            elif s[i] == '-':
                sign = -1
                i += 1
            elif s[i] == '(':
                stack.append(result)
                stack.append(sign)  # Push the current result and sign onto the stack
                result = 0
                sign = 1
                i += 1
            elif s[i] == ')':
                result *= stack.pop()  # Pop the sign
                result += stack.pop()  # Pop the previous result and add it to current result
                i += 1
            else:  # Skip spaces
                i += 1
        return result
 

The Java, C++, Go, Typescript, and C# examples provided earlier all follow the same fundamental approach and have the same time and space complexity characteristics. They simply differ in syntax and specific library functions used.