infixexpression

Class ShuntingYard

java.lang.Object

infixexpression.ShuntingYard

public class ShuntingYard
extends java.lang.Object

The Shunting-Yard algorithm is due to Edsger Dijkstra. This version of Shunting-Yard is based on modifications to the algorithm found on the Wikipedia web site here: https://en.wikipedia.org/wiki/Shunting-yard_algorithm. It converts an infix expression to postfix form. Unlike the Wikipedia article, this code does not handle functions. Also, unlike the Wikipedia article, this code does handle assignment to variables. There is no attempt here to validate the infix expression. It assumes that the user has entered a legal infix expression that may contain parenthesis to override the normal precedence of operators. The precedence rules are as follows: Raising to a power with ^ has the highest precedence. Multiplication and division have a higher precedence than addition and subtraction. The assignment operator = is of lower precedence than addition or subtraction. All of the operators associate left to right - except for ^ and =. The ^ and = operators associate right to left. Here is an example execution:

2 -3 - 5

2 3 - 5 -

3 + 5 * 6

3 5 6 * +

(3 + 4) * ( 9 - 8)

3 4 + 9 8 - *

n = k = 4

n k 4 = =

net + pay

net pay +

3 + 4 * 5

3 4 5 * +

1 + 2 + 3 + 4 * 5

1 2 + 3 + 4 5 * +

3^5^6

3 5 6 ^ ^

4^(3+4)

4 3 4 + ^

123 + 456

123 456 +

12.34 + 65.66

12.34 65.66 +

There are two main data structures involved in the computation: A stack is used to hold operators and a queue is used to store the output as it is generated.

Constructor Summary

Constructors

Constructor and Description
ShuntingYard()

Method Summary

Modifier and Type	Method and Description
java.lang.String	getQueueAsString()
boolean	isPrecedenceLessThan(Token o1, Token o2)
boolean	isPrecedenceLessThanOrEqualTo(Token o1, Token o2)
boolean	leftAssociative(Token o)
static void	main(java.lang.String[] args) The main routine reads one line of infix and, when the return key is entered, writes one line of the corresponding postfix.
boolean	rightAssociative(Token o)
void	shuntingYard(Token[] toks, int size) Perform the Shunting-yard algorithm and add the postfix expression to the queue.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ShuntingYard

public ShuntingYard()

Method Detail

getQueueAsString

public java.lang.String getQueueAsString()

Returns:

the queue contents as a String in FIFO order.

leftAssociative

public boolean leftAssociative(Token o)

Parameters:

o - is a Token from the infix expression

Returns:

true if and only if o is +, -, /, *

rightAssociative

public boolean rightAssociative(Token o)

Parameters:

o - is a Token from the infix expression

Returns:

true if and only if o is ^ or =

isPrecedenceLessThanOrEqualTo

public boolean isPrecedenceLessThanOrEqualTo(Token o1,
                                             Token o2)

Parameters:

o1 - is a Token from the infix expression

o2 - is a Token from the infix expression

Returns:

true if and only if o1 has less than or equal to the precedence of o2.

isPrecedenceLessThan

public boolean isPrecedenceLessThan(Token o1,
                                    Token o2)

Parameters:

o1 - is a Token from the infix expression

o2 - is a Token from the infix expression

Returns:

true if and only if o1 has less than the precedence of o2.

shuntingYard

public void shuntingYard(Token[] toks,
                         int size)

Perform the Shunting-yard algorithm and add the postfix expression to the queue.

Parameters:

toks - an array of Tokens

size - of this size

main

public static void main(java.lang.String[] args)
                 throws java.io.IOException

The main routine reads one line of infix and, when the return key is entered, writes one line of the corresponding postfix. The main routine runs (reading infix and writing postfix) until the user hits the return key on an empty line. Pre-condition: The user is well behaved and always enters legal infix expressions containing number, variable names or operators chosen from the set {+,-,*,/,^,=}. Post-condition: The generated postfix contains a single space between tokens. This routine creates a ShuntingYard object. It then runs the shuntingYard method on the tokenized input. The tokenized input is the infix string broken down into tokens. It writes the data left in the queue to the output screen.

Parameters:

args - not used

Throws:

java.io.IOException