Here is a fully working Java solution for evaluation of Reverse Polish Notation (Postfix Expression). This is a common interview question that is asked in Google, Yahoo and Facebook. Solution Java class doesn’t have a main() method. You can write a main() method and call evalRPN() method from there. Input argument to evalRPN() method should be a String ArrayList with valid Postfix expression.
Sample input: [“6”, “1”, “-“, “3”, “*”]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
import java.util.*; import java.lang.*; import java.io.*;
class Solution { public int evalRPN(ArrayList<String> A) { Stack<Integer> stack = new Stack<Integer>(); for(String a : A){ Integer current = null; //check if current value is operand try{ current = Integer.parseInt(a); } catch(NumberFormatException e){ } if(current != null){ stack.push(current); } else{ // find last two operands int operand2 = stack.pop(); int operand1 = stack.pop(); //apply current operator on these operands int value = calculate(operand1, operand2, a); stack.push(value); } } return stack.pop(); } private int calculate(int operand1, int operand2, String a){ int result = 0; if(a.equals("+")){ result = operand1 + operand2; } else if(a.equals("-")){ result = operand1 - operand2; } else if(a.equals("*")){ result = operand1 * operand2; } else if(a.equals("/")){ result = operand1 / operand2; } return result; } }
|