Basic Calculator hard

Problem Statement

Evaluate a string expression representing a basic calculator. The expression contains digits, +, -, (, and ). You can assume the given expression is always valid.

Example 1

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

Example 2

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

Steps

This problem requires handling operator precedence and parentheses. We'll use a stack-based approach to solve it:

1. Initialization: Create two stacks: one for numbers (numStack) and one for operators (opStack). We'll also need a variable sign to track the current sign (+1 or -1).

2. Iteration: Iterate through the input string s:

   • Whitespace: Ignore whitespace characters.
   • Digit: Read consecutive digits to form a number and push it onto numStack after multiplying by the current sign.
   • '+' or '-': Push the current number (with the appropriate sign) onto numStack, update the sign, and continue.
   • '(': Push the current sign and the current value of opStack onto their respective stacks and reset the sign to +1. This handles nested parentheses.
   • ')': While the top of opStack is not '(', pop operators and operands, perform calculations and push the result onto numStack. Then, pop the previous sign and opStack value, restoring the context.

3. Final Calculation: After processing the entire string, perform any remaining operations on the stacks.

Explanation

The stack-based approach simulates the order of operations. The opStack stores pending operations, and parentheses are handled by pushing and popping the state of the stack, ensuring correct precedence. The sign variable efficiently handles the positive or negative sign before each number.

Code

function calculate(s: string): number {
    const numStack: number[] = [];
    const opStack: string[] = [];
    let sign: number = 1;
    let num: number = 0;

    for (let i = 0; i < s.length; i++) {
        const char = s[i];

        if (/\d/.test(char)) {
            num = num * 10 + parseInt(char);
        }

        if (!/\d/.test(char) && char !== ' ' || i === s.length -1) {
            numStack.push(num * sign);
            num = 0;
            sign = 1;
        }

        if (char === '+') {
            
        } else if (char === '-') {
            sign = -1;
        } else if (char === '(') {
            opStack.push(String(sign));
            opStack.push('(');
            sign = 1;
        } else if (char === ')') {
            while (opStack.length > 0 && opStack[opStack.length - 1] !== '(') {
                const op = opStack.pop();
                const num2 = numStack.pop();
                const num1 = numStack.pop();
                numStack.push(op === '+' ? num1 + num2 : num1 - num2);
            }
            opStack.pop(); // Pop the '('
            if(opStack.length > 0){
                sign = parseInt(opStack.pop())
            }
        }
    }

    return numStack.reduce((sum, num) => sum + num, 0);
}

Complexity

• 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, as the stacks can grow up to the size of the input string (e.g., deeply nested parentheses). In the average case, it will be less than O(n).