Basic Calculator
The key idea
There is no
* or /, so the only hard part is parentheses and the running sign. Carry a running result, a sign (+1 or -1), and a building num. On ( push the current result and sign, then reset both for a fresh sub-expression; on ) finish the inner sum, multiply by the saved sign, and add back the saved result. The stack remembers the context outside each parenthesis so you never need recursion.Problem
Given a string s representing a valid mathematical expression, evaluate it and return its value.
The expression contains only non-negative integers, the operators + and -, parentheses ( and ), and spaces. There is no multiplication or division, so precedence comes entirely from the parentheses.
The - operator may be unary (for example -(2 + 3)), but + is never unary. You may not use any built-in library function such as eval that would evaluate the string directly.
Constraints
1 <= s.length <= 3 * 10^5sconsists of digits,'+','-','(',')', and' 'srepresents a valid expression'+'is not used as a unary operation (+1and+(2 + 3)are invalid)'-'could be used as a unary operation (-1and-(2 + 3)are valid)- There will be no two consecutive operators in the input
- Every number and running calculation fits in a signed 32-bit integer
Examples
Input: s = "1 + 1"
Output: 2
Input: s = " 2-1 + 2 "
Output: 3
Input: s = "1-(2+3)"
Output: -4
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization