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
infix postfix 3 + 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 :
3 5 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.
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 is"3 2"and the stack contains a plus sign
- 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 is"3 2 +"and the stack contains a minus sign
- Read the next token, it is "1" which is an operand, hence append it to the postfix.
Now the postfix is"3 2 + 1"and the stack contains a minus sign.
- 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 -"
2. 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
And finally we add rule number 3 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