Arithmetic Evaluator (Postfix Evaluator)

Introduction

Evaluation of arithmetic expression is a basic functionalities of programming languages. The algorithm is usually taught in school but few programmers will implement an arithmetic evaluator on themselves after they left school. It is used to be an assignments for students who study computer science, especially for those who are studying compiler theory.

This article doesn't encourage homework copying. Anyway, it doesn't hurt to have a look at other people implementation.

Postfix expression

Normally, we write an arithmetic expression in the so called "infix form", meaning that the operator is in the middle of the two operands. For example : 3 + 5

We can always rewrite the expression into the postfix form, such that the operator come after the operands. Some samples are shown below :

Infix form               Postfix form
  3 + 5                    3 5 +
  12 * 5                   12 5 *
  4 + 7 - 8                4 7 + 8 -
  4 + 7 * 8                4 7 8 * +
  ( 4 + 7 ) * 8            4 7 + 8 *

Stack based evaluator

The postfix forms have many desirable properties for a computer evaluator. Firstly, it doesn't require parenthesis and there is no ambiguity of evaluation precedence. The implementation is straight forward. With the help of a stack, we can scan the postfix expression from left to right and store the intermediate result back to the stack.

For example, the following are the steps in evaluating the expression : 24 7 + 6 *

1. Read the next token, which is 24. It is an operand and we push it to the operand stack.
2. Read the next token, which is 7. This is another operand and we push it to the operand stack
3. Read the next token, which is a plus sign, this is an operator and we need two operands now.
   So we pop two operands from the stack, apply the "plus operator", then push the result back to the stack. Now the stack will contains the number 31.
   
4. Read the next token, which is 6. This is an operand and we push it to the operand stack.
   Now the stack contains 31 and 6
5. Read the next token, which is a multiplication operator. We pop two operands from the stack and apply the operator. 31 and 6 are popped out and they are multiplied together, the result is pushed back to the stack. Now the stack contains 186.
6. There are no more tokens and the evaluation is complete, just pop the result from the stack

To summarize, whenever the next token is an operand, we push it to the stack. Whenever the next token is an operator, we pop two operands from the stack, apply the operator, then push the result back to the stack.

Simple Implementation

The above example leads directly to the following straight forward implementations.

// Stack base postfix evaluator
  public static double evaluate(String postfix)
  {
    java.util.Stack<String> stack=new java.util.Stack<String>();

    java.util.StringTokenizer st = new java.util.StringTokenizer(postfix);
    while (st.hasMoreTokens())
    {
      String token=st.nextToken();
      if (isOperand(token))
      {
        stack.push(token);
      }
      if (isOperator(token))
      {
        String operand2=stack.pop();
        String operand1=stack.pop();
        String value=applyOperator(operand1,operand2,token);
        stack.push(value);
      }
    }
    
    String result = stack.pop();
    return Double.parseDouble(result);
  }

Full Runnable Demo

The following is a sample program that evaluates this postfix expression :

5 6 2 + * 12 4 / - 

The expression is defined in the variable postfix in the main() method. You may change it to another expression if you wish.
Note that all tokens are separated by spaces which not only enhances readability but also simplifies the implementation. It is because java provides a built in StringTokenizer which can loop through all tokens with ease.

/******************************************************************************
* File : PostfixEvaluator.java
* Author : http://java.macteki.com/
* Description :
*   Evaluate a postfix expression. 
* Tested with : JDK 1.6
******************************************************************************/

class PostfixEvaluator
{
  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 token)
  {
    String tokenList="+-*/";
    if (tokenList.indexOf(token)>=0) return true;
    return false;
  }

  public static String applyOperator(String operand1, String operand2, String operator)
  {
    double value1=Double.parseDouble(operand1);
    double value2=Double.parseDouble(operand2);
    double result=0;

    if (operator.equals("+"))
    {
      result=value1+value2;
    }
    else if (operator.equals("-"))
    {
      result=value1-value2;
    }
    else if (operator.equals("*"))
    {
      result=value1*value2;
    }
    else if (operator.equals("/"))
    {
      result=value1/value2;
    }

    return ""+result;  // convert result to String
  }

  public static double evaluate(String postfix)
  {
    java.util.Stack<String> stack=new java.util.Stack<String>();

    java.util.StringTokenizer st = new java.util.StringTokenizer(postfix);
    while (st.hasMoreTokens())
    {
      String token=st.nextToken();
      if (isOperand(token))
      {
        stack.push(token);
      }
      if (isOperator(token))
      {
        String operand2=stack.pop();
        String operand1=stack.pop();
        String value=applyOperator(operand1,operand2,token);
        stack.push(value);
      }
    }
    
    String result = stack.pop();
    return Double.parseDouble(result);
  }

  public static void main(String[] args) throws Exception
  {
    String postfix = "5 6 2 + * 12 4 / - ";   // change this line as needed
    double result=evaluate(postfix);
    System.out.println("evaluate["+postfix+"]="+result);
  }
}

Further works

We now have a evaluator for the postfix expression. We are obviously missing a class that converts the infix expression into the postfix expression, which will be presented in future articles.