### Previous Work

In the previous article, Postfix Evaluator, it is shown that if we rewrite an arithmetic expression into the postfix form, then we can implement an arithmetic evaluator with simple algorithm. However, we used to write arithmetic expression in infix form. Therefore we must first convert the infix form into the postfix form in order to have a more complete evaluator.### Infix to Postfix, manual conversion

infixpostfix3 + 5 3 5 + 3 + 5 - 2 3 5 + 2 - 3 + 5 * 2 3 5 2 * + ( 3 + 5 ) * 2 3 5 + 2 *

Make sure you understand how the conversion is done, pay special attention to the third and the forth expression, they have different evaluation precedence.

It may help understanding how the conversion is done if we manually evaluate a postfix expression. A simplest postfix expression is of the form :

operand1 operand2 operatorExample :

3 5 +Whenever we see such a simple form in a more complex expression, we can substitute it with the calculated result. For example, we can substitute the above expression with 8.

Now we go for a more complex example, to evaluate :

3 5 2 * +

### Evaluation by substitution

Underline a simple postfix expression :

35 2 *+

Since 5 * 2 = 10, we may now make a substitution :

3 10 +

Now we have another simple postfix expression, since 3+10=13, we make another substitution

13which is the desired result.

### Algorithm to convert Infix to Postfix

To convert the expression, we must divide it into tokens. In this case, a token is either an operand or an operator or a parenthesis sign.Have a look at the above four postfix examples, we can see that the order of operand is never changed during the conversion. Hence we have the first rule in conversion :

1. Whenever the next token is an operand, append it to the postfix expression.

1. Whenever the next token is an operand, append it to the postfix expression.

2. If the next token is an operator, push it to the stack.(Note : this rule need to be modified later)

2. If the next token is an operator, push it to the stack.(Note : this rule need to be modified later)

An obvious question is, when to pop out the operator ? Consider the following expression :

3 + 2 - 1

- Read the next token, it is "3" which is an operand, hence append it to the postfix.

- Read the next token, which is a plus sign, push it to the operator stack.

- Read the next token, it is "2" which is an operand, hence append it to the postfix.

Now the postfix isand the stack contains a plus sign`"3 2"`

- Read the next token, which is a minus sign, normally we should push it to the operator stack.

However, before doing so, we first examine the stack top element, we found a plus sign there, since a plus sign has the same evaluation precedence as the minus sign, we can safely pop out the plus sign now.

Now the postfix isand the stack contains a minus sign`"3 2 +"`

- Read the next token, it is "1" which is an operand, hence append it to the postfix.

Now the postfix isand the stack contains a minus sign.`"3 2 + 1"`

- There are no more token, pop out all the operator from the stack and append it to the postfix one by one.

The final result would become`"3 2 + 1 -"`

And finally we add rule number 32. If the next token is an operator then while stack is not empty if precedence(stack top operator) >= precedence(token) pop the stack top operator and append it to the postfix end if end while push the token operator to the stack end if

3. If there are no more tokens, pop all operators in the stack, and append them to the postfix one by one

### Algorithm

The above three rules are simple but they don't take care of parenthesis, a full algorithm is presented below :// algorithm : infix to postfix while (more token to read) read next token if (token is operand) append token to postfix if (token is left parenthesis) push token to stack if (token is operator) pop all operators with higher or equal precedence than token append those operators to postfix push token if (token is right parenthesis) pop all operators until left parenthesis append those operators to postfix end while // no more tokens pop all operators append those operators to postfix

### Implementation

// convert infix to postfix // straight forward implementation of the above algorithm public static String convert(String infix) { java.util.Stack<String> stack=new java.util.Stack<String>(); String postfix=""; String space=" "; java.util.StringTokenizer st=new java.util.StringTokenizer(infix); while (st.hasMoreTokens()) { String token=st.nextToken(); if (isOperand(token)) { postfix += token + space; } else if (token.equals("(")) { stack.push(token); } else if (isOperator(token)) { while (!stack.empty() && precedence(stack.peek())>=precedence(token)) { postfix += stack.pop() + space; } stack.push(token); } else if (token.equals(")")) { while (!stack.peek().equals("(")) { postfix += stack.pop() + space; } stack.pop(); // pop the left parenthesis } } while (!stack.empty()) { postfix += stack.pop() + space; } return postfix; }

### Demonstration

The following program will convert a infix expression into a postfix expression, then evaluate the value using the Evaluator in the previous article. You will need PostfixEvaluator.java in the previous article to run this demo. Note that we must use space to separate all tokens in the input String. Hence the input can be :String infix="( 6 + 2 ) * 5 - 8 / 4";But cannot be :

String infix="(6+2)*5-8/4";

This restriction will be removed in BNF tokenizer

/****************************************************************************** * File : PostfixConverter.java * Author : http://java.macteki.com/ * Description : * Convert infix to postfix * Tested with : JDK 1.6 ******************************************************************************/ class PostfixConverter { public static boolean isOperand(String s) { double a=0; try { a=Double.parseDouble(s); } catch (Exception ignore) { return false; } return true; } public static boolean isOperator(String s) { String operatorList="+-*/"; return operatorList.indexOf(s)>=0; } public static int precedence(String operator) { int precedence=0; if (operator.equals("+")) { precedence=1; } else if (operator.equals("-")) { precedence=1; } else if (operator.equals("*")) { precedence=2; } else if (operator.equals("/")) { precedence=2; } return precedence; } public static String convert(String infix) { java.util.Stack<String> stack=new java.util.Stack<String>(); String postfix=""; String space=" "; java.util.StringTokenizer st=new java.util.StringTokenizer(infix); while (st.hasMoreTokens()) { String token=st.nextToken(); if (isOperand(token)) { postfix += token + space; } else if (token.equals("(")) { stack.push(token); } else if (isOperator(token)) { while (!stack.empty() && precedence(stack.peek())>=precedence(token)) { postfix += stack.pop() + space; } stack.push(token); } else if (token.equals(")")) { while (!stack.peek().equals("(")) { postfix += stack.pop() + space; } stack.pop(); // pop the left parenthesis } } while (!stack.empty()) { postfix += stack.pop() + space; } return postfix; } public static void main(String[] args) throws Exception { String infix="( 6 + 2 ) * 5 - 8 / 4"; // change this line as needed String postfix=convert(infix); System.out.println("infix="+infix); System.out.println("postfix="+postfix); System.out.println("evaluation="+PostfixEvaluator.evaluate(postfix)); } }

### Result :

java PostfixConverter infix=( 6 + 2 ) * 5 - 8 / 4 postfix=6 2 + 5 * 8 4 / - evaluation=38.0

Very Nice

ReplyDeleteThanks for reading

Delete