I’ve solved a few tasks from http://leetcode.com/ and going to publish my solutions,
So, first task is
Evaluate Reverse Polish Notation
The task description is :
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
Stop and think …
What do we have ? I can see some list of the numbers and operations, so, it looks like you or me added all items in LIFO style, like {2->1->+-> and so on}. OK, good, we can try to find data structure implemented that style. Each of us knows about Stack … OK, good, try to use that data structure in our implementation …
Firstly I’ve added calculator:
enum Operation{
PLUS("+"){
int calculate(int left, int right){
return left+right;
}
},MINUS("-"){
int calculate(int left, int right){
return left-right;
}
},MULTIPLY("*"){
int calculate(int left, int right){
return left*right;
}
},DIVIDE("/"){
int calculate(int left, int right){
return left/right;
}
};
String operation;
Operation(String op){
operation = op;
}
String getName(){
return operation;
}
abstract int calculate(int left, int right);
static Operation get(String val){
Operation[] operations = values();
for(Operation operation: operations){
if(operation.getName().equals(val))
return operation;
}
return null;
}
}
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> result = new Stack<Integer>();
for (String token : tokens) {
Operation operation;
if(!isNum(token)){
operation = Operation.get(token);
int secondValue = result.pop();
result.push(operation.calculate(result.pop(),secondValue));
}else {
result.push( Integer.valueOf(token));
}
}
return result.pop();
}
boolean isNum(String data){
boolean isNum = true;
try{
Integer.parseInt(data);
}catch(Exception e){
isNum = false;
}
return isNum;
}
}