Shunting yard algorithm

<h2 id="a-simple-conversion">A simple conversion</h2>
<ol><li>Input: 3 + 4</li>
<li>Push 3 to the output <a href="/facts/Queue_(data_structure)/hVPjPXus">queue</a> (whenever a number is read it is pushed to the output)</li>
<li><a href="/facts/Stack_(data_structure)/bj7l94v1">Push</a> + (or its ID) onto the operator <a href="/facts/Stack_(data_structure)/bj7l94v1">stack</a></li>
<li>Push 4 to the output queue</li>
<li>After reading the expression, <a href="/facts/Stack_(data_structure)/bj7l94v1">pop</a> the operators off the stack and add them to the output.
In this case there is only one, "+".</li>
<li>Output: 3 4 +</li></ol>
<p>This already shows a couple of rules:
</p>
<ul><li>All numbers are pushed to the output when they are read.</li>
<li>At the end of reading the expression, pop all operators off the stack and onto the output.</li></ul>
<h2 id="graphical-illustration">Graphical illustration</h2>

<p>Graphical illustration of algorithm, using a <a href="/facts/Wye_junction/9t4YyIQA">three-way railroad junction</a>. 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 precedences 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).
</p>
<h2 id="the-algorithm-in-detail">The algorithm in detail</h2>
<p class="note">For important terms, see <a href="/facts/Token_(parser)/T1JYWpIf">token (parser)</a>, <a href="/facts/Function_(mathematics)/CdReEKCh">function (mathematics)</a>, <a href="/facts/Operator_associativity/HcEdArws">Operator associativity</a>, and <a href="/facts/Order_of_operations/sWsoTzbH">Order of operations</a>.</p>
/* The functions referred to in this algorithm are simple single argument functions such as sine, inverse or factorial. */
/* This implementation does not implement composite functions, functions with a variable number of arguments, or unary operators. */

while there are <a href="/facts/Token_(parser)/T1JYWpIf">tokens</a> to be read:
    read a token
    if the token is:
    - a <i>number</i>:
        put it into the output queue
    - a <i><a href="/facts/Function_(mathematics)/CdReEKCh">function</a></i>:
        push it onto the operator stack 
    - an <i>operator</i> <i>o</i>1:
        while (
            there is an operator <i>o</i>2 at the top of the operator stack which is not a left parenthesis, 
            and (<i>o</i>2 has greater <a href="/facts/Order_of_operations/sWsoTzbH">precedence</a> than <i>o</i>1 or (<i>o</i>1 and <i>o</i>2 have the same precedence and <i>o</i>1 is left-associative))
        ):
            pop <i>o</i>2 from the operator stack into the output queue
        push <i>o</i>1 onto the operator stack
    - a <i>","</i>:
        while the operator at the top of the operator stack is not a left parenthesis:
             pop the operator from the operator stack into the output queue
    - a <i>left parenthesis</i> (i.e. "("):
        push it onto the operator stack
    - a <i>right parenthesis</i> (i.e. ")"):
        while the operator at the top of the operator stack is not a left parenthesis:
            {assert the operator stack is not empty}
            /* If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. */
            pop the operator from the operator stack into the output queue
        {assert there is a left parenthesis at the top of the operator stack}
        pop the left parenthesis from the operator stack and discard it
        if there is a function token at the top of the operator stack, then:
            pop the function from the operator stack into the output queue
/* After the while loop, pop the remaining items from the operator stack into the output queue. */
while there are tokens on the operator stack:
    /* If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. */
    {assert the operator on top of the stack is not a (left) parenthesis}
    pop the operator from the operator stack onto the output queue

