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:
Most commonly used String methods in Java
HandlerAdapters in Spring MVC
Hướng dẫn Java Design Pattern – Singleton
Spring Data JPA and Null Parameters
How to Define a Spring Boot Filter?
Quick Intro to Spring Cloud Configuration
Java Program to Implement Patricia Trie
Concurrent Test Execution in Spring 5
Quick Guide on Loading Initial Data with Spring Boot
A Guide to Spring Boot Admin
How to Read a File in Java
A Guide to Apache Commons Collections CollectionUtils
A Guide to System.exit()
Quick Guide to the Java StringTokenizer
LinkedHashSet trong Java hoạt động như thế nào?
Removing all Nulls from a List in Java
Java Program to Perform Deletion in a BST
REST Web service: Tạo ứng dụng Java RESTful Client với Jersey Client 2.x
Rate Limiting in Spring Cloud Netflix Zuul
Java Program to Implement Brent Cycle Algorithm
Java Program to Implement Shell Sort
How to Read HTTP Headers in Spring REST Controllers
Java Program to implement Priority Queue
Java Program to Check if a Matrix is Invertible
Java Program to Perform the Unique Factorization of a Given Number
Java Program to Generate Random Numbers Using Multiply with Carry Method
Test a REST API with Java
Java Program to Find Nearest Neighbor for Dynamic Data Set
Spring Boot - Quick Start
Giới thiệu Java 8
Java Program to Check Cycle in a Graph using Graph traversal
Java Program to Perform Stooge Sort