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