Sunday, June 12, 2011

Arithmetic Evaluator (Infix to Postfix)

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 operator
Example :
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
13
which 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.

How about if we read an operator ? We can not append it to the postfix expression yet because we must have written two operands before writing an operator. We know that the next operand is coming hence we can save this operator to somewhere first. An operator stack is a ideal space.

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

  1. Read the next token, it is "3" which is an operand, hence append it to the postfix.
  2. Read the next token, which is a plus sign, push it to the operator stack.
  3. 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
  4. 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
  5. 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.
  6. 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 -"
Now we can modify rule number two :

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

2 comments: