Evaluate Reverse Polish Notation (Leetcode 150)

Difficulty: Medium Link: Day 25: May Leetcode Challenge

Problem Description

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +-*, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Examples

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
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
= 22

Constraints

  • 1 <= tokens.length <= 104
  • tokens[i] is either an operator: "+""-""*", or "/", or an integer in the range [-200, 200].

Solution

We can immediately think of a brute force approach where we can keep evaluating result on the fly. However, the problem arises when there is a nested expression where we need to backtrack. For example:

Input : ["4","13","5","/","+"]
Result : (4 + (13 / 5)) = 6

In such cases, we will might have to track back the whole array in reverse which would increase its complexity to O(N2). We need to come up with a better approach.

If you know about history of reverse polish notation, it was designed specifically to make computing easier with the more efficient use of a stack. Using the stack would enable us to get the last two operands and easily store the resultant value for future calculations. Since it is given that input would always be a valid reverse polish expression, hence we would always have at least two operands before any operator(+ / – *). One more thing to note is that in case of / and – , the order of the operands matters. So if input is 3 2 –, then result should be 3 – 2 and not 2-3. We can ensure this by using the top of the stack as second operand and value popped after it as the first operand. We also need to push the result back into the stack and ultimately the final result would be left on the stack which we can return.

Swift

class Solution {
func evalRPN(_ tokens: [String]) -> Int {
var stack = [Int]()
var operators = "+-/*"
for token in tokens {
if operators.contains(token) {
var result = 0
let second = stack.popLast()!
let first = stack.popLast()!
switch token {
case "+":
result = first + second
case "":
result = first second
case "*":
result = first * second
default:
result = first/second
}
stack.append(result)
}
else if let value = Int(token){
stack.append(value)
}
}
return stack[0]
}
}

Python

def evalRPN(self, tokens):
stack = []
for token in tokens:
if token not in "+-/*":
stack.append(int(token))
continue
number_2 = stack.pop()
number_1 = stack.pop()
result = 0
if token == "+":
result = number_1 + number_2
elif token == "-":
result = number_1 number_2
elif token == "*":
result = number_1 * number_2
else:
result = int(number_1 / number_2)
stack.append(result)
return stack.pop()

Java

class Solution {
private static final Map<String, BiFunction<Integer, Integer, Integer>> OPERATIONS = new HashMap<>();
// Ensure this only gets done once for ALL test cases.
static {
OPERATIONS.put("+", (a, b) > a + b);
OPERATIONS.put("", (a, b) > a b);
OPERATIONS.put("*", (a, b) > a * b);
OPERATIONS.put("/", (a, b) > a / b);
}
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (!OPERATIONS.containsKey(token)) {
stack.push(Integer.valueOf(token));
continue;
}
int number2 = stack.pop();
int number1 = stack.pop();
BiFunction<Integer, Integer, Integer> operation;
operation = OPERATIONS.get(token);
int result = operation.apply(number1, number2);
stack.push(result);
}
return stack.pop();
}
}

Complexity Analysis

We are iterating linearly on the input array and popping last two elements in case we encounter an operator which is O(1) operation. Hence, it is a O(N) algorithm. For space, we are using a stack which in the worst case, would contain all the elements at once.

Time = O(N)

Space = O(N)

Leave a Reply

Your email address will not be published. Required fields are marked *