2014年5月6日星期二

Stack Solution - Evaluate Reverse Polish Notation

The basic idea is to use a stack to store each token until find an operator.

public class Solution {
    public int evalRPN(String[] tokens) {
if (tokens == null || tokens.length == 0) {
return Integer.MIN_VALUE;
}
Stack<String> inputTokens = new Stack<String>();
int result = Integer.MIN_VALUE;
int index = 0;
while (index < tokens.length) {
if(!tokens[index].equals("+")  && !tokens[index].equals("-") && !tokens[index].equals("*") && !tokens[index].equals("/")){
if (tokens.length == 1) {
return Integer.parseInt(tokens[index]);
}
inputTokens.push(tokens[index]);
} else {
if (inputTokens.size() < 2) {
return Integer.MIN_VALUE;
}
int operandTwo = Integer.parseInt(inputTokens.pop());
int operandOne = Integer.parseInt(inputTokens.pop());
if (tokens[index].equals("+")) {
// if (index == tokens.length - 1) {
// result = operandOne + operandTwo;
// } else {
inputTokens.push(String.valueOf(operandOne + operandTwo));
// }
}
if (tokens[index].equals("-")) {
// if (index == tokens.length - 1) {
// result = operandOne - operandTwo;
// } else {
inputTokens.push(String.valueOf(operandOne - operandTwo));
// }
}
if (tokens[index].equals("*")) {
// if (index == tokens.length - 1) {
// result = operandOne * operandTwo;
// } else {
inputTokens.push(String.valueOf(operandOne * operandTwo));
// }
}
if (tokens[index].equals("/")) {
// if (index == tokens.length - 1) {
// result = operandOne / operandTwo;
// } else {
inputTokens.push(String.valueOf(operandOne / operandTwo));
// }
}

}
index++;
}
if (inputTokens.size() != 0) {
   result = Integer.parseInt(inputTokens.pop());
//return Integer.MIN_VALUE;
}
return result;
}
}

没有评论: