logoNEURAL COOK
SearchAll PostsTagsNotesAuthor
logoNEURAL COOK

A posts created with Next.js and Tailwind.css

Explore

  • All posts
  • Notes
  • Snippets
  • Tags
  • RSS feed

Connect

instagramtwitterfacebookyoutubelinkedinmailgithub

© 2026 VIKI. All rights reserved.

Built with
Contents
Table Of Contents
2. Add Two Numbers3. Longest Substring Without Repeating Characters5. Longest Palindromic Substring8. String to Integer (atoi)11. Container With Most Water15. 3Sum17. Letter Combinations of a Phone Number19. Remove Nth Node From End of List22. Generate Parentheses33. Search in Rotated Sorted Array34. Find First and Last Position of Element in Sorted Array48. Rotate Image49. Group Anagrams50. Pow(x, n)53. Maximum Subarray54. Spiral Matrix56. Merge Intervals61. Rotate List73. Set Matrix Zeroes74. Search a 2D Matrix75. Sort Colors78. Subsets137. Single Number II138. Copy List with Random Pointer150. Evaluate Reverse Polish Notation151. Reverse Words in a String153. Find Minimum in Rotated Sorted Array155. Min Stack162. Find Peak Element169. Majority Element198. House Robber207. Course Schedule215. Kth Largest Element in an Array227. Basic Calculator II236. Lowest Common Ancestor of a Binary Tree237. Delete Node in a Linked List238. Product of Array Except Self451. Sort Characters By Frequency540. Single Element in a Sorted Array560. Subarray Sum Equals K636. Exclusive Time of Functions875. Koko Eating Bananas1011. Capacity To Ship Packages Within D Days1101. The Earliest Moment When Everyone Become Friends1283. Find the Smallest Divisor Given a Threshold2140. Solving Questions With Brainpower3169. Count Days Without Meetings3481. Apply Substitutions
Code Scratch/leetcode/medium

227. Basic Calculator II

2 min read
On this pageIntuition
IntuitionComplexityCode

# 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 ComplexityTime Complexity
O(n)\text{O}(n)O(n)O(n)\text{O}(n)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&lt;Character&gt; operatorStack = new Stack<>();
    Stack&lt;Integer&gt; valueStack = new Stack<>();
 
    for (int index = 0; index &lt; 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&gt; 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);
}
 
←Previous215. Kth Largest Element in an ArrayNext→236. Lowest Common Ancestor of a Binary Tree

On this page

IntuitionComplexityCode