0% completed
Problem Statement
Given an array of strings tokens
that represents an arithmetic expression in Reverse Polish Notation (RPN), evaluate
the expression and return the resulting integer value.
- The valid operators are
'+'
,'-'
,'*'
, and'/'
. - Each operand can be an integer or another expression.
- Division between two integers should truncate towards zero.
- No division by zero will occur.
- The input is a valid RPN expression.
- All results fit within a 32-bit integer.
Examples
Example 1
- Input: tokens =
["2", "11", "5", "/", "+"]
- Output:
4
- Explanation: (11 / 5) = 2, then (2 + 2) = 4.
Example 2
- Input: tokens =
["2", "3", "11", "+", "*"]
- Output:
28
- Explanation: (11 + 3) = 14, then (2 * 14) = 28.
Example 3
- Input: tokens =
["5", "1", "2", "+", "4", "*", "+", "3", "-"]
- Output:
14
- Explanation: (1 + 2) = 3, (3 * 4) = 12, (5 + 12) = 17, (17 - 3) = 14.
Constraints:
- 1 <= tokens.length <= 10<sup>4</sup>
tokens[i]
is either an operator: "+", "-", "*", or "/", or an integer in the range[-200, 200]
.
Solution
To solve this problem, we use a stack to evaluate the Reverse Polish Notation. In RPN, every operator follows all of its operands. We process each token in the input array one by one. When we encounter an operand (number), we push it onto the stack. When we encounter an operator, we pop the required number of operands from the stack, perform the operation, and push the result back onto the stack. This approach ensures that operations are performed in the correct order. Using a stack is efficient here because it allows us to handle the nested structure of the expression naturally.
This approach is effective because it takes advantage of the LIFO (Last In, First Out) nature of stacks, ensuring that each operation uses the most recently encountered operands. It also handles all types of valid RPN expressions without needing to parse or rearrange the input, making it straightforward and reliable.
Step-by-Step Algorithm
- Create an empty stack to store intermediate results.
- Iterate through each token in the input array
tokens
:- If the token is a number, convert it to an integer and push it onto the stack.
- If the token is an operator (
+
,-
,*
, or/
):- Pop the top two numbers from the stack. Let's call them
b
anda
(wherea
is the second popped number andb
is the first popped number). - Apply the operator to
a
andb
. For example, if the operator is+
, calculatea + b
. - Push the result of the operation back onto the stack.
- Pop the top two numbers from the stack. Let's call them
- After processing all tokens, the stack should contain exactly one element. This element is the result of the expression.
- Return the value of the single element left in the stack as the result.
Algorithm Walkthrough
Using the input: ["5", "1", "2", "+", "4", "*", "+", "3", "-"]
Initial State
- Stack:
[]
Step-by-Step Execution
-
Token:
"5"
- Action: Push
5
onto the stack. - Stack:
[5]
- Action: Push
-
Token:
"1"
- Action: Push
1
onto the stack. - Stack:
[5, 1]
- Action: Push
-
Token:
"2"
- Action: Push
2
onto the stack. - Stack:
[5, 1, 2]
- Action: Push
-
Token:
"+"
- Action: Pop
2
and1
from the stack, compute1 + 2 = 3
, push3
back onto the stack. - Stack:
[5, 3]
- Action: Pop
-
Token:
"4"
- Action: Push
4
onto the stack. - Stack:
[5, 3, 4]
- Action: Push
-
Token:
"*"
- Action: Pop
4
and3
from the stack, compute3 * 4 = 12
, push12
back onto the stack. - Stack:
[5, 12]
- Action: Pop
-
Token:
"+"
- Action: Pop
12
and5
from the stack, compute5 + 12 = 17
, push17
back onto the stack. - Stack:
[17]
- Action: Pop
-
Token:
"3"
- Action: Push
3
onto the stack. - Stack:
[17, 3]
- Action: Push
-
Token:
"-"
- Action: Pop
3
and17
from the stack, compute17 - 3 = 14
, push14
back onto the stack. - Stack:
[14]
- Action: Pop
Final State
- Stack:
[14]
- Result:
14
The final value in the stack, 14
, is the result of the RPN expression.
Code
Complexity Analysis
Time Complexity
The time complexity of the algorithm is O(n), where n
is the number of tokens in the input array. Each token is processed once, and basic stack operations (push and pop) take constant time, O(1).
Space Complexity
The space complexity of the algorithm is O(n), where n
is the number of tokens. In the worst case, all tokens are numbers, and we push each onto the stack, resulting in a maximum stack size of n
.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible