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⁴
• 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

1. Create an empty stack to store intermediate results.
2. 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 and a (where a is the second popped number and b is the first popped number).
     • Apply the operator to a and b. For example, if the operator is +, calculate a + b.
     • Push the result of the operation back onto the stack.
3. After processing all tokens, the stack should contain exactly one element. This element is the result of the expression.
4. 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

1. Token: "5"

   • Action: Push 5 onto the stack.
   • Stack: [5]

2. Token: "1"

   • Action: Push 1 onto the stack.
   • Stack: [5, 1]

3. Token: "2"

   • Action: Push 2 onto the stack.
   • Stack: [5, 1, 2]

4. Token: "+"

   • Action: Pop 2 and 1 from the stack, compute 1 + 2 = 3, push 3 back onto the stack.
   • Stack: [5, 3]

5. Token: "4"

   • Action: Push 4 onto the stack.
   • Stack: [5, 3, 4]

6. Token: "*"

   • Action: Pop 4 and 3 from the stack, compute 3 * 4 = 12, push 12 back onto the stack.
   • Stack: [5, 12]

7. Token: "+"

   • Action: Pop 12 and 5 from the stack, compute 5 + 12 = 17, push 17 back onto the stack.
   • Stack: [17]

8. Token: "3"

   • Action: Push 3 onto the stack.
   • Stack: [17, 3]

9. Token: "-"

   • Action: Pop 3 and 17 from the stack, compute 17 - 3 = 14, push 14 back onto the stack.
   • Stack: [14]

Final State

• Stack: [14]
• Result: 14

The final value in the stack, 14, is the result of the RPN expression.