Basic Calculator (With Parentheses)

📋

Problem

Imagine building a simple calculator app that can handle addition, subtraction, and nested parentheses, just like a real calculator on your phone.

Given a string s representing a valid arithmetic expression containing digits, '+', '-', '(', ')', and spaces, implement a basic calculator to evaluate it and return the result as an integer. The expression is guaranteed to be valid and may contain nested parentheses.

1 ≤ s.length ≤ 10^5s consists of digits, '+', '-', '(', ')', and ' ' (space) characters.The expression is always valid.No multiplication or division operators are present.

Edge cases: "" (empty string) → 0"(1)" → 1"- (3 + (4 + 5))" → -12

</>

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: 0 for empty string inputCode crashes or returns default zero without checking empty input explicitly.✅ Add a condition to return 0 immediately if input string is empty.

Wrong: Incorrect sign application for nested parentheses, e.g. returning positive instead of negativeNot pushing and popping sign stack correctly when encountering '(' and ')'.✅ Use a stack to track cumulative signs and apply them after evaluating inner parentheses.

Wrong: Wrong result for unary minus expressions like '1 + -2'Failing to distinguish unary minus from binary minus during parsing.✅ Check if '-' is followed by a digit and treat as unary minus by parsing negative number.

Wrong: Integer overflow or wrong parsing for large numbers like 2147483647Using 32-bit int without care or incorrect parsing logic.✅ Use 64-bit integer or Python's arbitrary precision int to parse large numbers safely.

Wrong: Timeout on large inputRecursive parsing or repeated string slicing causing O(n^2) or worse complexity.✅ Implement iterative stack-based parsing with O(n) time complexity.

✓

Test Cases

Focus on handling base cases like empty strings and single numbers inside parentheses.

Pay attention to nested parentheses and sign propagation through multiple layers.

Optimize your solution to run in linear time using iterative stack-based parsing.

t1_01basic

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

Expected2

⏱ Performance - must finish in 2000ms

Simple addition without parentheses: 1 + 1 = 2

💡 Focus on parsing digits and handling '+' and '-' operators.

💡 Use a stack to manage signs and evaluate expressions inside parentheses.

💡 Accumulate numbers and apply signs immediately; handle '(' by pushing current result and sign.

Why it failed: Incorrect result likely due to ignoring spaces or not handling '+' and '-' signs properly. Fix by trimming spaces and applying sign changes correctly.

✓ Basic addition parsed and evaluated correctly.

t1_02basic

Input{"s":"(2 + 3) - 4"}

Expected1

⏱ Performance - must finish in 2000ms

Expression with parentheses: (2 + 3) - 4 = 5 - 4 = 1

💡 Parentheses change the evaluation order; use a stack to save state before '(' and restore after ')'.

💡 Push current result and sign before '('; pop and combine after ')'.

💡 Ensure signs outside parentheses are applied to the entire parenthesized expression.

Why it failed: Failed to correctly apply sign outside parentheses or to restore previous state after ')'. Fix by pushing and popping result and sign stacks properly.

✓ Parentheses handled correctly with proper sign application.

t2_01edge

Input{"s":""}

Expected0

⏱ Performance - must finish in 2000ms

Empty string input should return 0 as no expression to evaluate.

💡 Check how your code handles empty input or strings with no digits.

💡 Return 0 if no numbers are found or input is empty.

💡 Initialize result to 0 and handle empty input as a special case.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a check for empty string and returning 0 immediately.

✓ Empty input handled gracefully returning 0.

t2_02edge

Input{"s":"(1)"}

Expected1

⏱ Performance - must finish in 2000ms

Single number inside parentheses should evaluate to that number.

💡 Parentheses may enclose a single number; ensure this is handled correctly.

💡 When encountering '(', push current state; on ')', pop and combine.

💡 Do not ignore numbers inside parentheses even if alone.

