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:
Lập trình hướng đối tượng (OOPs) trong java
Java Web Services – Jersey JAX-RS – REST và sử dụng REST API testing tools với Postman
Jackson – Change Name of Field
Spring Security Form Login
Java Program to Implement Fenwick Tree
Java Program to Implement Patricia Trie
Java Program to Implement Radix Sort
Converting String to Stream of chars
Java – Byte Array to Reader
Java Program to Implement Booth Algorithm
Java Program to Implement Ternary Tree
OAuth2 for a Spring REST API – Handle the Refresh Token in AngularJS
Java Program to Implement Binomial Tree
Java Optional as Return Type
Error Handling for REST with Spring
The Modulo Operator in Java
Hướng dẫn Java Design Pattern – Proxy
A Guide to JPA with Spring
A Custom Data Binder in Spring MVC
Java Program to Find the Minimum Element of a Rotated Sorted Array using Binary Search approach
Guide to Spring Cloud Kubernetes
Jackson – Bidirectional Relationships
A Guide to Concurrent Queues in Java
Java Program to Implement Branch and Bound Method to Perform a Combinatorial Search
Jackson vs Gson
Java Program to Perform Partition of an Integer in All Possible Ways
Remove the First Element from a List
Lớp TreeMap trong Java
Java Program to Implement Sorted Vector
Spring REST with a Zuul Proxy
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
Java Program to Implement Efficient O(log n) Fibonacci generator