191. Calculator To Evaluate Simple Expression String
Calculator To Evaluate Simple Expression String
Implement a basic calculator that evaluates a valid arithmetic expression given as a string.
The expression may contain non-negative integers, the operators +, -, *, and /, opening parentheses (, closing parentheses ), and empty spaces.
Parentheses must be evaluated before the surrounding expression.
Multiplication and division must be evaluated before addition and subtraction when they appear at the same parenthesis level.
Integer division must truncate toward zero.
The given expression is always valid.
You must not use any built-in expression evaluator such as eval.
Method Signature
int calculate(String expression)
- Evaluates the valid arithmetic expression string.
- Returns the final integer result after applying parentheses, operator precedence, and truncating division toward zero.
Input Format
The input is a string expression.
expression contains only digits, empty spaces, +, -, *, /, (, and ).- All integers inside
expression are non-negative.
- The expression is guaranteed to be valid.
Output Format
Return an integer representing the evaluated value of expression.
Rules
- Spaces do not affect the result.
- Parentheses have the highest priority.
* and / have higher priority than + and -.- Operators with the same priority are evaluated from left to right.
- Integer division truncates toward zero.
- Do not use built-in expression evaluation functions such as
eval.
Constraints
1 ≤ expression.length() ≤ 300,000expression is a valid arithmetic expression.expression contains only non-negative integers, empty spaces, +, -, *, /, (, and ).- Every intermediate result is in the range
-2,147,483,648 to 2,147,483,647.
- The final answer is in the range
-2,147,483,648 to 2,147,483,647.
Examples
Example 1
calculate(expression = "3 + 2")
Output: 5
Explanation: 3 + 2 = 5.
Example 2
calculate(expression = " 8-6 / 3 ")
Output: 6
Explanation: Division is evaluated first. 6 / 3 = 2, so the expression becomes 8 - 2 = 6.
Example 3
calculate(expression = "4*(2+3*3)/2+(7-5)")
Output: 24
Explanation: Inside the parentheses, 2 + 3 * 3 = 11. Then 4 * 11 / 2 = 22 and 7 - 5 = 2, so the final result is 24.
Example 4
calculate(expression = "(10+2*6-(4*5/2+3)*2)+1")
Output: -3
Explanation: 2 * 6 = 12, 4 * 5 / 2 = 10, and (10 + 3) * 2 = 26. The expression becomes 10 + 12 - 26 + 1 = -3.