You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
130 lines
4.2 KiB
Java
130 lines
4.2 KiB
Java
/*
|
|
This is a Java Program to Implement Shunting Yard Algorithm. Shunting Yard algorithm is used for converting an infix expression into a postfix expression.
|
|
*/
|
|
|
|
/**
|
|
** 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);
|
|
}
|
|
}
|
|
|
|
/*
|
|
Enter infix expression
|
|
1+2*3/4-5%6*7/8+9-1
|
|
|
|
Postfix expression : 123*4/+56%7*8/-9+1- |