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-
Related posts:
Java Program to Find Maximum Element in an Array using Binary Search
Java Switch Statement
Java Program to Implement Regular Falsi Algorithm
Java Program to Perform Uniform Binary Search
Hướng dẫn Java Design Pattern – Null Object
Spring Boot - Scheduling
Java Program to Implement CopyOnWriteArraySet API
A Guide to the finalize Method in Java
Exploring the New Spring Cloud Gateway
Java Program to Implement a Binary Search Tree using Linked Lists
Java Program to Check whether Directed Graph is Connected using DFS
Java Program to Generate Date Between Given Range
Implementing a Runnable vs Extending a Thread
Java Streams vs Vavr Streams
Spring Security OAuth Login with WebFlux
Java Program to Implement Ternary Search Algorithm
Encode/Decode to/from Base64
Java Program to Solve the 0-1 Knapsack Problem
Setting the Java Version in Maven
Java Program to Implement Hash Tables Chaining with Binary Trees
Partition a List in Java
Cơ chế Upcasting và Downcasting trong java
How to Read a File in Java
Jackson vs Gson
Java Program to Use the Bellman-Ford Algorithm to Find the Shortest Path
Java Program to Implement Floyd Cycle Algorithm
Luồng Daemon (Daemon Thread) trong Java
Java Program to Perform Postorder Recursive Traversal of a Given Binary Tree
Java Program to Implement Booth Algorithm
Jackson – Bidirectional Relationships
Java Program to Implement Horner Algorithm
Read an Outlook MSG file