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:
Guava CharMatcher
Convert XML to JSON Using Jackson
Java Program to Perform Finite State Automaton based Search
Java Program to Implement Interpolation Search Algorithm
Java Map With Case-Insensitive Keys
JWT – Token-based Authentication trong Jersey 2.x
Java Program to Implement Max Heap
Spring Cloud AWS – Messaging Support
Daemon Threads in Java
Java Program to Find the Mode in a Data Set
Filtering a Stream of Optionals in Java
Java Program to Use Dynamic Programming to Solve Approximate String Matching
Java Program to Optimize Wire Length in Electrical Circuit
Giới thiệu Java 8
Jackson – Decide What Fields Get Serialized/Deserialized
Java Program to Compute Cross Product of Two Vectors
Guide to CountDownLatch in Java
Java Program to Perform integer Partition for a Specific Case
Mapping Nested Values with Jackson
Java Program to find the peak element of an array using Binary Search approach
Guide to Java 8’s Collectors
A Quick JUnit vs TestNG Comparison
Java Program to Implement Johnson’s Algorithm
Serverless Functions with Spring Cloud Function
Database Migrations with Flyway
Java – Reader to Byte Array
Tính đóng gói (Encapsulation) trong java
Simultaneous Spring WebClient Calls
Java InputStream to String
Java Program to Describe the Representation of Graph using Incidence Matrix
Java Program to Find All Pairs Shortest Path
Java Program to implement Bi Directional Map