# The Shunting-Yard Algorithm

6 replies to this topic

### #1Reedbeta

DevMaster Staff

• 5307 posts
• LocationBellevue, WA

Posted 11 December 2011 - 07:57 PM

I wrote an article about an algorithm that doesn't seem to be very widely known, but should be! It's called the "shunting-yard algorithm" and is used to parse arithmetic expressions in infix notation. Check out the article here: http://www.reedbeta....yard-algorithm/
reedbeta.com - developer blog, OpenGL demos, and other projects

### #2}:+()___ (Smile)

Member

• Members
• 169 posts

Posted 11 December 2011 - 11:48 PM

Ha ha, for my parsers I've reinvented the wheel and created modification of this algorithm with combined operand/operation stack. In my stack I have operands (A) or operands with incomplete operation (A+). Each stack element have 'level' which corresponds to operator precedence and incoming operator combines stack elements with level higher than operator level. At the end of expression I put dummy operator with lowest level.

For example, parsing token sequence A * B + C * D [end]
A
A*
A*   B
(A*B)+		   <-  A* and B have higher level than +
(A*B)+   C
(A*B)+   C*
(A*B)+   C*   D
((A*B)+(C*D))=	   <-  (A*B)+, C* and D have higher level than [end]


If someone decides to use my version instead of original I can give additional details.
Sorry my broken english!

### #3roel

Senior Member

• Members
• 698 posts

Posted 12 December 2011 - 10:39 AM

That was an interesting read, Reed. Haven't heard of it in CS classes either.

### #4fireside

Senior Member

• Members
• 1587 posts

Posted 12 December 2011 - 11:15 AM

I think, particularly with indy games, these kinds of solutions may be used more often.
Currently using Blender and Unity.

### #5Stainless

Member

• Members
• 581 posts
• LocationSouthampton

Posted 12 December 2011 - 12:40 PM

Interesting, quick and simple to code as well

However I still just "Use the Forth Luke"

You can write a Forth interpreter in very little code

### #6.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 12 December 2011 - 02:35 PM

Ah yes, one of the legacies of the famous Dutch computer scientiest Edsger Dijkstra

.edit:

Quote

I never heard of this algorithm until I happened to see a forum post that referenced it
Funny, was it this one? http://devmaster.net...dpost__p__65660
-
Currently working on: the 3D engine for Tomb Raider.

### #7Reedbeta

DevMaster Staff

• 5307 posts
• LocationBellevue, WA

Posted 12 December 2011 - 06:18 PM

Yes, .oisyn, that was indeed the one.
reedbeta.com - developer blog, OpenGL demos, and other projects

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users