[ Data Structures with Java ] Section 14.5 : Infix Expression Evaluation

Preface : 
Section 14.4 discuss the use of a stack for postfix expression evaluation. These expression are relatively easy to evaluate because they don't contain subexpression and already account for precedence among operators. In addition, the algorithm requires only a single stack that stores operands. Unfortunately, postfix expressions have limited application. Most electronic calculators and programming languages assume expression are entered with infix notation rather than postfix notation. Evaluation of an infix expression is more difficult. the algorithm must have a strategy to handle subexpressions and must maintain the order of precedence and associativity for operators. For instance, in the expression : 
9 + (2 - 3) * 8 

we evaluate the subexpression (2-3) first and then use the result as the left operand for *. The operator * execute before the + operator because it has higher precedence. There are two approaches to infix expression evaluation. One approach scans the infix expression and uses separate operator and operand stacks to store the terms. The algorithm produces the result directly. A second approach converts the infix expression to its equivalent postfix expression and then calls the postfix expression evaluator from previous section to compute the result. In this section, we will discussion the second approach. 

Infix Expression Attributes : 
Infix expressions consist of operands, operators and pairs of parentheses that create subexpression, which are computed separately. There is an order of precedence and associativity among operators. The order of precedence dictates that you evaluate the operators with highest precedence first. Among arithmetic operators, the additive operator (+,-) have the lowest precedence; next are the multiplicative operators (*,/,%). The exponentiation operator (^) has the highest precedence. The concept of associativity refers to the order of execution for operators at the same precedence level. If more than one operator has the same precedence, the leftmost operator executes first in the case of left associativity (+,-,*,/,%) and the righmost operator executes first in the case of right associativity (^). A few examples will clarify the difference between left and right associativity. 
The operators * and / have the same order of precedence and are left associativity. In the following expression, compute the successive products and then evaluate the quotient : 
7*2*4/5 Evaluate: ((7*2)*4)/5 = (14*4)/5 = 56/5 = 11 

The exponentiation operator ^, is the right-associative. The following expression involves two successive ^ operations. Compute with the rightmost operator 3^2 = 9 and use the result as the exponent with the leftmost operator 2^9=512 : 
2^3^2 Evaluate: (2^(3^2)) = 2^9 = 512 

Infix-to-Postfix Conversion : 
The infix-to-postfix conversion algorithm takes an infix expression as input string and returns the corresponding postfix expression as output string. The algorithm has some similarities with the postfix evaluation algorithm. Both scan the expression looking for operands and operators and use a stack to store elements. Postfix evaluation copies operands to a stack and does calculations when an operator is found. The infix-to-postfix conversion algorithm copies operands to the output string and use a stack to store and process operators and the left-parenthesis symbol. You must understand how the operator stack works to appreciate the algorithm because it manages the order of precedence and associativity of operators as well as handling subexpression. 
We will use a series of examples to expose the issue. Each example introduces a new concept that details how the stack handles operators. By tracing the scan of the infix expression, you will know how the stack is involved in the solution. 
Example 1: Infix Expression a + b *c 

This example illustrates how the stack temporarily stores operators awaiting their right-hand side operand. Scan the operand, and immediately write it to the postfix string. The next term is operator +, which cannot be written to the postfix string until the scan identifies its right-hand operand. Push + on an operator stack and proceed (Blk 1). Scan the operand b and write it to the postfix string. We next find the operator *, which has higher precedence than +, and hence must appear in the final postfix expression before +. Push * on the stack, which has the effect of driving the + operator with lower precedence further down in the stack (Blk 2). Read operand c and write it to the postfix string. After completing the scan of the expression, clear the stack and write the operators to the output string. The operators are released in the order * followed by +, which is the order of their precedence. The result is the postfix string "abc*+".

Example 2: Infix Expression a * b / c + d 

