Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are+,-,*,/. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
我的解题思路：这道题应该是简单的，但是要注意Interge.parseInt()方法以及栈中数据的先后顺序
在下的代码 时间122ms 空间11880k
import java.util.Stack;
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
for (int i=0;i<tokens.length;i++){
String str = tokens[i];
if (str.equals("+")) {
int res = stack.pop() + stack.pop();
stack.push(res);
}
else if (str.equals("-")) {
int res = (stack.pop() - stack.pop()) * (-1);
stack.push(res);
}
else if (str.equals("*")) {
int res = stack.pop() * stack.pop();
stack.push(res);
}
else if (str.equals("/")) {
int num1 = stack.pop();
int num2 = stack.pop();
int res = num2 / num1;
stack.push(res);
}
else {
stack.push(Integer.parseInt(str));
}
}
return stack.pop();
}
}
大神代码 时间148ms 空间13132k 思路很新颖，用了异常来pop元素，非常好的方法
import java.util.Stack;
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0;i<tokens.length;i++){
try{
int num = Integer.parseInt(tokens[i]);
stack.add(num);
}catch (Exception e) {
int b = stack.pop();
int a = stack.pop();
stack.add(get(a, b, tokens[i]));
}
}
return stack.pop();
}
private int get(int a,int b,String operator){
switch (operator) {
case "+":
return a+b;
case "-":
return a-b;
case "*":
return a*b;
case "/":
return a/b;
default:
return 0;
}
}
}
leetcode evaluate-reverse-polish-notation
原文：http://www.cnblogs.com/Melinni/p/7436413.html