Description
You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of the expression.
Note that:
- The valid operators are
'+','-','*', and'/'. - Each operand may be an integer or another expression.
- The division between two integers always truncates toward zero.
- There will not be any division by zero.
- The input represents a valid arithmetic expression in a reverse polish notation.
- The answer and all the intermediate calculations can be represented in a 32-bit integer.
Examples:
Example 1:
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22Solution in Python
Approach:
- Initialization: Create an empty stack to keep track of the operands.
- Iterate through Tokens: Loop through each token in the input list:
- If the token is an operand (integer): Convert it to an integer and push it onto the stack.
- If the token is an operator: Pop the top two elements from the stack, perform the operation, and push the result back onto the stack.
- Final Result: After processing all tokens, the stack should contain one element, which is the result of the expression.
Detailed Steps:
- Operand Handling: When encountering an integer, simply push it onto the stack.
- Operator Handling: For operators (
+,-,*,/):- Pop the top two elements from the stack.
- Apply the operator with the second popped element as the left operand and the first popped element as the right operand (since the first popped element is more recent and thus on the right in the expression).
- Push the result back onto the stack.
- Division Handling: Ensure integer division truncates towards zero, which is handled correctly by Python’s
//operator when applied to positive results ofintdivision.
Python
from typing import List
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
# Stack to hold operands
stack = []
# Iterate through each token
for token in tokens:
if token in "+-*/":
# Operator encountered
right = stack.pop() # First popped element (right operand)
left = stack.pop() # Second popped element (left operand)
# Perform the operation based on the token
if token == '+':
result = left + right
elif token == '-':
result = left - right
elif token == '*':
result = left * right
elif token == '/':
# Division should truncate towards zero
result = int(left / right) # Ensures truncation towards zero
stack.append(result) # Push the result back to the stack
else:
# Operand encountered, convert to integer and push to stack
stack.append(int(token))
# The final result should be the only element in the stack
return stack.pop()Explanation:
- Stack Initialization: An empty list
stackis initialized to store operands. - Iteration: Each token is processed. If it’s an operator, the last two operands are popped from the stack, the operation is performed, and the result is pushed back onto the stack.
- Operands: Converted to integers and pushed directly onto the stack.
- Final Result: The last remaining element in the stack is the result of the RPN expression.
This solution is efficient with a time complexity of O(n), where nnn is the number of tokens, and it uses space proportional to the number of tokens due to the stack. The constraints ensure that this approach will handle all valid input sizes within reasonable limits.
Solution in Javascript
JavaScript
/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function(tokens) {
// Stack to hold operands
const stack = [];
// Iterate through each token
for (const token of tokens) {
if (['+', '-', '*', '/'].includes(token)) {
// Operator encountered
const right = stack.pop(); // First popped element (right operand)
const left = stack.pop(); // Second popped element (left operand)
let result;
// Perform the operation based on the token
switch (token) {
case '+':
result = left + right;
break;
case '-':
result = left - right;
break;
case '*':
result = left * right;
break;
case '/':
// Division should truncate towards zero
result = Math.trunc(left / right); // Use Math.trunc for truncation towards zero
break;
}
stack.push(result); // Push the result back to the stack
} else {
// Operand encountered, convert to integer and push to stack
stack.push(parseInt(token, 10));
}
}
// The final result should be the only element in the stack
return stack.pop();
};Solution in Java
Java
import java.util.Stack;
class Solution {
public int evalRPN(String[] tokens) {
// Stack to hold operands
Stack<Integer> stack = new Stack<>();
// Iterate through each token in the input array
for (String token : tokens) {
if (isOperator(token)) {
// Operator encountered
int right = stack.pop(); // First popped element (right operand)
int left = stack.pop(); // Second popped element (left operand)
int result = 0;
// Perform the operation based on the token
switch (token) {
case "+":
result = left + right;
break;
case "-":
result = left - right;
break;
case "*":
result = left * right;
break;
case "/":
// Division should truncate towards zero
result = left / right; // Integer division truncates towards zero in Java
break;
}
stack.push(result); // Push the result back onto the stack
} else {
// Operand encountered, convert to integer and push to stack
stack.push(Integer.parseInt(token));
}
}
// The final result should be the only element in the stack
return stack.pop();
}
// Helper method to check if a token is an operator
private boolean isOperator(String token) {
return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
}
}Solution in C#
C#
using System;
using System.Collections.Generic;
public class Solution {
public int EvalRPN(string[] tokens) {
// Stack to hold operands
Stack<int> stack = new Stack<int>();
// Iterate through each token in the input array
foreach (var token in tokens) {
if (IsOperator(token)) {
// Operator encountered
int right = stack.Pop(); // First popped element (right operand)
int left = stack.Pop(); // Second popped element (left operand)
int result = 0;
// Perform the operation based on the token
switch (token) {
case "+":
result = left + right;
break;
case "-":
result = left - right;
break;
case "*":
result = left * right;
break;
case "/":
// Division should truncate towards zero
result = left / right; // Integer division truncates towards zero in C#
break;
}
stack.Push(result); // Push the result back onto the stack
} else {
// Operand encountered, convert to integer and push to stack
stack.Push(int.Parse(token));
}
}
// The final result should be the only element in the stack
return stack.Pop();
}
// Helper method to check if a token is an operator
private bool IsOperator(string token) {
return token == "+" || token == "-" || token == "*" || token == "/";
}
}