[ Data Structures with Java ] Section 14.4 : Postfix Expressions

Preface :
Electronic calculators illustrate one of the primary application of a stack. The user enters a mathematical expression by pressing a sequence of numbers (operands) and operators, followed by the '=' key. The calculator computes and displays the result. The process assumes that the user enters the expression in a specific expression format. For instance, an integer expression such as :
-8 + (4*12 + 5%2)/3

contains operands (8,4,12,5,2,3), a unary operator (-), binary operators (+,%,*,/), and parentheses that create subexpressions. The operators are termed unary and binary because they require one or two operands respectively. We say the expression is in infix format because each binary operator appears between its operands and each unary operator precedes its operand. Infix is the most common format for writing expressions and is the expression format of choice for most programming languages and calculators.
Some calculators allow an alternative postfix format, where an operator comes after its operands. The format is also called RPN or Reverse Polish Notation. The term Polish refers to the fact that the notation was developed by the Polish mathematician. The infix expression "a+b" has the equivalent postfix form "ab+". With postfix format, an operator appears in the expression as soon as its two operands are available. To understand how this rule applies, consider the translation of the following infix expression to posfix :
1. Infix: a+ b*c > Postfix: abc*+

Because * has higher precedence than +, the evaluation of b*c must come first. The operator + has operands a and b*c. The evaluation of + appears only after we identify the two operands a and bc*.

2. Infix: (a+b)*c > Postfix: ab+c*

The parentheses create the subexpression "ab+" as the left hand operand for the operator *. The operator * appears only after we identify the right-hand operand c.

3. Infix: (a*b+c)/d + e > Postfix: ab*c+d/e+

The subexpression is "ab*c+". Division (/) is the next operator and appears immediately after the operand d. The result after division is the left-hand operand for operator +, which immediately follows its righ-hand operator e.

We can summarize the conversion from infix to postfix with two simple rules :

Rule1 : Scan the infix expression from left to right. Immediately record an operand in the postfix expression as soon as it is identified.
Rule2 : Record an operator as soon as its operands are identified. We will discuss this rule in detail in Section 14.5 when we will develop an algorithm to convert an infix expression to a postfix expression. This algorithm involves interpreting parentheses (subexpression), operator precedence, and associativity.

Postfix Evaluation :
With an expression in postfix format, we can use a simple algorithm to evaluate the result. The algorithm scans each term of the expression from left to right and uses a stack to hold the operands. If a term is an operand, push it onto the stack. If the term is a binary operator, we can evaluate its result because its two operands already reside on the stack in the top two positions. To carry out the evaluation of the operator, pop the stack twice to retrieve the operands, evaluate the expression, and then push the result back onto the stack. After processing all of the terms in the expression, there will be a single value on the top of the stack, which is the result. Consider the expression "4 3 5 * +". Evaluating it requires five steps :


The PostfixEval Class :
We can design a class, PostfixEval, which takes a postfix expression and evaluates it. We assume the operands are single-digit nonnegative integers. This simplifies the process of distinguishing between an operator and an operand. The class handles the standard binary integer operators +, -, *, / and %. In addition, the class evaluates expression contains the binary exponentiation operator ^, which takes two operands, a and b, and computes a^b.
The PostfixEval class contains a default constructor that creates an instance without a specified postfix expression to evaluation. The expression is introduced by the method setPostfixExp(), which takes a string argument containing the postfix expression. The access method getPostfixExp() enables a programmer to retrieve the current expression. The key method, evaluate(), attempts to compute the value of the postfix expression. If successful, it returns the value of the expression. If the expression contains an error, the method throws an ArithmeticException. If desired, the calling block can catch the exception and output the error message that is created when the evaluation process identifies an error. A series of private methods, compute(), getOperand() and isOperator() are used by evaluate() to identify operators and to compute the result for an arithmetic operation :

- Class PostfixEval Implementation :

view plaincopy to clipboardprint?

