Wednesday, 11 September 2013

Efficiently parse single digit arithmatic expression

Efficiently parse single digit arithmatic expression

How would you efficiently (optimizing for runtime but also keeping space
at a minimum) parse and evaluate a single digit arithmetic expression in
Java.
The following arithmetic expressions are all valid:
eval("-5")=-5
eval("+4")=4
eval("4")=4
eval("-7+2-3")=-8
eval("5+7")=12
My approach is to iterate over all elements, keeping track of the current
arithmetic operation using a flag, and evaluate digit by digit.
public int eval(String s){
int result = 0;
boolean add = true;
for(int i = 0; i < s.length(); i++){
char current = s.charAt(i);
if(current == '+'){
add = true;
} else if(current == '-'){
add = false;
} else {
if(add){
result += Character.getNumericValue(current);
} else {
result -= Character.getNumericValue(current);
}
}
}
return result;
}
Is this the only optimal solution? I have tried to use stacks to keep
track of the arithmetic operator, but I am not sure this is any more
efficient. I also have not tried regular expressions. I only ask because I
gave the above solution in an interview and was told it is sub-optimal.

No comments:

Post a Comment