Why it failed: Fails to return number inside parentheses correctly, possibly skipping single numbers. Fix by correctly processing numbers inside parentheses before returning.

✓ Single number inside parentheses evaluated correctly.

t2_03edge

Input{"s":"- (3 + (4 + 5))"}

Expected-12

⏱ Performance - must finish in 2000ms

Nested parentheses with leading negative sign: -(3 + (4 + 5)) = -12

💡 Leading '-' before parentheses applies to entire expression inside.

💡 Use stack to track signs and apply them correctly to nested expressions.

💡 Ensure sign is applied after evaluating inner parentheses.

Why it failed: Incorrect sign application for nested parentheses with leading '-'. Fix by pushing sign before '(' and applying it after evaluating inner expression.

✓ Nested parentheses with leading negative sign handled correctly.

t3_01corner

Input{"s":"1 - (2 - (3 - (4 + 5)))"}

Expected-7

⏱ Performance - must finish in 2000ms

Complex nested parentheses with alternating signs: 1 - (2 - (3 - (4 + 5))) = 1

💡 Nested parentheses can flip signs multiple times; track sign stack carefully.

💡 Each '(' pushes current sign; each ')' pops it, combining with current sign.

💡 Avoid greedy evaluation; process fully nested expressions before applying outer signs.

Why it failed: Greedy or partial evaluation leads to wrong sign application in nested parentheses. Fix by using a stack to track cumulative signs and apply after full evaluation.

✓ Correctly handles multiple nested parentheses with alternating signs.

t3_02corner

Input{"s":"2147483647"}

Expected2147483647

⏱ Performance - must finish in 2000ms

Maximum 32-bit integer value as input should be parsed correctly.

💡 Handle large numbers without overflow or truncation.

💡 Parse digits into integer carefully, avoiding integer overflow in intermediate steps.

💡 Use appropriate data type to store large numbers during parsing.

Why it failed: Integer overflow or incorrect parsing of large numbers. Fix by using 64-bit integer type or Python int which is unbounded.

✓ Large integer parsed and returned correctly.

t3_03corner

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

Expected-1

⏱ Performance - must finish in 2000ms

Expression with unary minus after plus: 1 + -2 = -1

💡 Handle unary minus correctly when it appears after '+' or '-' operators.

💡 Distinguish between binary and unary minus during parsing.

💡 Treat '-' followed by a digit as negative number, not subtraction operator.

Why it failed: Fails to parse unary minus correctly, treating '-2' as subtraction instead of negative number. Fix by checking if '-' is unary and parsing number accordingly.

✓ Unary minus after plus handled correctly.

t4_01performance

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

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100000, must complete in O(n) time within 2 seconds.

💡 Use a stack-based iterative approach for O(n) time complexity.

💡 Avoid recursive parsing or repeated string slicing to prevent TLE.

💡 Process characters in a single pass with constant time stack operations.

Why it failed: TLE due to exponential or quadratic time complexity from recursive parsing or repeated string operations. Fix by implementing iterative stack-based parsing with O(n) complexity.

✓ Efficient O(n) stack-based parsing confirmed.

Practice

1. Consider the following Python code implementing the optimal 132 pattern detection algorithm. What is the return value when the input is [3, 1, 4, 2]?

easy

A. None

B. False

C. Raises an error

D. True

Solution

1. Step 1: Trace the loop with input [3,1,4,2]

   Iterate reversed: 2,4,1,3. Initially, stack=[], third=-inf. - num=2: stack empty, append 2. - num=4: stack top 2 < 4, pop 2, third=2, append 4. - num=1: 1 < third(2), return True.

2. Step 2: Confirm early return

   At num=1, condition triggers return True, so output is True.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Early return on detecting 132 pattern confirmed [OK]

Hint: Early return when num < third triggers True [OK]

Common Mistakes:

• Confusing iteration order
• Misunderstanding when third updates
• Off-by-one in stack operations