<p>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(<i>n</i>) — linear in the size of the input.
</p><p>The shunting yard algorithm can also be applied to produce prefix notation (also known as <a href="/facts/Polish_notation/dUzpf2Ys">Polish notation</a>). 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), while making sure to change the <a href="/facts/Operator_associativity/HcEdArws">associativity</a> condition to right.
</p>
<h2 id="detailed-examples">Detailed examples</h2>
<p>Input: 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3
</p>
<table><tbody><tr><th>Operator</th><th>Precedence</th><th>Associativity</th></tr><tr><td>^</td><td>4</td><td>Right</td></tr><tr><td>×</td><td>3</td><td>Left</td></tr><tr><td>÷</td><td>3</td><td>Left</td></tr><tr><td>+</td><td>2</td><td>Left</td></tr><tr><td>−</td><td>2</td><td>Left</td></tr></tbody></table>
<p>The symbol ^ represents the <a href="/facts/Exponentiation/pac6QY2g">power operator</a>.
</p>
<table><tbody><tr><th>Token</th><th>Action</th><th>Output(in <a href="/facts/Reverse_Polish_Notation/a6rDoJ7X">RPN</a>)</th><th>Operatorstack</th><th>Notes</th></tr><tr><td>3</td><td>Add token to output</td><td>3</td><td></td><td></td></tr><tr><td>+</td><td>Push token to stack</td><td>3</td><td>+</td><td></td></tr><tr><td>4</td><td>Add token to output</td><td>3 4</td><td>+</td><td></td></tr><tr><td>×</td><td>Push token to stack</td><td>3 4</td><td>× +</td><td>× has higher precedence than +</td></tr><tr><td>2</td><td>Add token to output</td><td>3 4 2</td><td>× +</td><td></td></tr><tr><td rowspan="2">÷</td><td>Pop stack to output</td><td>3 4 2 ×</td><td>+</td><td>÷ and × have same precedence</td></tr><tr><td>Push token to stack</td><td>3 4 2 ×</td><td>÷ +</td><td>÷ has higher precedence than +</td></tr><tr><td>(</td><td>Push token to stack</td><td>3 4 2 ×</td><td>( ÷ +</td><td></td></tr><tr><td>1</td><td>Add token to output</td><td>3 4 2 × 1</td><td>( ÷ +</td><td></td></tr><tr><td>−</td><td>Push token to stack</td><td>3 4 2 × 1</td><td>− ( ÷ +</td><td></td></tr><tr><td>5</td><td>Add token to output</td><td>3 4 2 × 1 5</td><td>− ( ÷ +</td><td></td></tr><tr><td rowspan="2">)</td><td>Pop stack to output</td><td>3 4 2 × 1 5 −</td><td>( ÷ +</td><td>Repeated until "(" found</td></tr><tr><td>Pop stack</td><td>3 4 2 × 1 5 −</td><td>÷ +</td><td>Discard matching parenthesis</td></tr><tr><td>^</td><td>Push token to stack</td><td>3 4 2 × 1 5 −</td><td>^ ÷ +</td><td>^ has higher precedence than ÷</td></tr><tr><td>2</td><td>Add token to output</td><td>3 4 2 × 1 5 − 2</td><td>^ ÷ +</td><td></td></tr><tr><td>^</td><td>Push token to stack</td><td>3 4 2 × 1 5 − 2</td><td>^ ^ ÷ +</td><td>^ is evaluated right-to-left</td></tr><tr><td>3</td><td>Add token to output</td><td>3 4 2 × 1 5 − 2 3</td><td>^ ^ ÷ +</td><td></td></tr><tr><td><i>end</i></td><td>Pop entire stack to output</td><td>3 4 2 × 1 5 − 2 3 ^ ^ ÷ +</td><td></td><td></td></tr></tbody></table>
<p>Input: sin ( max ( 2, 3 ) ÷ 3 × π )
</p>
<table><tbody><tr><th>Token</th><th>Action</th><th>Output(in <a href="/facts/Reverse_Polish_Notation/a6rDoJ7X">RPN</a>)</th><th>Operatorstack</th><th>Notes</th></tr><tr><td>sin</td><td>Push token to stack</td><td></td><td>sin</td><td></td></tr><tr><td>(</td><td>Push token to stack</td><td></td><td>( sin</td><td></td></tr><tr><td>max</td><td>Push token to stack</td><td></td><td>max ( sin</td><td></td></tr><tr><td>(</td><td>Push token to stack</td><td></td><td>( max ( sin</td><td></td></tr><tr><td>2</td><td>Add token to output</td><td>2</td><td>( max ( sin</td><td></td></tr><tr><td>,</td><td>Ignore</td><td>2</td><td>( max ( sin</td><td>The operator at the top of the stack is a left parenthesis</td></tr><tr><td>3</td><td>Add token to output</td><td>2 3</td><td>( max ( sin</td><td></td></tr><tr><td rowspan="3'">)</td><td>Pop stack to output</td><td>2 3</td><td>( max ( sin</td><td>Repeated until "(" is at the top of the stack</td></tr><tr><td>Pop stack</td><td>2 3</td><td>max ( sin</td><td>Discarding matching parentheses</td></tr><tr><td>Pop stack to output</td><td>2 3 max</td><td>( sin</td><td>Function at top of the stack</td></tr><tr><td>÷</td><td>Push token to stack</td><td>2 3 max</td><td>÷ ( sin</td><td></td></tr><tr><td>3</td><td>Add token to output</td><td>2 3 max 3</td><td>÷ ( sin</td><td></td></tr><tr><td rowspan="2">×</td><td>Pop stack to output</td><td>2 3 max 3 ÷</td><td>( sin</td><td></td></tr><tr><td>Push token to stack</td><td>2 3 max 3 ÷</td><td>× ( sin</td><td></td></tr><tr><td>π</td><td>Add token to output</td><td>2 3 max 3 ÷ π</td><td>× ( sin</td><td></td></tr><tr><td rowspan="3">)</td><td>Pop stack to output</td><td>2 3 max 3 ÷ π ×</td><td>( sin</td><td>Repeated until "(" is at the top of the stack</td></tr><tr><td>Pop stack</td><td>2 3 max 3 ÷ π ×</td><td>sin</td><td>Discarding matching parentheses</td></tr><tr><td>Pop stack to output</td><td>2 3 max 3 ÷ π × sin</td><td></td><td>Function at top of the stack</td></tr><tr><td><i>end</i></td><td>Pop entire stack to output</td><td>2 3 max 3 ÷ π × sin</td><td></td><td></td></tr></tbody></table>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Operator-precedence_parser/YHfocsFq">Operator-precedence parser</a></li>
<li><a href="/facts/Stack-sortable_permutation/xdLmgwmr">Stack-sortable permutation</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.cs.utexas.edu/~EWD/MCReps/MR35.PDF">Dijkstra's original description of the Shunting yard algorithm</a></li>
<li><a href="https://literateprograms.org/shunting_yard_algorithm__c_.html">Literate Programs implementation in C</a></li>
<li><a href="https://github.com/Skarlett/shunting-yard-rs/blob/93bf03b37da611c1d642b6e221597ae095189901/src/main.rs#L220-L300">Demonstration of Shunting yard algorithm in Rust</a></li>
<li><a href="http://www.chris-j.co.uk/parsing.php">Java Applet demonstrating the Shunting yard algorithm</a></li>
<li><a href="http://www.codeding.com/?article=11">Silverlight widget demonstrating the Shunting yard algorithm and evaluation of arithmetic expressions</a></li>
<li><a href="http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm">Parsing Expressions by Recursive Descent</a> Theodore Norvell © 1999–2001. Access date September 14, 2006.</li>
<li><a href="https://nl.mathworks.com/matlabcentral/fileexchange/68458-evaluation">Matlab code, evaluation of arithmetic expressions using the shunting yard algorithm</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Theodore Norvell (1999). "Parsing Expressions by Recursive Descent". www.engr.mun.ca. Retrieved 2020-12-28. <a href="http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm" target="_blank">http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Dijkstra, Edsger (1961-11-01). "Algol 60 translation : An Algol 60 translator for the X1 and making a translator for Algol 60". Stichting Mathematisch Centrum. <a href="https://ir.cwi.nl/pub/9251" target="_blank">https://ir.cwi.nl/pub/9251</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Shunting yard algorithm open-in-new

Shunting yard algorithm