Thursday, September 18, 2014

Evaluate Reverse Polish Notation

public int evalRPN(String[] tokens){
int invalidResult = 0;
int size = tokens.length;

//validate tokens:
for(int i=0; i<size; i++){
if(!isInteger(tokens[i]) && !isSymbol(tokens[i])){
return invalidResult;
}
}

if(size==1 && isInteger(tokens[0])) return getInteger(tokens[0]);

if (size<2) return invalidResult;

Deque<Integer> numQ=new ArrayDeque<Integer>();
numQ.addFirst(getInteger(tokens[0]));
numQ.addFirst(getInteger(tokens[1]));
int idx = 2;
int op1;
int op2;
while(idx<tokens.length && numQ.size()>0){
if (isSymbol(tokens[idx])){
op2 = numQ.remove();
op1 = numQ.remove();
numQ.addFirst(calculate(op1, op2, tokens[idx]));
}
else {
numQ.addFirst(getInteger(tokens[idx]));
}
idx++;
}
if(numQ.size()!=1 || idx!=tokens.length) return invalidResult;
return numQ.remove();
}

private boolean isSymbol(String s){
if (s.equalsIgnoreCase("+")
||s.equalsIgnoreCase("-")
||s.equalsIgnoreCase("*")
||s.equalsIgnoreCase("/")) return true;
return false;
}

private int calculate(int op1, int op2, String op){
if(op.equalsIgnoreCase("+")){
return op1 + op2;
}
if(op.equalsIgnoreCase("-")){
return op1 - op2;
}
if(op.equalsIgnoreCase("*")){
return op1 * op2;
}
if(op.equalsIgnoreCase("/")){
if (op2 == 0) return 0;
return op1 / op2;
}
return 0;
}

private boolean isInteger(String s){
return s.matches("\\d++") || s.matches("\\+\\d++") || s.matches("-\\d++");
}

private int getInteger(String s){
int invalidValue = 0;
if (s.matches("\\d++")) return Integer.valueOf(s);
if (s.matches("\\+\\d++"))return Integer.valueOf(s.substring(1));
if (s.matches("-\\d++")) return Integer.valueOf(s.substring(1))*(-1);
return invalidValue;
}
}

No comments:

Post a Comment