1. package DSwJ.S14;  
2.   
3. import java.util.Scanner;  
4.   
5. public class PostfixEval {  
6.     private String postfixExpression;  
7.     private ALStack operandStack;  
8.     private String operators = "+-*/^";  
9.       
10.     public PostfixEval(){  
11.         operandStack = new ALStack();  
12.     }  
13.     public PostfixEval(String expr) {  
14.         this();  
15.         postfixExpression = expr;         
16.     }  
17.       
18.     public int compute(int right, int left, char op){  
19.         int result=0;  
20.         switch(op) {  
21.         case '+':  
22.             result =  left+right;  
23.             System.out.println("\t"+left+"+"+right+"="+result);  
24.             break;  
25.         case '-':  
26.             result =  left-right;  
27.             System.out.println("\t"+left+"-"+right+"="+result);  
28.             break;  
29.         case '*':  
30.             result =  left*right;  
31.             System.out.println("\t"+left+"*"+right+"="+result);  
32.             break;  
33.         case '%':  
34.             if(right==0) throw new ArithmeticException("Divide by 0!!!");  
35.             result = left%right;  
36.             System.out.println("\t"+left+"%"+right+"="+result);  
37.             break;  
38.         case '/':         
39.             if(right==0) throw new ArithmeticException("Divide by 0!!!");  
40.             result =  left/right;  
41.             System.out.println("\t"+left+"/"+right+"="+result);  
42.             break;  
43.         case '^':  
44.             if(right==0 && left==0) if(right==0) throw new ArithmeticException("No definition of 0^0!!!");  
45.             if(right==0) result =  1;  
46.             else {  
47.                 int tmp=1;  
48.                 for(int i=1; i<=right; i++) tmp*=left;  
49.                 result =  tmp;  
50.             }             
51.             System.out.println("\t"+left+"^"+right+"="+result);  
52.             break;  
53.         }  
54.         operandStack.push(result);  
55.         return result;  
56.     }  
57.       
58.     public int evaluate(){  
59.         int index=0;  
60.         char curPos;  
61.         while(index
62.             curPos = postfixExpression.charAt(index);  
63.             if(Character.isWhitespace(curPos)) continue;  
64.             System.out.println("\tDeal "+curPos);  
65.             if(isOperator(curPos)) {  
66.                 compute(getOperand(), getOperand(), curPos);  
67.             } else {  
68.                 if(Character.isDigit(curPos)){  
69.                     operandStack.push(new Integer(new Character(curPos).toString()));  
70.                 } else {  
71.                     throw new ArithmeticException("Illegal operand("+curPos+")!!!");  
72.                 }  
73.             }  
74.             index++;  
75.         }  
76.         if(operandStack.size()==1) return operandStack.pop();  
77.         else {  
78.             operandStack.clear();  
79.             throw new ArithmeticException("Short of operator!!!");  
80.         }  
81.     }  
82.       
83.     public int getOperand() {  
84.         if(!operandStack.isEmpty()) return operandStack.pop();  
85.         throw new ArithmeticException("Short of operand!!!");  
86.     }  
87.       
88.     public String getPostfixExp(){return postfixExpression;}  
89.     public boolean isOperator(char op) {  
90.         return operators.indexOf(op)>=0;  
91.     }  
92.     public void setPostfixExp(String postfixExp) {  
93.         postfixExpression = postfixExp;  
94.     }  
95. }  

Program 14.3 : Evaluating a Postfix Expression
The program evaluates a postfix expression. After prompting, the program reads an expression from the keyboard and assign it to the PostfixEval objectpostfixExp using the method setPostfixExp(). Enclose the call to evaluate() in a try block in case an error occurs :

- Demo of class PostfixEval :

view plaincopy to clipboardprint?

1. public static main(){  
2.     // 25+3*83/-  
3.     PostfixEval exp = new PostfixEval();  
4.     String rpnExp;  
5.     Scanner keyIn = new Scanner(System.in);  
6.     System.out.print("Enter the postfix expression: ");  
7.     rpnExp = keyIn.nextLine();  
8.     exp.setPostfixExp(rpnExp);  
9.     try{  
10.         System.out.println("The value of the expression= "+exp.evaluate());  
11.     }catch(ArithmeticException ex) {  
12.         ex.printStackTrace();  
13.     }  
14. }  

Result :
Enter the postfix expression: 25+3*83/- 
Deal 2
Deal 5
Deal +
2+5=7
Deal 3
Deal *
7*3=21
Deal 8
Deal 3
Deal /
8/3=2
Deal -
21-2=19
The value of the expression= 19

This message was edited 3 times. Last update was at 09/10/2010 14:37:59