Skip to content

227. Basic Calculator II

Intuition

The expression is in infix notation (e.g., "3+2*2"), which needs to respect operator precedence (* and / over + and -). Instead of evaluating directly, we simulate infix-to-postfix conversion and evaluate on the fly using a stack. This helps maintain order and precedence without using built-in eval().

  • Traverse the input string character by character.
  • Build multi-digit numbers.
  • Use a stack to store numbers and apply operators when precedence rules dictate.
  • After traversing the input, apply any remaining operations in the stack.
  • Return the final result from the stack.

Complexity

Space Complexity Time Complexity
$\(\text{O}(n)\)$ $\(\text{O}(n)\)$

Code

// Determines the precedence level of the given operator
int getPrecedence(char operator) {
    if (operator == '*' || operator == '/') return 2;
    else if (operator == '+' || operator == '-') return 1;
    return -1;
}

// Converts infix expression to postfix on-the-fly and evaluates it using stacks
int evaluateInfixExpression(String expression) {
    Stack<Character> operatorStack = new Stack<>();
    Stack<Integer> valueStack = new Stack<>();

    for (int index = 0; index < expression.length(); ++index) {
        char currentChar = expression.charAt(index);

        // Skip whitespace
        if (currentChar == ' ') continue;

        // If it's a digit, parse the full number and evaluate
        if (Character.isDigit(currentChar)) {
            StringBuilder currentNumber = new StringBuilder();
            while (index < expression.length() && Character.isDigit(expression.charAt(index))) {
                currentNumber.append(expression.charAt(index));
                index++;
            }
            index--; // step back to compensate for extra index increment
            evaluateToken(valueStack, currentNumber.toString());
        } else {
            // While there is an operator on the stack with higher or equal precedence, apply it
            while (!operatorStack.isEmpty() && getPrecedence(currentChar) <= getPrecedence(operatorStack.peek())) {
                evaluateToken(valueStack, operatorStack.pop().toString());
            }

            // Push the current operator
            operatorStack.push(currentChar);
        }
    }

    // Apply remaining operators
    while (!operatorStack.isEmpty()) {
        evaluateToken(valueStack, operatorStack.pop().toString());
    }

    // Final result is at the top of the value stack
    return valueStack.peek();
}

// Applies an operation or pushes a number to the stack
void evaluateToken(Stack<Integer> valueStack, String token) {
    if (token.equals("*")) {
        int operand2 = valueStack.pop();
        int operand1 = valueStack.pop();
        valueStack.push(operand1 * operand2);
    } else if (token.equals("/")) {
        int operand2 = valueStack.pop();
        int operand1 = valueStack.pop();
        valueStack.push(operand1 / operand2); // Integer division truncates toward zero
    } else if (token.equals("+")) {
        int operand2 = valueStack.pop();
        int operand1 = valueStack.pop();
        valueStack.push(operand1 + operand2);
    } else if (token.equals("-")) {
        int operand2 = valueStack.pop();
        int operand1 = valueStack.pop();
        valueStack.push(operand1 - operand2);
    } else {
        // Token is a number; convert and push onto the value stack
        valueStack.push(Integer.parseInt(token));
    }
}

// Entry point method
public int calculate(String expression) {
    return evaluateInfixExpression(expression);
}

Comments