Basic Calculator II
Problem Description
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = "3+2*2"
Output: 7
Example 2:
Input: s = " 3/2 "
Output: 1
Example 3:
Input: s = " 3+5 / 2 "
Output: 5
Constraints:
- 1 <= s.length <= 3 * 105
sconsists of integers and operators('+', '-', '*', '/')separated by some number of spaces.srepresents a valid expression.- All the integers in the expression are non-negative integers in the range [0, 231 - 1].
- The answer is guaranteed to fit in a 32-bit integer.
Solve it on LeetCode
Approaches
1. Two Stacks
Intuition:
The problem requires us to evaluate a string containing a mathematical expression with +, -, *, and /. A straightforward approach is to use two stacks: one for numbers and another for operators. This is similar to the standard method used for evaluating expressions.
Steps:
- Use two stacks: one for operands (numbers) and one for operators.
- Traverse each character in the string:
- If it's a digit, build the number.
- If it's an operator, push the current number to the operands stack, then push the operator to the operators stack.
- Evaluate whenever necessary (
*and/have higher precedence). - Pop remaining operators and operands to calculate the result using a simple post-fix evaluation.
- Return the result.
Code:
- Time Complexity: O(n), where n is the length of the string.
- Space Complexity: O(n), due to the space used by the stacks.
2. One Stack
Intuition:
By recognizing the fact that * and / operations are executed immediately and have higher precedence, we can simplify our approach by using only one stack. We can optimize by directly evaluating the immediate * and / results on the numbers residing in the stack.
Steps:
- Initialize one stack to store evaluated values.
- Traverse the string similarly and calculate results on the fly based on operator priorities.
- Append intermediate results computed by
*and/into the stack. - Sum up the stack to get the final result.
Code:
- Time Complexity: O(n), where n is the length of the string.
- Space Complexity: O(n), due to the space used by the stack.
3. In-Place Calculation Using Single Pass and Single Stack
Intuition:
We can make this more efficient by minimizing stack use to only necessary intermediate results. We can modify the processed result in place using a single pass through the string. By evaluating high-priority operations as soon as possible, only results of addition/subtraction need to be stored.
Steps:
- Use a single stack to store previous evaluated results and only nums needed for adjusting the result from unfinished operations when needed.
- Track running total adjusted with prior operations.
- Evaluate high-precedence operations (
*,/) immediately and push intermediate results into the stack. - Perform addition and subtraction on accumulated results from the stack at the end.
Code:
- Time Complexity: O(n), where n is the length of the string.
- Space Complexity: O(1), due to constant space use.