2. You are given a list of tokens representing an arithmetic expression in postfix notation, where each token is either an integer or an operator (+, -, *, /). Which algorithmic approach guarantees an optimal and straightforward evaluation of this expression?

easy

A. Dynamic programming approach that stores intermediate results in a table indexed by token positions.

B. Greedy algorithm that evaluates tokens from left to right, applying operators as soon as possible without using extra data structures.

C. Stack-based iterative evaluation that pushes operands and applies operators by popping the last two operands from the stack.

D. Recursive backtracking that tries all possible ways to parenthesize the expression and selects the correct evaluation.

Solution

1. Step 1: Understand the problem structure

   Postfix expressions require operands to be processed before operators, which naturally fits a stack structure.

2. Step 2: Identify the correct approach

   Stack-based iterative evaluation pushes operands and pops two operands when an operator is encountered, applying the operator and pushing the result back.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Stack usage matches postfix evaluation logic [OK]

Hint: Postfix evaluation naturally uses a stack [OK]

Common Mistakes:

• Thinking greedy evaluation without stack works
• Confusing postfix with infix DP
• Using recursion without clear base cases

3. Consider the following buggy code snippet for the optimal calculator. Which line contains the subtle bug that causes incorrect results for expressions with negative division?

medium

A. Line with 'current_op = c' updating the operator

B. Line with 'last_num = last_num // current_num' (integer division without handling negatives)

C. Line with 'current_num = current_num * 10 + int(c)' parsing digits

D. Line with 'total += last_num' inside '+' case

Solution

1. Step 1: Identify division handling

   Integer division of negative numbers must truncate toward zero, not floor.

2. Step 2: Locate bug line

   The line 'last_num = last_num // current_num' does not handle negative last_num correctly, causing wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct negative division requires special handling, missing here [OK]

Hint: Negative division truncation requires special code [OK]

Common Mistakes:

• Ignoring negative division truncation
• Forgetting to add last_num at end
• Misparsing digits

4. What is the time complexity of the optimal stack-based decoding algorithm for a string of length n with maximum repeat count max_k?

medium

A. O(n * max_k)

B. O(n)

C. O(n^2)

D. O(n log max_k)

Solution

1. Step 1: Identify loops and string expansions

   The algorithm iterates over n characters, but each decoded substring can be repeated up to max_k times, causing repeated concatenations.

2. Step 2: Analyze string multiplication cost

   Multiplying substrings by count k can cause up to O(n * max_k) time in worst case, as repeated expansions dominate.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Repeated expansions cause linear times max_k complexity [OK]

Hint: String repeats multiply runtime by max_k [OK]

Common Mistakes:

• Assuming O(n) ignoring repeat expansions
• Confusing max_k with log factor

5. Suppose the problem is modified so that digits can be removed multiple times (i.e., you can remove the same digit repeatedly if it appears multiple times), or the input string can contain non-digit characters. Which modification to the original algorithm is necessary to handle these changes correctly?

hard

A. Use a frequency map to track digit counts and remove digits greedily based on frequency

B. Switch to a brute force approach generating all subsequences since greedy no longer applies

C. Preprocess input to filter out non-digit characters and apply the same monotonic stack algorithm without changes

D. Modify the stack to allow re-insertion of digits and skip non-digit characters during iteration

Solution

1. Step 1: Analyze impact of repeated removals and non-digit chars

   Allowing multiple removals of the same digit requires the stack to handle re-insertion or multiple passes. Non-digit chars must be skipped to avoid errors.

2. Step 2: Identify necessary algorithm modification

   The stack must be adapted to allow re-insertion or multiple removals, and iteration must skip non-digit characters to maintain correctness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Handling input sanitization and stack flexibility is key for this variant [OK]

Hint: Stack must handle re-insertions and skip invalid chars [OK]

Common Mistakes:

• Assuming original algorithm works unchanged
• Ignoring input sanitization
• Switching to brute force unnecessarily