This example illustrates how to use the stack to handle operators that have the same or lower precedence. Scan the first three terms, writing operands a and b to the postfix string and pushing operator * on the stack(Blk1). The next item is operator /, which has the same precedence as * but will execute after *. In the postfix string, * must come before /. Accomplish this by ensuring that no operator enters the stack until all of the prior operators with the same or higher precedence have been removed. Pop the operator * and copy it to the postfix string (Blk2). After scan lower precedence than / on the stack. Pop the / and then push + on the stack (Blk3). Complete the scan with the operand d and then remove the operator + from the stack (Blk4). The resulting postfix expression is "ab*c/d+"

Example 3: Infix Expression a^b^c 

This example illustrates how to use precedence values to handle the exponential operator ^, which is right associative. This implies we must evaluate the expression b^c first and use the result as the right operand of a (a^). Handling the second ^ operator is the problem. After reading the symbols a^b, the operands a and b are in the postfix string and the operator ^ is on the stack (Blk1). We must next deal with the second ^ operator. So we have operator ^ has higher precedence outside the stack than the operator ^ which already in the stack. So the resulting postfix expression is "abc^^":

Example 4: Infix Expression a * (b + c) 

This example illustrates how to handle the left and the right parentheses that set off a subexpression. It must be handled like a separate infix expression with the main difference that the subexpression is converted to postfix expression when we scan the right parenthesis ")" that corresponds to its left parenthesis "(". For how to, please refer to below sample code which implements the functionality we talk as far.

- ALStack.java : General version of stack which used to store operators.

view plaincopy to clipboardprint?

1. package DSwJ.S14;  
2.   
3. import java.util.ArrayList;  
4.   
5. public class ALStack implements Stack{  
6.     private ArrayList stackList = null;  
7.       
8.     public ALStack() {  
9.         stackList = new ArrayList();  
10.     }  
11.   
12.     public void clear(){stackList.clear();}  
13.       
14.     @Override  
15.     public T peek() {  
16.         if(stackList.size()==0) throw new EmptyStackException("Empty Stack");  
17.         return stackList.get(stackList.size()-1);  
18.     }  
19.   
20.     @Override  
21.     public T pop() {  
22.         if(stackList.size()==0) throw new EmptyStackException("Empty Stack");  
23.         return stackList.remove(stackList.size()-1);  
24.     }  
25.   
26.     @Override  
27.     public void push(T item) {  
28.         stackList.add(item);          
29.     }  
30.       
31.     @Override  
32.     public int size() {  
33.         return stackList.size();  
34.     }  
35.       
36.     @Override  
37.     public boolean isEmpty() {  
38.         return stackList.isEmpty();  
39.     }  
40.       
41.     public static void main(String args[]) {  
42.         exam14_1();  
43.     }  
44.       
45.     public static void exam14_1(){  
46.         ALStack stk = new ALStack();  
47.         for(int i=1; i<=5; i++)  
48.             stk.push(i);  
49.         System.out.println("Stack size= "+stk.size());  
50.         System.out.println("Poping the stack: ");  
51.         while(!stk.isEmpty()){  
52.             System.out.print(stk.pop()+" ");  
53.         }  
54.     }     
55. }  

- EOperator.java : Enumeration of operators

view plaincopy to clipboardprint?

1. package DSwJ.S14.operators;  
2.   
3. public enum EOperator {  
4.     OperPlus(1,'+'),OperMinus(1,'-'),OperMulti(2,'*'),OperDivide(2,'/'), OperRemider(2,'%'),  
5.     OperLev(4,'^'),OperLevInStack(3,'^');  
6.     private int precedience;  
7.     private char operator;  
8.       
9.     private EOperator(int p, char op) {precedience = p; operator=op;}  
10.       
11.     public boolean preOrEqual(EOperator ope) {  
12.         //System.out.println("[Test]"+getPre()+" with "+ope.getPre());  
13.         if(getPre()>=ope.getPre()) return true;  
14.         return false;  
15.     }  
16.       
17.     public EOperator inStack(){  
18.         if(this.equals(EOperator.OperLev)) {  
19.             return EOperator.OperLevInStack;              
20.         }  
21.         return this;  
22.     }  
23.     public char operator(){return operator;}  
24.     public int getPre(){return precedience;}  
25.     public static EOperator transfer(char c) {  
26.         switch(c) {  
27.         case '+':  
28.             return EOperator.OperPlus;  
29.         case '-':  
30.             return EOperator.OperMinus;  
31.         case '*':  
32.             return EOperator.OperMulti;  
33.         case '/':  
34.             return EOperator.OperDivide;  
35.         case '%':  
36.             return EOperator.OperRemider;  
37.         case '^':  
38.             return EOperator.OperLev;  
39.         }  
40.         return null;  
41.     }  
42. }  

