• ㊗️
• 大家
• offer
• 多多！

## Problem

Evaluate the value of an arithmetic expression in Reverse 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


## Code

class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(String s : tokens){
if(s.equals("+")){
stack.push(stack.pop() + stack.pop());
} else if (s.equals("-")){
int b = stack.pop();
int a = stack.pop();
stack.push(a - b);
} else if (s.equals("*")){
stack.push(stack.pop() * stack.pop());
} else if(s.equals("/")){
int b = stack.pop();
int a = stack.pop();
stack.push(a / b);
} else {
stack.push(Integer.parseInt(s));
}
}

return stack.pop();
}
}


public class CalculatorException extends Exception {
public CalculatorException(String message) {
super(message);
}
}

public enum Operator {
public Double calculate(Double firstOperand, Double secondOperand) throws CalculatorException {
return secondOperand + firstOperand;
}
},

...
SQUAREROOT("sqrt", 1) {
public Double calculate(Double firstOperand, Double secondOperand) {
return sqrt(firstOperand);
}
},

private static final Map<String, Operator> lookup = new HashMap<String, Operator>();

static {
for (Operator o : values()) {
lookup.put(o.getSymbol(), o);
}
}

private String symbol;
private String opposite;
private int operandsNumber;

Operator(String symbol, int operandsNumber) {
this.symbol = symbol;
this.operandsNumber = operandsNumber;
}

public static Operator getEnum(String value) {
return lookup.get(value);
}

public abstract Double calculate(Double firstOperand, Double secondOperand) throws CalculatorException;

public String getSymbol() {
return symbol;
}

public int getOperandsNumber() {
return operandsNumber;
}

@Override
public String toString() {
return symbol;
}
}

class Solution {
Stack<Double> valuesStack = new Stack<>();

private Double tryParseDouble(String str) {
try {
return Double.parseDouble(str);
} catch (NumberFormatException nfe) {
return null;
}
}

private void calculate(String operatorString) throws CalculatorException {
if (valuesStack.isEmpty()) {
throw new CalculatorException("empty stack");
}

Operator operator = Operator.getEnum(operatorString);
if (operator == null) {
throw new CalculatorException("invalid operator");
}

if (operator.getOperandsNumber() > valuesStack.size()) {
throwInvalidOperand(operatorString);
}

Double firstOperand = valuesStack.pop();
Double secondOperand = (operator.getOperandsNumber() > 1) ? valuesStack.pop() : null;
Double result = operator.calculate(firstOperand, secondOperand);

if (result != null) {
valuesStack.push(result);
}
}

public double evalRPN(String[] tokens) throws Exception {
for (String token : tokens) {
Double value = tryParseDouble(token);
if (value == null) {
calculate(token);
} else {
valuesStack.push(value);
}
}

double res = 0;
while (!valuesStack.isEmpty()) {
res += valuesStack.pop();
}

return res;
}
}