Basic Calculator II medium

Problem Statement

Evaluate a given arithmetic expression containing +, -, *, and / operators. The expression is given as a string, and you should follow the standard order of operations (PEMDAS/BODMAS), where multiplication and division have higher precedence than 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. Handle Whitespace: Remove leading and trailing whitespace from the input string.

2. Split into Tokens: Split the string into tokens (numbers and operators). We'll use a Stringtokenizer for simplicity. Alternatively, you could iterate character by character.

3. Two-Stack Approach: We'll use two stacks: one for numbers (numStack) and one for operators (opStack).

4. Iteration: Iterate through the tokens.

   • If a token is a number, push it onto numStack.
   • If a token is an operator:
     • While opStack is not empty and the precedence of the current operator is less than or equal to the precedence of the top operator in opStack, perform the operation using the top two numbers from numStack and push the result back onto numStack. Then, pop the operator from opStack.
     • Push the current operator onto opStack.

5. Final Calculations: After iterating through all tokens, perform any remaining operations in opStack.

6. Result: The final result will be the top element of numStack.

Explanation

The two-stack approach mimics the order of operations. Higher precedence operators are processed first because they're pushed onto the opStack earlier and will be processed before lower-precedence operators during the iterative evaluation. The use of a stack ensures that the operations are performed in the correct order - last in, first out (LIFO). Integer division is handled naturally in Java.

Code

import java.util.Stack;
import java.util.StringTokenizer;

class Solution {
    public int calculate(String s) {
        s = s.trim(); //remove leading/trailing whitespace
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> opStack = new Stack<>();
        StringTokenizer st = new StringTokenizer(s, "+-*/ ", true); //tokenize with spaces
        
        while (st.hasMoreTokens()) {
            String token = st.nextToken();
            if (Character.isDigit(token.charAt(0))) {
                numStack.push(Integer.parseInt(token));
            } else if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
                while (!opStack.isEmpty() && precedence(token.charAt(0)) <= precedence(opStack.peek())) {
                    numStack.push(performOp(numStack.pop(), numStack.pop(), opStack.pop()));
                }
                opStack.push(token.charAt(0));
            }
        }
        while (!opStack.isEmpty()) {
            numStack.push(performOp(numStack.pop(), numStack.pop(), opStack.pop()));
        }
        return numStack.pop();
    }

    private int precedence(char op) {
        if (op == '+' || op == '-') return 1;
        return 2; // * or /
    }

    private int performOp(int b, int a, char op) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return a / b; //integer division
            default: return 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, which occurs if the input string has only operators, resulting in n elements in the stacks. In most cases the space complexity would be much less than O(n).