- InfixToPostfix.java : Implementation of algorithm on transferring Infix-expression to Postfix-expression.

view plaincopy to clipboardprint?

1. package DSwJ.S14;  
2.   
3. import DSwJ.S14.operators.EOperator;  
4.   
5. public class InfixToPostfix {  
6.     private String infixExpression;  
7.     private String operators = "+-*/^";  
8.       
9.     public InfixToPostfix() {  
10.           
11.     }  
12.       
13.     public InfixToPostfix(String infixExp) {  
14.         infixExpression = infixExp;  
15.     }  
16.       
17.     public boolean isOperator(char op) {  
18.         return operators.indexOf(op)>=0;  
19.     }  
20.       
21.     public boolean isSubexpr(char op) {  
22.         if(op == '(') return true;  
23.         return false;  
24.     }  
25.       
26.     public String genPostfixExpr(){  
27.         return transferToPosfixExp(infixExpression);  
28.     }  
29.       
30.     protected String transferToPosfixExp(String expr){  
31.         StringBuffer postfixExp = new StringBuffer("");  
32.         ALStack operatorStack = new ALStack();  
33.         int index=0;  
34.         char curPos;  
35.         while(index
36.             curPos = expr.charAt(index);  
37.             if(Character.isWhitespace(curPos)) {  
38.                 index++;  
39.                 continue;  
40.             }  
41.             if(isOperator(curPos)) {  
42.                 EOperator operator = EOperator.transfer(curPos);  
43.                 if(operator!=null) {  
44.                     if(operatorStack.isEmpty()){  
45.                         operatorStack.push(operator.inStack());  
46.                     } else {  
47.                         if(operatorStack.peek().preOrEqual(operator)){  
48.                             postfixExp.append(operatorStack.pop().operator());  
49.                             operatorStack.push(operator.inStack());  
50.                         } else {  
51.                             operatorStack.push(operator.inStack());  
52.                         }  
53.                     }  
54.                 } else {  
55.                     throw new ArithmeticException("Illegal operator("+curPos+")!!!");  
56.                 }  
57.             } else if(isSubexpr(curPos)){  
58.                 int cnt = 1;  
59.                 int sindex = index+1;  
60.                 char ichar;  
61.                 while(cnt>0 && sindex
62.                     ichar = expr.charAt(sindex);  
63.                     if(ichar==')') cnt--;  
64.                     else if(ichar=='(') cnt++;  
65.                     sindex++;  
66.                 }  
67.                 if(cnt==0) {  
68.                     sindex--;  
69.                     String subExpr = expr.substring(index+1, sindex);                 
70.                     postfixExp.append(transferToPosfixExp(subExpr));                      
71.                     index = sindex;  
72.                 } else {  
73.                     throw new ArithmeticException("Not balanced expression!!!");  
74.                 }                 
75.             } else {  
76.                 postfixExp.append(curPos);  
77.             }  
78.             index++;  
79.         }  
80.         while(!operatorStack.isEmpty()){  
81.             postfixExp.append(operatorStack.pop().operator());  
82.         }  
83.         return postfixExp.toString();  
84.     }  
85.       
86.     public static void main(String args[]) {  
87.         //String infixExp = "a+b*c";  
88.         //String infixExp = "a*b/c+d*e";  
89.         //String infixExp = "a^b^c";  
90.         String infixExp = "a*((b+c)*e)";  
91.         System.out.println("Infix expre: "+infixExp);  
92.         InfixToPostfix infixToPostfix = new InfixToPostfix(infixExp);   
93.         try{  
94.             System.out.println("Postfix expr: "+infixToPostfix.genPostfixExpr());  
95.         }catch(ArithmeticException e){  
96.             e.printStackTrace();  
97.         }  
98.     }  
99. }