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.

  1. /**
  2.  ** Java Program to Implement Shunting Yard Algorithm
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class ShuntingYard **/
  8. public class ShuntingYard
  9. {
  10.     /** enum **/
  11.     private enum Precedence
  12.     {
  13.         lparen(0), rparen(1), plus(2), minus(3), divide(4), times(5), mod(6), eos(7), operand(8);
  14.  
  15.         private int index;
  16.         Precedence(int index)
  17.         {
  18.             this.index = index;
  19.         }
  20.         public int getIndex()
  21.         {
  22.             return index;
  23.         }        
  24.     } 
  25.     /** in stack precedence **/
  26.     private static final int[] isp = {0, 19, 12, 12, 13, 13, 13, 0};
  27.     /** incoming character precedence **/
  28.     private static final int[] icp = {20, 19, 12, 12, 13, 13, 13, 0};
  29.     /** operators **/
  30.     private static final char[] operators = {'{', '}', '+', '-', '/', '*', '%', ' '};
  31.     /** precedence stack **/
  32.     private Precedence[] stack; 
  33.     /** stack top pointer **/
  34.     private int top;
  35.  
  36.     /** pop element from stack **/
  37.     private Precedence pop()
  38.     {
  39.         return stack[top--];
  40.     }
  41.     /** push element onto stack **/
  42.     private void push(Precedence ele)
  43.     {
  44.         stack[++top] = ele;
  45.     }
  46.     /** get precedence token for symbol **/
  47.     public Precedence getToken(char symbol)
  48.     {
  49.         switch (symbol)
  50.         {
  51.         case '('  : return Precedence.lparen;
  52.         case ')'  : return Precedence.rparen;
  53.         case '+'  : return Precedence.plus;
  54.         case '-'  : return Precedence.minus;
  55.         case '/'  : return Precedence.divide;
  56.         case '*'  : return Precedence.times;
  57.         case '%'  : return Precedence.mod;
  58.         case ' '  : return Precedence.eos;
  59.         default   : return Precedence.operand;
  60.         }
  61.     }
  62.  
  63.     /** Function to convert infix to postfix **/
  64.     public String postfix(String infix)
  65.     {
  66.         String postfix = "";
  67.         top = 0;
  68.         stack = new Precedence[infix.length()];
  69.         stack[0] = Precedence.eos;
  70.         Precedence token;
  71.         for (int i = 0; i < infix.length(); i++)
  72.         {
  73.             token = getToken(infix.charAt(i));
  74.             /** if token is operand append to postfix **/
  75.             if (token == Precedence.operand)
  76.                 postfix = postfix + infix.charAt(i);
  77.             /** if token is right parenthesis pop till matching left parenthesis **/
  78.             else if (token == Precedence.rparen)
  79.             {
  80.                 while (stack[top] != Precedence.lparen)
  81.                     postfix = postfix + operators[pop().getIndex()];
  82.                 /** discard left parenthesis **/
  83.                 pop();
  84.             }
  85.             /** else pop stack elements whose precedence is greater than that of token **/
  86.             else
  87.             {
  88.                 while (isp[stack[top].getIndex()] >= icp[token.getIndex()])
  89.                     postfix = postfix + operators[pop().getIndex()];
  90.                 push(token);
  91.             }
  92.         }
  93.         /** pop any remaining elements in stack **/
  94.         while ((token = pop()) != Precedence.eos)
  95.             postfix = postfix + operators[token.getIndex()];
  96.  
  97.         return postfix;
  98.     }
  99.     /** Main function **/
  100.     public static void main (String[] args) 
  101.     {
  102.         Scanner scan = new Scanner(System.in);
  103.         System.out.println("Shunting Yard Algorithm Test\n");
  104.         /** Make an object of ShuntingYard class **/
  105.         ShuntingYard sy = new ShuntingYard();
  106.  
  107.         /** Accept infix expression **/
  108.         System.out.println("Enter infix expression");
  109.         String infix = scan.next();
  110.  
  111.         String postfix = sy.postfix(infix);
  112.         System.out.println("\nPostfix expression : "+ postfix);
  113.     }
  114. }

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.

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

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.