Basic Calculator hard

Problem Statement

Evaluate a given string expression representing a basic calculator. The expression consists of digits, '+', '-', '(', ')', and spaces. The expression should be evaluated to return the integer result.

Example 1

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

Example 2

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

Steps to Solve

1. Handle Parentheses: We'll use a stack to handle nested parentheses. When we encounter an opening parenthesis '(', we push the current state (current number and sign) onto the stack. When we encounter a closing parenthesis ')', we pop the state from the stack and continue the calculation.

2. Track Sign and Number: We maintain a variable sign to track the current sign (+ or -). Initially, the sign is positive. We also maintain a variable num to accumulate the current number.

3. Iteration: We iterate through the string. If we encounter a digit, we accumulate it to num. If we encounter a '+', '-', or ')', we process the current num with the current sign and then update the sign and reset num. For '(' we push the current state onto the stack.

4. Stack Operations: When we encounter a ')', we pop the state from the stack. We calculate the result of the expression within the parentheses.

5. Final Result: After iterating through the entire string, the accumulated value will be the final result.

Explanation

The solution utilizes a stack to handle the nested parentheses. The sign variable cleverly tracks whether the next number should be added or subtracted. The algorithm efficiently parses the expression, handling digits, operators, and parentheses in a structured manner. The stack allows for a recursive-like evaluation of nested expressions without explicit recursion, improving efficiency and managing memory effectively.

Code (Java)

import java.util.Stack;

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int sign = 1; // 1 for +, -1 for -
        int num = 0;
        int result = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                result += sign * num;
                num = 0;
                sign = 1;
            } else if (c == '-') {
                result += sign * num;
                num = 0;
                sign = -1;
            } else if (c == '(') {
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1; //reset sign for inner parentheses
            } else if (c == ')') {
                result += sign * num;
                num = 0;
                result *= stack.pop(); // Apply sign from outer scope
                result += stack.pop(); // Add the result from outer scope
            }
        }
        result += sign * num; // Add the last number
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n), where n is the length of the input string. We iterate through the string once.
• Space Complexity: O(n) in the worst case, due to the stack. The stack's size can grow proportionally to the depth of nested parentheses in the expression. In the best case (no parentheses) space complexity is O(1).