DSA problem
Basic Calculator
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation. The expression s consists of digits, +, -, (, ), and . There is no multiplication or division — that simplification matters — but there are arbitrary levels of parentheses and unary-like minus signs.
Note: you are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval() or its equivalents. You must build the parser yourself.
Without multiplication and division, every operand contributes either +num or -num to the running result, but the sign for any sub-expression flips when it sits inside an odd number of minus-prefixed parentheses. The stack technique here remembers, at the moment we enter a (, both the result accumulated so far and the sign that should apply to the entire upcoming sub-expression.
Concretely, we walk s once with three variables: result (the running total at this scope), sign (+1 or -1, the sign to apply to the next number), and num (the number currently being built digit by digit). On ( we push result and sign, then reset them to start a fresh sub-scope. On ) we add the current number into result (closing this scope), then pop the saved sign and result and combine: result = savedResult + savedSign * result. Plus and minus signs simply update sign. At the end we add the final number to result and return it. This is O(n) time and O(n) space.
Examples
s = "1 + 1"2s = " 2-1 + 2 "3s = "(1+(4+5+2)-3)+(6+8)"23Constraints
- 1 <= s.length <= 3 * 10^5
- s consists of digits, '+', '-', '(', ')', and ' '.
- s represents a valid expression.
- '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
- '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
- There will be no two consecutive operators in the input.
- Every number and running calculation will fit in a signed 32-bit integer.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.