Java Program to Implement Shunting Yard Algorithm

This is a Java Program to Implement Shunting Yard Algorithm. Shunting Yard algorithm is used for converting an infix expression into a postfix expression.

Here is the source code of the Java Program to Implement Shunting Yard Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
 ** Java Program to Implement Shunting Yard Algorithm
 **/
 
import java.util.Scanner;
 
/** Class ShuntingYard **/
public class ShuntingYard
{
    /** enum **/
    private enum Precedence
    {
        lparen(0), rparen(1), plus(2), minus(3), divide(4), times(5), mod(6), eos(7), operand(8);
 
        private int index;
        Precedence(int index)
        {
            this.index = index;
        }
        public int getIndex()
        {
            return index;
        }        
    } 
    /** in stack precedence **/
    private static final int[] isp = {0, 19, 12, 12, 13, 13, 13, 0};
    /** incoming character precedence **/
    private static final int[] icp = {20, 19, 12, 12, 13, 13, 13, 0};
    /** operators **/
    private static final char[] operators = {'{', '}', '+', '-', '/', '*', '%', ' '};
    /** precedence stack **/
    private Precedence[] stack; 
    /** stack top pointer **/
    private int top;
 
    /** pop element from stack **/
    private Precedence pop()
    {
        return stack[top--];
    }
    /** push element onto stack **/
    private void push(Precedence ele)
    {
        stack[++top] = ele;
    }
    /** get precedence token for symbol **/
    public Precedence getToken(char symbol)
    {
        switch (symbol)
        {
        case '('  : return Precedence.lparen;
        case ')'  : return Precedence.rparen;
        case '+'  : return Precedence.plus;
        case '-'  : return Precedence.minus;
        case '/'  : return Precedence.divide;
        case '*'  : return Precedence.times;
        case '%'  : return Precedence.mod;
        case ' '  : return Precedence.eos;
        default   : return Precedence.operand;
        }
    }
 
    /** Function to convert infix to postfix **/
    public String postfix(String infix)
    {
        String postfix = "";
        top = 0;
        stack = new Precedence[infix.length()];
        stack[0] = Precedence.eos;
        Precedence token;
        for (int i = 0; i < infix.length(); i++)
        {
            token = getToken(infix.charAt(i));
            /** if token is operand append to postfix **/
            if (token == Precedence.operand)
                postfix = postfix + infix.charAt(i);
            /** if token is right parenthesis pop till matching left parenthesis **/
            else if (token == Precedence.rparen)
            {
                while (stack[top] != Precedence.lparen)
                    postfix = postfix + operators[pop().getIndex()];
                /** discard left parenthesis **/
                pop();
            }
            /** else pop stack elements whose precedence is greater than that of token **/
            else
            {
                while (isp[stack[top].getIndex()] >= icp[token.getIndex()])
                    postfix = postfix + operators[pop().getIndex()];
                push(token);
            }
        }
        /** pop any remaining elements in stack **/
        while ((token = pop()) != Precedence.eos)
            postfix = postfix + operators[token.getIndex()];
 
        return postfix;
    }
    /** Main function **/
    public static void main (String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Shunting Yard Algorithm Test\n");
        /** Make an object of ShuntingYard class **/
        ShuntingYard sy = new ShuntingYard();
 
        /** Accept infix expression **/
        System.out.println("Enter infix expression");
        String infix = scan.next();
 
        String postfix = sy.postfix(infix);
        System.out.println("\nPostfix expression : "+ postfix);
    }
}

Output:

Shunting Yard Algorithm Test
 
Enter infix expression
1+2*3/4-5%6*7/8+9-1
 
Postfix expression : 123*4/+56%7*8/-9+1-