Basic Calculator II medium

Problem Statement

Evaluate a mathematical expression represented as a string, containing only non-negative integers, +, -, *, and /. The expression should be evaluated in the order of operations, with multiplication and division having precedence over addition and subtraction.

Example 1

Input: "3+2*2" Output: 7 Explanation: 3 + (2 * 2) = 7

Example 2

Input: " 3/2 " Output: 1 Explanation: 3 / 2 = 1 (integer division)

Steps

1. Tokenize the input string: Split the string into an array of numbers and operators. Handle spaces appropriately.
2. Operator Precedence: Implement operator precedence using a stack-based approach or a two-pass algorithm. We'll use a stack approach here.
3. Evaluation: Process the tokens from left to right. When we encounter a number, push it onto the stack. When we encounter an operator:
   • If the operator has higher precedence than the previous operator (or if the stack is empty), push it onto an operator stack.
   • If the operator has lower precedence than the previous operator (or the top of the operator stack), pop the top operator and the top two operands from the number stack, perform the operation, and push the result back onto the number stack. Repeat until precedence is handled correctly.
4. Final Result: After processing all tokens, the top (and only) element of the number stack will be the result.

Explanation

The solution uses two stacks: one for numbers (numStack) and one for operators (opStack). The precedence function determines the order of operations. We iterate through the tokens:

• Numbers are pushed onto numStack.
• Operators are handled according to precedence. If the current operator's precedence is greater than or equal to the top of opStack, it's pushed onto opStack. Otherwise, we perform the operation using the top two numbers and operator from their respective stacks. This ensures higher precedence operations are performed first.
• Finally, the remaining operations are performed to obtain the final result.

Code

function calculate(s: string): number {
    s = s.trim(); //Remove leading/trailing spaces
    const numStack: number[] = [];
    const opStack: string[] = [];
    let num: string = "";
    const precedence: { [key: string]: number } = { '+': 1, '-': 1, '*': 2, '/': 2 };

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

        if (/[0-9]/.test(char)) {
            num += char;
        }

        if (!/[0-9]/.test(char) && char !== ' ' || i === s.length -1) { //Number ends or last char
          if(num){
            numStack.push(parseInt(num));
            num = "";
          }
          if(char === ' '){
              continue;
          }
          if (opStack.length === 0 || precedence[char] >= precedence[opStack[opStack.length - 1]]) {
              opStack.push(char);
          } else {
              while (opStack.length > 0 && precedence[char] < precedence[opStack[opStack.length - 1]]) {
                  const op = opStack.pop()!;
                  const num2 = numStack.pop()!;
                  const num1 = numStack.pop()!;
                  const result = performOperation(num1, num2, op);
                  numStack.push(result);
              }
              opStack.push(char);
          }
        }
    }

    while (opStack.length > 0) {
        const op = opStack.pop()!;
        const num2 = numStack.pop()!;
        const num1 = numStack.pop()!;
        const result = performOperation(num1, num2, op);
        numStack.push(result);
    }

    return numStack[0];
}


function performOperation(num1: number, num2: number, op: string): number {
    switch (op) {
        case '+': return num1 + num2;
        case '-': return num1 - num2;
        case '*': return num1 * num2;
        case '/': return Math.trunc(num1 / num2); // Integer division
        default: throw new Error("Invalid operator");
    }
}

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, to store the stacks. The space complexity is proportional to the number of operators and operands in the expression. In the best case (e.g., a simple addition), the space complexity will be smaller.