# Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression inReverse Polish Notation.

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

Note:

• Division between two integers should truncate toward zero.
• The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.

Example 1:

``````Input:
["2", "1", "+", "3", "*"]

Output:
9

Explanation:
((2 + 1) * 3) = 9
``````

Example 2:

``````Input:
["4", "13", "5", "/", "+"]

Output:
6

Explanation:
(4 + (13 / 5)) = 6
``````

Example 3:

``````Input:
["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
``````

## Solution

Stack Implementation - (12ms)

``````class Solution {
public int evalRPN(String[] tokens) {
Deque<String> stack = new ArrayDeque<>();

for (String token : tokens) {
if (!isOperator(token)) {
stack.push(token);
} else {
int num1 = Integer.parseInt(stack.pop());
int num2 = Integer.parseInt(stack.pop());
int res = 0;
switch(token) {
case "+":
res = num2 + num1;
break;
case "-":
res = num2 - num1;
break;
case "*":
res = num2 * num1;
break;
case "/":
res = num2 / num1;
break;
}
stack.push(String.valueOf(res));
}
}
return Integer.parseInt(stack.peek());
}

private boolean isOperator(String token) {
}
}
``````

Improved without too much conversion of String / Integer - (11ms, 86.58%)

``````class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();

for (String token : tokens) {
if (!isOperator(token)) {
stack.push(Integer.valueOf(token));
} else {
int num1 = stack.pop();
int num2 = stack.pop();
int res = 0;
switch(token) {
case "+":
res = num2 + num1;
break;
case "-":
res = num2 - num1;
break;
case "*":
res = num2 * num1;
break;
case "/":
res = num2 / num1;
break;
}
stack.push(res);
}
}
return stack.peek();
}

private boolean isOperator(String token) {
}
}
``````

Another implementation: https://www.jiuzhang.com/solution/evaluate-reverse-polish-notation/

``````public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> s = new Stack<Integer>();
String operators = "+-*/";
for(String token : tokens){
if(!operators.contains(token)){
s.push(Integer.valueOf(token));
continue;
}

int a = s.pop();
int b = s.pop();
if(token.equals("+")) {
s.push(b + a);
} else if(token.equals("-")) {
s.push(b - a);
} else if(token.equals("*")) {
s.push(b * a);
} else {
s.push(b / a);
}
}
return s.pop();
}
}
``````