# Evaluate Expression

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

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

Input Format

```The only argument given is character array A.
```
Output Format

```Return the value of arithmetic expression formed using reverse Polish Notation.
```
For Example

```Input 1:
A =   ["2", "1", "+", "3", "*"]
Output 1:
9
Explaination 1:
starting from backside:
*: ( )*( )
3: ()*(3)
+: ( () + () )*(3)
1: ( () + (1) )*(3)
2: ( (2) + (1) )*(3)
((2)+(1))*(3) = 9

Input 2:
A = ["4", "13", "5", "/", "+"]
Output 2:
6
Explaination 2:
+: ()+()
/: ()+(() / ())
5: ()+(() / (5))
1: ()+((13) / (5))
4: (4)+((13) / (5))
(4)+((13) / (5)) = 6```
Method:

Use a stack to keep track of the numbers, every time an operator is seen, pop two numbers and perform the operation.

Solution:

Time: O(n)
Space: O(n)

public class Solution {
public int evalRPN(ArrayList<String> A) {
Deque<String> stack = new ArrayDeque<>();
int result = 0;
for (String str : A) {
if (isOperator(str)) {
int b = Integer.valueOf(stack.pop());
int a = Integer.valueOf(stack.pop());
int temp = 0;
if (str.equals("+")) {
temp = a + b;
} else if (str.equals("-")) {
temp = a - b;
} else if (str.equals("*")) {
temp = a * b;
} else if (str.equals("/")) {
temp = a / b;
}
stack.push("" + temp);
} else {
stack.push(str);
}
}
return Integer.valueOf(stack.pop());
}

private boolean isOperator(String str) {
if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
return true;
}
return false;
}
}