Yahoo Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
There is a hack : you may use eval function, if programming language supports such things.
For example, if you are writing in Java, you may use ScriptEngineManager.
ScriptEngineManager manager = new ScriptEngineManager();
ScriptEngine engine = manager.getEngineByName("js");
Object result = engine.eval("3+4*2");
otherwise you can build reverse polish notation, and then evaluate it.
Suppose that all operators are binary, no brackets.
private static Map<Character, Integer> priority;
static {
priority = new HashMap<Character, Integer>();
priority.put('+',1);
priority.put('-',2);
priority.put('*',3);
priority.put('/',4);
priority.put('^',5);
}
private static Boolean isOperator(char c){
return priority.containsKey(c);
}
private static Boolean isOperand(char c){
int val = Character.getNumericValue(c);
return (0 <= val && val <= 9);
}
private static int evaluate (Character c , int b , int a) throws Exception {
switch (c) {
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
case '^':
return (int)Math.pow(a,b);
default:
throw new Exception("Unknown operator");
}
}
private static int evaluate(String s) throws Exception {
if (s.length() == 0)
return 0;
Stack<Integer> operands = new Stack<Integer>();
Stack<Character> operators = new Stack<Character>();
for (int i = 0 ; i < s.length() ; i++){
char currentChar = s.charAt(i);
if (isOperand(currentChar))
operands.push(Character.getNumericValue(currentChar));
else if (isOperator(currentChar)){
if (operators.isEmpty()) {
operators.push(currentChar);
continue;
}
if (priority.get(operators.peek()) < priority.get(currentChar)){
operators.add(currentChar);
continue;
}
char currentOperator = currentChar;
while (!operators.isEmpty() && priority.get(currentOperator) < priority.get(operators.peek())){
operands.push(evaluate(operators.pop(), operands.pop(), operands.pop()));
}
operators.push(currentChar);
}
else{
throw new Exception("Unknown lexeme");
}
}
while (!operators.isEmpty()) {
operands.push(evaluate(operators.pop(), operands.pop(), operands.pop()));
}
return operands.peek();
}
//bodmas rule without brackets
public static void main(String args[])
{
String str = "3+2^2*5/2-1+2^2";
System.out.println(evaluate(str.replace("-", "+-").replace("+", "\\+").replace("^", "\\^").replace("*", "\\*")));
}
private static String evaluate(String str) {
if(str.contains("+"))
{
String arr[] = compute(str.replace("\\+", "+"),"\\+") ;
return calculate(arr, "+");
}
else if(str.contains("*"))
{
String arr[] = compute(str.replace("\\*", "*"),"\\*") ;
return calculate(arr, "*");
}
else if(str.contains("/"))
{
String arr[] = compute(str,"/") ;
return calculate(arr, "/");
}
else if(str.contains("^"))
{
String arr[] = compute(str.replace("\\^", "^"),"\\^") ;
//return calculate(arr, "^");
return ""+Math.pow(toInt(arr[0]), toInt(arr[1]));
}
else
return str;
}
public static String calculate(String arr[], String operator)
{
// create a script engine manager
ScriptEngineManager factory = new ScriptEngineManager();
// create JavaScript engine
ScriptEngine engine = factory.getEngineByName("JavaScript");
// evaluate JavaScript code from given file - specified by first argument
// engine.eval();
double result = toInt(arr[0]);
for(int i = 1 ; i< arr.length; i++)
{
try {
result = (Double) engine.eval(result+operator+arr[i]);
} catch (ScriptException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return result+"";
}
public static String[] compute(String str, String operator)
{
String[] arr = str.split(operator);
for( int i = 0; i< arr.length; i++)
{
arr[i] = evaluate(arr[i]);
}
return arr;
}
public static double toInt(String str)
{
return Double.parseDouble(str);
}
}
use reverse polish notation.
- GK June 07, 2014