How do you approach Basic Calculator?

With only + and -, you can evaluate left to right keeping a running result and the sign of the next term. What breaks this? Parentheses.

What is the time complexity of Basic Calculator?

Time complexity: O(n) - single scan. Space complexity: O(n) worst case for the nesting stack.

What are common mistakes on Basic Calculator?

Popping without first checking the stack is non-empty. Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer. Pushing values where the problem needs indices back.

Sitelet https://gitgood.dev/coding/basic-calculator

gitGood.dev

← Back to problems

Basic Calculator

HardData Structures

Description

Given a string s representing a valid arithmetic expression, evaluate it and return the result as an integer.

The expression may contain:

Non-negative integer numbers
+ and - operators (including unary minus, e.g. "-(2 + 3)")
Parentheses ( and )
Spaces

You must not use any built-in expression evaluator (such as eval).

Example 1

Input: s = "1 + 1"

Output: 2

Example 2

Input: s = " 2-1 + 2 "

Output: 3

Example 3

Input: s = "(1+(4+5+2)-3)+(6+8)"

Output: 23

Constraints

- 1 <= s.length <= 3 * 10^5 - s consists of digits, '+', '-', '(', ')', and ' '. - s represents a valid expression. - '+' is never used as a unary operator. - Every number and the result fit in a signed 32-bit integer.

Basic Calculator: approach, complexity and pitfalls

A hard stack problem, graded against 7 test cases (4 of them hidden).

The pattern: Stack

Last-in-first-out processing - matching, nesting, and deferred evaluation.

Reach for it when you see: Balanced brackets, nested structures, undo/back semantics, or expression evaluation.

If you are stuck

Show the 3-step hint ladder

With only + and -, you can evaluate left to right keeping a running result and the sign of the next term. What breaks this? Parentheses.
When you hit '(', the running result and pending sign must be remembered until the matching ')' - a stack of saved (result, sign) contexts handles arbitrary nesting.
On ')', finish the inner result, pop the saved sign and result, and combine: result = savedResult + savedSign * innerResult. A unary minus is just a '-' seen before '(' or a number.

The optimal approach

Show the approach: Running Sum with a Context Stack

Scan the string once, maintaining a running `result`, the `sign` to apply to the next term, and the number being parsed. On `(`, push the current `result` and `sign` onto a stack and start a fresh subexpression; on `)`, finish the subexpression and combine it with the popped context: `result = savedResult + savedSign * inner`.

Unary minus falls out naturally: `-( ... )` simply records `sign = -1` before the parenthesis is opened. Multi-digit numbers are accumulated digit by digit, and spaces are skipped.

Time: O(n) - single scan
Space: O(n) worst case for the nesting stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Stack mistakes

These apply to the pattern as a whole, not just this problem.

Popping without first checking the stack is non-empty.
Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer.
Pushing values where the problem needs indices back.