Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Shunting yard algorithm
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the shunting yard algorithm is a method for parsing arithmetical or logical expressions, or a combination of both, specified in <a href="/facts/Infix_notation/LY0dMhay">infix notation</a>. It can produce either a postfix notation string, also known as <a href="/facts/Reverse_Polish_notation/a6rDoJ7X">reverse Polish notation</a> (RPN), or an <a href="/facts/Abstract_syntax_tree/73AUK1jI">abstract syntax tree</a> (AST). The <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> was invented by <a href="/facts/Edsger_Dijkstra/910x0MjT">Edsger Dijkstra</a>, first published in November 1961, and named the "shunting yard" algorithm because its operation resembles that of a <a href="/facts/Classification_yard/GrRCVyY1">railroad shunting yard</a>. </p><p>Like the evaluation of RPN, the shunting yard algorithm is <a href="/facts/Stack_(data_structure)/bj7l94v1">stack</a>-based. Infix expressions are the form of mathematical notation most people are used to, for instance "3 + 4" or "3 + 4 × (2 − 1)". For the conversion there are two text <a href="/facts/Variable_(programming)/VoCKtwml">variables</a> (<a href="/facts/String_(computer_science)/4ChJu5WS">strings</a>), the input and the output. There is also a <a href="/facts/Stack_(data_structure)/bj7l94v1">stack</a> 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 <a href="/facts/Reverse_Polish_notation/a6rDoJ7X">reverse Polish notation</a>) "3 4 +" and "3 4 2 1 − × +", respectively. </p><p>The shunting yard algorithm will correctly parse all valid infix expressions, but does not reject all invalid expressions. For example, "1 2 +" is not a valid infix expression, but would be parsed as "1 + 2". The algorithm can however reject expressions with mismatched parentheses. </p><p>The shunting yard algorithm was later generalized into <a href="/facts/Operator-precedence_parser/YHfocsFq">operator-precedence parsing</a>. </p>