Shunting Yard Algorithm

Get Shunting Yard Algorithm essential facts below. View Videos or join the Shunting Yard Algorithm discussion. Add Shunting Yard Algorithm to your PopFlock.com topic list for future reference or share this resource on social media.

## A simple conversion

## Graphical illustration

## The algorithm in detail

## Detailed example

## See also

## External links

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Shunting Yard Algorithm

This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. (August 2013) (Learn how and when to remove this template message) |

In computer science, the **shunting-yard algorithm** is a method for parsing mathematical expressions specified in infix notation. It can produce either a postfix notation string, also known as Reverse Polish notation (RPN), or an abstract syntax tree (AST). The algorithm was invented by Edsger Dijkstra and named the "shunting yard" algorithm because its operation resembles that of a railroad shunting yard. Dijkstra first described the Shunting Yard Algorithm in the Mathematisch Centrum report MR 34/61.

Like the evaluation of RPN, the shunting yard algorithm is stack-based. Infix expressions are the form of mathematical notation most people are used to, for instance or . For the conversion there are two text variables (strings), the input and the output. There is also a stack that holds operators not yet added to the output queue. To convert, the program reads each symbol in order and does something based on that symbol. The result for the above examples would be (in Reverse Polish notation) and , respectively.

The shunting-yard algorithm was later generalized into operator-precedence parsing.

- Input:
- Push 3 to the output queue (whenever a number is read it is pushed to the output)
- Push + (or its ID) onto the operator stack
- Push 4 to the output queue
- After reading the expression, pop the operators off the stack and add them to the output.
- In this case there is only one, "+".

- Output:

This already shows a couple of rules:

- All numbers are pushed to the output when they are read.
- At the end of reading the expression, pop all operators off the stack and onto the output.

Graphical illustration of algorithm, using a three-way railroad junction. The input is processed one symbol at a time: if a variable or number is found, it is copied directly to the output a), c), e), h). If the symbol is an operator, it is pushed onto the operator stack b), d), f). If the operator's precedence is lower than that of the operators at the top of the stack or the precedents are equal and the operator is left associative, then that operator is popped off the stack and added to the output g). Finally, any remaining operators are popped off the stack and added to the output i).

Important terms: Token, Function, Operator associativity, Precedence

/* This implementation does not implement composite functions,functions with variable number of arguments, and unary operators. */whilethere are tokens to be read: read a token.ifthe token is a number,then: push it to the output queue.else ifthe token is a functionthen: push it onto the operator stackelse ifthe token is an operatorthen:while((there is an operator at the top of the operator stack)and((the operator at the top of the operator stack has greater precedence)or(the operator at the top of the operator stack has equal precedenceandthe token is left associative))and(the operator at the top of the operator stack is not a left parenthesis)): pop operators from the operator stack onto the output queue. push it onto the operator stack.else ifthe token is a left parenthesis (i.e. "("),then: push it onto the operator stack.else ifthe token is a right parenthesis (i.e. ")"),then:whilethe operator at the top of the operator stack is not a left parenthesis: pop the operator from the operator stack onto the output queue. /* If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. */ifthere is a left parenthesis at the top of the operator stack,then: pop the operator from the operator stack and discard it /* After while loop, if operator stack not null, pop everything to output queue */ifthere are no more tokens to readthen:whilethere are still operator tokens on the stack: /* If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. */ pop the operator from the operator stack onto the output queue. exit.

To analyze the running time complexity of this algorithm, one has only to note that each token will be read once, each number, function, or operator will be printed once, and each function, operator, or parenthesis will be pushed onto the stack and popped off the stack once--therefore, there are at most a constant number of operations executed per token, and the running time is thus O(*n*)--linear in the size of the input.

The shunting yard algorithm can also be applied to produce prefix notation (also known as Polish notation). To do this one would simply start from the end of a string of tokens to be parsed and work backwards, reverse the output queue (therefore making the output queue an output stack), and flip the left and right parenthesis behavior (remembering that the now-left parenthesis behavior should pop until it finds a now-right parenthesis). And changing the associativity condition to right.

Input:

Operator Precedence Associativity ^ 4 Right × 3 Left ÷ 3 Left + 2 Left - 2 Left

The symbol ^ represents the power operator.

Token Action Output

(in RPN)Operator

stackNotes 3 Add token to output 3 + Push token to stack 3 + 4 Add token to output 3 4 + × Push token to stack 3 4 × + × has higher precedence than + 2 Add token to output 3 4 2 × + ÷ Pop stack to output 3 4 2 × + ÷ and × have same precedence Push token to stack 3 4 2 × ÷ + ÷ has higher precedence than + ( Push token to stack 3 4 2 × ( ÷ + 1 Add token to output 3 4 2 × 1 ( ÷ + - Push token to stack 3 4 2 × 1 - ( ÷ + 5 Add token to output 3 4 2 × 1 5 - ( ÷ + ) Pop stack to output 3 4 2 × 1 5 - ( ÷ + Repeated until "(" found Pop stack 3 4 2 × 1 5 - ÷ + Discard matching parenthesis ^ Push token to stack 3 4 2 × 1 5 - ^ ÷ + ^ has higher precedence than ÷ 2 Add token to output 3 4 2 × 1 5 - 2 ^ ÷ + ^ Push token to stack 3 4 2 × 1 5 - 2 ^ ^ ÷ + ^ is evaluated right-to-left 3 Add token to output 3 4 2 × 1 5 - 2 3 ^ ^ ÷ + *end*Pop entire stack to output 3 4 2 × 1 5 - 2 3 ^ ^ ÷ +

Input:

Token Action Output =

(in RPN)Operator

stackNotes sin Push token to stack sin ( Push token to stack ( sin max Push token to stack max ( sin ( Push token to stack ( max ( sin 2 Add token to output 2 ( max ( sin , ignore 2 ( max ( sin 3 Add token to output 2 3 ( max ( sin ) pop stack to output 2 3 ( max ( sin Repeated until "(" is at the top of the stack Pop stack 2 3 max ( sin Discarding matching parentheses ÷ Pop stack to output 2 3 max ( sin Push token to stack 2 3 max ÷ ( sin 3 Add token to output 2 3 max 3 ÷ ( sin × Pop stack to output 2 3 max 3 ÷ ( sin Push token to stack 2 3 max 3 ÷ × ( sin ? Add token to output 2 3 max 3 ÷ ? × ( sin ) Pop stack to output 2 3 max 3 ÷ ? × ( sin Repeated until "(" is at the top of the stack Pop stack 2 3 max 3 ÷ ? × sin Discarding matching parentheses *end*Pop entire stack to output 2 3 max 3 ÷ ? × sin

- Dijkstra's original description of the Shunting yard algorithm
- Literate Programs implementation in C
- Java Applet demonstrating the Shunting yard algorithm
- Silverlight widget demonstrating the Shunting yard algorithm and evaluation of arithmetic expressions
- Parsing Expressions by Recursive Descent Theodore Norvell © 1999-2001. Access date September 14, 2006.
- Matlab code, evaluation of arithmetic expressions using the shunting yard algorithm

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Popular Products

Music Scenes

Popular Artists