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);

```
    }
```
```
}
```

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-

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube

If you wish to look at all Java Programming examples, go to Java Programs.

« Prev - Extended Euclidean Algorithm in Java

» Next - Java Program to Implement Kadane’s Algorithm

Next Steps:

Get Free Certificate of Merit in Java Programming
Participate in Java Programming Certification Contest
Become a Top Ranker in Java Programming
Take Java Programming Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Apply for Information Technology Internship
Practice Information Technology MCQs
Buy Java Books
Practice Programming MCQs
Buy Programming Books

Recommended Articles: