Saturday, November 14, 2015

Expression evaluator

Given list of expressions
a = 10
b = a + 1
c = a + b
d = c * b + a * c
Print out value of last variable (in our example, it is d). 

First we would need a expression evaluator which will evaluate individual expression. 
Solution below uses two stacks for expression evaluation one for operator and one for operand. First we evaluate operations such as *, / which are high priority then evaluate +, - and = operators in second pass.

//The code below considers
//1. Only int values
//2. Only supports +, -, *, /, = operators  
public class Solution{

    private HashMap VarMap;
    Stack operandStack;
    Stack operatorStack;

    public  Solution(){
        VarMap = new HashMap<>();
        operandStack = new Stack<>();
        operatorStack = new Stack<>();
    }

    public int EvaluateExpression(String statement){
        return Evaluator(statement.replace(" ", ""));
    }

    private int GetNextOperand(String expression, int start){
        int i = start;
        for(; i < expression.length(); i++){
            char operator = expression.charAt(i);
            if(operator =='+' || operator == '-' || operator== '/' || operator == '*' || operator == '=')
               break;
        }
        return i;
    }

    private int EvaluateHighPriorityOpearators(){
        if(operatorStack.empty())
            return 0;
        char lastOperator = operatorStack.peek();
        switch (lastOperator){
            case '+':
            case '-':
                break;
            case '*': {
                String operand2 = operandStack.pop();
                String operand1 = operandStack.pop();

                String resultStr = operand1 + "*" + operand2;
                int result = VarMap.get(operand1) * VarMap.get(operand2);
                VarMap.put(resultStr, result);
                operandStack.push(resultStr);
                operatorStack.pop();
                return result;
            }
            case '/': {
                String operand2 = operandStack.pop();
                String operand1 = operandStack.pop();

                String resultStr = operand1 + "/" + operand2;
                int result = VarMap.get(operand1) / VarMap.get(operand2);
                VarMap.put(resultStr, result);
                operandStack.push(resultStr);
                operatorStack.pop();
                return result;
            }
        }
        return 0;
    }

    private int EvaluateNormalPriorityOperators() {
        if (operandStack.empty())
            return 0;
        int result = 0;
        if( VarMap.containsKey(operandStack.peek()) )
            result = VarMap.get(operandStack.pop());
        else
            result = Integer.parseInt(operandStack.pop());

        while (!operatorStack.empty()) {
            char lastOperator = operatorStack.pop();
            String operand1 = operandStack.pop();
            int val = 0;
            if (VarMap.containsKey(operand1))
                val = VarMap.get(operand1);
            else
                if(lastOperator != '=')
                    val = Integer.parseInt(operand1);

            switch (lastOperator) {
                case '+':
                    result += val;
                    break;
                case '-':
                    result -= val;
                    break;
                case '=':
                    VarMap.put(operand1, result);
                    break;
            }
        }
        return result;
    }

    private int Evaluator(String expression){
        int result = 0;
        String operand = "";
        char operator = ' ';
        for(int start = 0; start < expression.length(); ){
            int i = GetNextOperand(expression, start);
            operand = expression.substring(start, i);
            operandStack.push(operand);
            result = EvaluateHighPriorityOpearators();
            if (i < expression.length()){
                operator = expression.charAt(i);
                operatorStack.push(operator);
            }
            start = i + 1;
        }

        if(!operandStack.isEmpty()){
            result = EvaluateNormalPriorityOperators();
        }
        return result;
    }

    public static void main(String[] args) {
        List input = new ArrayList<>();
        input.add("a = 10");
        input.add("b = a + 1");
        input.add("c = a + b");
        input.add("d = c * b + a * b");

        Solution sol = new Solution();

        for (int i = 0; i < input.size()-1; i++){
            sol.EvaluateExpression(input.get(i));
        }
        System.out.println(sol.EvaluateExpression(input.get(input.size()-1)));
    }
}

//Output of above code
341

Question referenced from geeksforgeeks
Comments are welcome.

No comments:

Post a Comment