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 HashMapVarMap; 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