Postfix notation represents a algebraic expression.
These are evaluated faster than infix notation, as ( ) are not required.
Algorithm - using Stack
- For each element in postfix string
- if element is an operand
- push element into Stack => Operand
- else // Operator
- Pop from Stack => Operand 1
- Pop from Stack => Operand 2
- Evaluate value using both operands and element (Operator) => value
- Push the value to Stack
- Pop the element of Stack => Final result
Example
String postfix = "2
3 1 * + 9 -"
|
element
|
oprnd1
|
oprnd2
|
value
|
stack
|
|
2
|
|
|
|
2
|
|
3
|
|
|
|
2,3
|
|
1
|
|
|
|
2,3,1
|
|
*
|
3
|
1
|
3*1
|
2,3
|
|
+
|
3
|
2
|
3+2
|
5
|
|
9
|
|
|
|
5,9
|
|
-
|
5
|
9
|
5-9
|
-4
|
Java code
public static int evaluatePostfix(String postfixStr) {
String[] postfixArr = postfixStr.split("");
Stack<Integer> stack = new Stack<Integer>();
for(String element : postfixArr) {
boolean isOperator = isOperator(element);
if(isOperator) {
int value1 = stack.pop();
int value2 = stack.pop();
int value = calculate(value2, value1, element);
stack.push(value);
else {
stack.push(Integer.valueOf(element));
}
}int value = calculate(value2, value1, element);
stack.push(value);
else {
stack.push(Integer.valueOf(element));
}
return stack.pop();
}
private static int calculate(int a, int b, String operator){
int result = 0;
if("+".equals(operator)) {
result = (a+b);
else if("-".equals(operator)) {
result = (a-b);
else if("*".equals(operator)) {
result = (a*b);
result = (a*b);
else if("/".equals(operator)) {
result = (a/b);
result = (a/b);
return result;
private static boolean isOperator(String element) {
if("+".equals(element) || "-".equals(element)
|| "/".equals(element) || "*".equals(element)) {
return true;
}
return false;
}
