Basic Calculator II (No Parentheses)

📋

Problem

Imagine building a simple calculator app that can evaluate expressions with addition, subtraction, multiplication, and division, but without parentheses. How do you correctly compute the result respecting operator precedence?

Given a string s which represents a valid arithmetic expression containing non-negative integers, '+', '-', '*', and '/' operators, evaluate the expression and return the integer result. The integer division should truncate toward zero. The expression does not contain any parentheses and is guaranteed to be valid.

1 ≤ s.length ≤ 10^5s consists of digits, '+', '-', '*', '/', and spaces ' ' only.The integer division should truncate toward zero.The expression is always valid.

Edge cases: Expression with only one number → returns that numberExpression with spaces between every character → correct parsingDivision by 1 → returns the original number

</>

IDE

def calculate(s: str) -> int:public int calculate(String s)int calculate(string s)function calculate(s)

def calculate(s: str) -> int:
    # Write your solution here
    pass

class Solution {
    public int calculate(String s) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int calculate(string s) {
    // Write your solution here
    return 0;
}

function calculate(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Incorrect sum ignoring precedence (e.g., 9 instead of 7 for '3+2*2')Evaluating expression strictly left to right without operator precedence.✅ Implement stack-based evaluation applying multiplication and division immediately before addition and subtraction.

Wrong: Wrong division result due to flooring instead of truncation (e.g., 1 instead of 2 for '5/2')Using floor division or incorrect integer division that does not truncate toward zero.✅ Use int() cast or equivalent truncation toward zero for division results.

Wrong: Fails on expressions with spaces (e.g., parsing error or wrong output)Not removing or ignoring spaces before parsing tokens.✅ Preprocess input string to remove spaces before evaluation.

Wrong: Fails single number input (e.g., returns 0 or error for '42')Expecting operators or stack usage even when expression is a single number.✅ Return parsed integer directly if no operators are present.

Wrong: TLE on large inputUsing nested loops or brute force approach with exponential or quadratic complexity.✅ Implement O(n) stack-based algorithm processing input in one pass.

✓

Test Cases

Focus on parsing and handling edge cases like single numbers and spaces.

Ensure your operator precedence logic is correct and handles chained operations.

Optimize your solution to run in linear time using a stack or similar approach.

t1_01basic

Input{"s":"3+2*2"}

Expected7

⏱ Performance - must finish in 2000ms

Multiplication has higher precedence, so 2*2=4, then 3+4=7.

💡 Consider operator precedence: multiplication and division before addition and subtraction.

💡 Use a stack to defer addition and subtraction until multiplication and division are resolved.

💡 Push numbers onto a stack and apply multiplication/division immediately; sum stack at end.

Why it failed: Incorrect result likely due to ignoring operator precedence or incorrect division truncation. Fix by applying multiplication/division immediately and truncating division toward zero.

✓ Correctly respects operator precedence and truncates division toward zero.

t1_02basic

Input{"s":" 3+5 / 2 "}

Expected5

⏱ Performance - must finish in 2000ms

5/2 truncates toward zero to 2, then 3+2=5.

💡 Trim spaces and parse numbers and operators carefully.

💡 Division should truncate toward zero, not floor or ceil.

💡 Apply division immediately and then add or subtract deferred values.

Why it failed: Wrong output due to incorrect parsing of spaces or wrong division truncation. Fix by removing spaces and using int truncation toward zero for division.

✓ Correctly parses spaces and truncates division toward zero.

t2_01edge

Input{"s":"42"}

Expected42

⏱ Performance - must finish in 2000ms

Expression with only one number returns that number.

💡 Check if expression contains only digits without operators.

💡 Return the parsed integer directly if no operators present.

💡 Avoid stack operations if expression is a single number.

Why it failed: Fails single number input by expecting operators or stack usage. Fix by returning parsed integer if no operators found.

✓ Handles single number expressions correctly.

t2_02edge

Input{"s":" 1 + 1 + 1 + 1 "}

Expected4

⏱ Performance - must finish in 2000ms

Expression with spaces between every character parses correctly and sums to 4.

💡 Remove or ignore spaces before processing.

💡 Parse tokens carefully to separate numbers and operators.

💡 Use a loop that skips spaces or preprocess string to remove spaces.

Why it failed: Fails due to incorrect parsing of spaces causing wrong tokens. Fix by removing spaces before parsing.

✓ Correctly parses expressions with spaces between characters.

t2_03edge

Input{"s":"8/1"}

Expected8

⏱ Performance - must finish in 2000ms

Division by 1 returns the original number.

💡 Division by 1 should not change the number.

💡 Ensure division truncation logic handles divisor=1 correctly.

💡 Check division operator implementation for edge divisors.

Why it failed: Incorrect output due to division implementation error or truncation bug. Fix by using int truncation toward zero for division.

✓ Division by 1 handled correctly.

t3_01corner

Input{"s":"14-3/2"}

Expected13

⏱ Performance - must finish in 2000ms

3/2 truncates to 1, so 14-1=13. Tests correct precedence and truncation.

💡 Beware of evaluating left to right ignoring precedence.

💡 Multiplication and division must be evaluated before addition and subtraction.

💡 Apply division truncation toward zero and then subtract.

Why it failed: Fails due to left-to-right evaluation ignoring precedence, resulting in wrong subtraction. Fix by applying multiplication/division before addition/subtraction.

✓ Correctly applies operator precedence and truncation.

t3_02corner

Input{"s":"2*3+4"}

Expected10

⏱ Performance - must finish in 2000ms

2*3=6 plus 4 equals 10. Tests correct multiplication before addition.

💡 Check if multiplication is applied immediately rather than deferred.

💡 Use a stack to hold intermediate results for addition/subtraction.

💡 Push multiplied result onto stack before summing.

Why it failed: Fails by adding before multiplying, ignoring precedence. Fix by applying multiplication immediately and deferring addition.

✓ Correctly handles multiplication before addition.

t3_03corner

Input{"s":"3+5/2*2-1"}

Expected6

⏱ Performance - must finish in 2000ms

5/2 truncates to 2, 2*2=4, expression is 3+4-1=6. Tests chained multiplication/division and addition/subtraction.

💡 Beware of mixing multiplication and division precedence and order.

💡 Evaluate multiplication and division left to right before addition/subtraction.

💡 Apply each multiplication/division immediately and update stack accordingly.

Why it failed: Fails by incorrect order of multiplication/division or wrong truncation. Fix by evaluating * and / left to right with truncation before + and -.

✓ Correctly evaluates chained multiplication and division with truncation.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100000, O(n) time complexity required to complete within 2 seconds.

💡 Use a single pass stack-based algorithm with O(n) time complexity.

💡 Avoid nested loops or recursion that cause O(n^2) or worse.

💡 Process characters sequentially and apply operations immediately.

Why it failed: TLE due to O(n^2) or exponential complexity from nested loops or brute force. Fix by implementing O(n) stack-based solution.

✓ Algorithm runs in O(n) time and passes performance constraints.

Practice

1. You receive a continuous stream of lowercase letters and need to report the first character that appears exactly once at each step. Which approach guarantees an optimal O(n) time solution with constant space for this problem?

easy

A. Use a dynamic programming approach to store subproblems of unique characters at each prefix of the stream.

B. Use a brute force scan of the entire stream so far to find the first unique character after each new letter.

C. Maintain a fixed-size frequency array for all lowercase letters and a queue to track potential unique characters, updating both as new letters arrive.

D. Use a greedy approach that picks the first character that hasn't appeared before without tracking frequencies.

Solution

1. Step 1: Understand problem constraints

   The stream consists of lowercase letters only, so a fixed-size frequency array of length 26 suffices.

2. Step 2: Identify optimal approach

   Using a frequency array plus a queue to track candidates for first unique character allows O(1) updates per character and O(n) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Frequency array + queue approach is standard for this problem [OK]

Hint: Frequency array + queue yields O(n) time and O(1) space [OK]

Common Mistakes:

• Thinking brute force scanning is efficient enough
• Assuming DP applies here
• Using greedy without frequency tracking

2. Consider the following Python code implementing the optimized next greater element algorithm. What is the final output when calling nextGreaterElement([4,1,2], [1,3,4,2])?

easy

A. [-1, -1, 3]

B. [-1, 3, -1]

C. [3, -1, -1]

D. [3, 4, -1]

Solution

1. Step 1: Trace stack and map updates for nums2

   Process nums2: push 1, then 3 > 1 so pop 1 -> map[1]=3; push 3; 4 > 3 pop 3 -> map[3]=4; push 4; 2 < 4 push 2. Stack ends with [4,2].

2. Step 2: Assign -1 for remaining stack elements and build result

   Pop 2 -> map[2]=-1; pop 4 -> map[4]=-1. Result for nums1=[4,1,2] is [map[4], map[1], map[2]] = [-1,3,-1].

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Matches expected output from code comments and manual trace [OK]

Hint: Stack pops smaller elements when a bigger one arrives [OK]

Common Mistakes:

• Confusing order of popping leading to wrong map values
• Forgetting to assign -1 for elements with no next greater
• Mixing up indices when building the final result

3. Consider the following buggy code for asteroid collision. Which line contains the subtle bug that causes incorrect behavior on equal size asteroids?

def asteroidCollision(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        while alive and stack and stack[-1] > 0 and a < 0:
            if stack[-1] < -a:
                stack.pop()
            elif stack[-1] == -a:
                alive = False
            else:
                alive = False
        if alive:
            stack.append(a)
    return stack

medium

A. Line with 'stack.pop()' inside 'if stack[-1] < -a:'

B. Line with 'while alive and stack and stack[-1] > 0 and a < 0:' condition

C. Line with 'alive = False' inside 'elif stack[-1] == -a:'

D. Line with 'stack.append(a)' after the while loop

Solution

1. Step 1: Identify behavior on equal size asteroids

   When sizes are equal, both asteroids should explode (pop from stack and not append current).

2. Step 2: Check code for equal size case

   In the buggy code, stack.pop() is missing when sizes are equal, so the top asteroid remains incorrectly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing stack.pop() causes incorrect survival of equal asteroid [OK]

Hint: Equal size asteroids both must be removed [OK]

Common Mistakes:

• Forgetting to pop stack on equal size
• Appending asteroid after it exploded
• Incorrect while loop condition

4. What is the time complexity of the optimal monotonic stack algorithm for finding the previous smaller element in an array of size n, and why might some candidates mistakenly think it is higher?

medium

A. O(n) because each element is pushed and popped at most once from the stack

B. O(n^2) because each element can be compared with all previous elements in worst case

C. O(n log n) due to repeated stack operations resembling binary search

D. O(n) but with O(n^2) auxiliary space due to storing intermediate results

Solution

1. Step 1: Identify the operations per element

   Each element is pushed once and popped at most once from the stack, so total stack operations are O(n).

2. Step 2: Understand why O(n^2) is a common misconception

   Nested loops in brute force suggest O(n^2), but monotonic stack avoids repeated comparisons by popping larger elements immediately.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Stack operations linear in n, no nested iteration causing quadratic time [OK]

Hint: Each element pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Confusing brute force nested loops with stack approach
• Assuming stack operations cost log n each
• Forgetting stack pops amortize total cost

5. Suppose the histogram bars can be reused multiple times (i.e., you can select the same bar multiple times consecutively to form a rectangle). Which modification to the monotonic stack approach correctly computes the largest rectangle area under this new condition?

hard

A. Switch to a dynamic programming approach that considers repeated bars and their cumulative widths

B. Use the same monotonic stack approach but multiply the height by the count of consecutive bars instead of width

C. Modify the stack to store counts of consecutive bars and update boundaries accordingly

D. No modification needed; the original monotonic stack approach already handles reuse

Solution

1. Step 1: Understand reuse changes problem nature

   Reusing bars means rectangles can extend beyond original boundaries, invalidating monotonic stack assumptions.

2. Step 2: Identify suitable approach

   Dynamic programming can track cumulative widths and heights considering reuse, unlike monotonic stack which assumes unique bars.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack does not handle repeated bar reuse correctly [OK]

Hint: Reuse breaks monotonic stack assumptions; DP needed [OK]

Common Mistakes:

• Assuming monotonic stack handles reuse without changes
• Trying to fix stack by storing counts only