Shunting-yard Algorithm - The Algorithm in Detail

The Algorithm in Detail

• While there are tokens to be read:

• Read a token.
• If the token is a number, then add it to the output queue.
• If the token is a function token, then push it onto the stack.
• If the token is a function argument separator (e.g., a comma):

• Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.

• If the token is an operator, o₁, then:

• while there is an operator token, o₂, at the top of the stack, and

either o₁ is left-associative and its precedence is less than or equal to that of o₂,

or o₁ has precedence less than that of o₂,

pop o₂ off the stack, onto the output queue;

• push o₁ onto the stack.

• If the token is a left parenthesis, then push it onto the stack.
• If the token is a right parenthesis:

• Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
• Pop the left parenthesis from the stack, but not onto the output queue.
• If the token at the top of the stack is a function token, pop it onto the output queue.
• If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

• When there are no more tokens to read:

• While there are still operator tokens in the stack:

• If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
• Pop the operator 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).