Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
Better to implement as binary trees, but something simple in Java -
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.regex.Pattern;
public class SimpleExpressionEvalImpl {
private Pattern pattern = Pattern.compile("\\d+");
private Hashtable<Object, Double> context_dict = new Hashtable<Object, Double>();
private double evaluate(Object expList) {
if (expList instanceof String) {
if (pattern.matcher(expList.toString()).matches()) {
return Integer.parseInt(expList.toString());
}else{
return context_dict.get(expList.toString());
}
}
else {
ArrayList<?> exp_list = (ArrayList<?>)expList;
String operator = exp_list.get(0).toString();
Object exp = exp_list.get(1);
if (operator.equalsIgnoreCase("root")) {
return evaluate(exp);
}else if (operator.equalsIgnoreCase("add")) {
return evaluate(exp) + evaluate(exp_list.get(2));
}else if (operator.equalsIgnoreCase("mult")) {
return evaluate(exp) * evaluate(exp_list.get(2));
}else if (operator.equalsIgnoreCase("div")) {
return evaluate(exp) / evaluate(exp_list.get(2));
}else if (operator.equalsIgnoreCase("let")) {
context_dict.put(exp, evaluate(exp_list.get(2)));
return evaluate(exp_list.get(3));
}
}
return 0;
}
private Object[] parse_exp_str(String exp_str, String func_name, int index) throws Exception {
ArrayList<Object> exp_list = new ArrayList<Object>();
exp_list.add(func_name);
String tmp_str = "";
try{
while(true) {
char currentChar = exp_str.charAt(index);
if(currentChar == '(') {
Object[] returned = parse_exp_str(exp_str, tmp_str, index+1);
index = (int)returned[1];
exp_list.add(returned[0]);
tmp_str = "";
if (func_name.equalsIgnoreCase("root")) break;
}else if (currentChar == ')') {
if (tmp_str.length() > 0) exp_list.add(tmp_str);
break;
}else if (currentChar == ',') {
if (tmp_str.length() > 0) exp_list.add(tmp_str);
tmp_str = "";
}else{
tmp_str += exp_str.charAt(index);
}
++index;
}
}catch (Exception e) {
// TODO: handle exception
throw new InvalidExpressionException(exp_str, e);
}
return new Object[]{exp_list, index};
}
public double evaluateExpression(String expression) throws Exception{
return evaluate(parse_exp_str(expression.replaceAll(" ", ""), "root", 0)[0]);
}
public static void main(String[] args) {
String[] expressions =
{
"add(1, 2)",
"add(1, mult(2, 3))",
"mult(add(2, 2), div(9, 3))",
"let(a, 5, add(a, a))",
"let(a, 5, let(b, mult(a, 10), add(b, a)))",
"let(a, 5, let(b, div(a, 10), add(b, a)))",
"let(a, let(b, 10, add(b, b)), let(b, 20, add(a, b)))"
};
if(args.length == 1) expressions = args;
SimpleExpressionEvalImpl impl = new SimpleExpressionEvalImpl();
for(int i = 0; i < expressions.length; i++) {
String temp = expressions[i];
try{
double result = impl.evaluateExpression(temp);
System.out.println(temp + " ==> " + result);
}catch(Exception e){
e.printStackTrace();
}
}
}
}
Following is my solution in python. First the given expression string needs to be parsed into an array of nested sub-expressions. This parsing is the hardest part. An expression like "add(1,2)" gives an array ["add", "1", "2"]. Similarly, an expression like "add(1,mult(2,3))" will produce an array as follows: ['add', '1', ['mult', '2', '3']] Once the parsing is done, we evaluate the expressions recursively.
For the 'let' expression, we maintain a "context" dictionary to keep track of local variables.
CODE
def my_is_integer(s): try: int(s) return True except ValueError: return False def eval_exp(exp_list_or_str, context_dict): if type(exp_list_or_str) is str: if my_is_integer(exp_list_or_str): return int(exp_list_or_str) elif exp_list_or_str.isalnum(): return context_dict[exp_list_or_str] else: if exp_list_or_str[0] == 'ROOT': return eval_exp(exp_list_or_str[1], context_dict) elif exp_list_or_str[0] == 'add': return eval_exp(exp_list_or_str[1], context_dict) \ + eval_exp(exp_list_or_str[2], context_dict) elif exp_list_or_str[0] == 'mult': return eval_exp(exp_list_or_str[1], context_dict) \ * eval_exp(exp_list_or_str[2], context_dict) elif exp_list_or_str[0] == 'div': return eval_exp(exp_list_or_str[1], context_dict) \ / eval_exp(exp_list_or_str[2], context_dict) elif exp_list_or_str[0] == 'let': context_dict[exp_list_or_str[1]] = eval_exp(exp_list_or_str[2], context_dict) return eval_exp(exp_list_or_str[3], context_dict) def parse_exp_str(exp_str, func_name, index): exp_list = [func_name] tmp_str="" while(True): if exp_str[index] == ')': ## encountered close of parenthesis if tmp_str != "": exp_list.append(tmp_str) break elif exp_str[index] == '(': ## encountered a sub expression which is a function (tmp_list, index) = parse_exp_str(exp_str, tmp_str, index+1) exp_list.append(tmp_list) tmp_str = "" if func_name == 'ROOT': break elif exp_str[index] == ',': ## acquired one argument if tmp_str != "": exp_list.append(tmp_str) tmp_str = "" index += 1 else: ##accumulate string tmp_str += exp_str[index] index += 1 return (exp_list, index+1) ### MAIN ### exp_array = [ 'add(1, 2)', 'add(1, mult(2, 3))', 'mult(add(2, 2), div(9, 3))', 'let(a, 5, add(a, a))', 'let(a, 5, let(b, mult(a, 10), add(b, a)))', 'let(a, let(b, 10, add(b, b)), let(b, 20, add(a, b)))' ] for exp_str in exp_array: exp_str = exp_str.replace(" ", "") #remove all spaces #parse expression string into a nested array of sub-expressions (exp_list, tmp) = parse_exp_str(exp_str, "ROOT", 0) #evaluate the parsed exp_list result = eval_exp(exp_list, {}) print exp_list print exp_str +" => "+ str(result) print "\n\n"OUTPUT
- whatevva' June 12, 2013