Community hub
0 subscribers7 pages, 0 posts
Recent from talks
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Shunting yard algorithm.
Nothing was collected or created yet.
Shunting yard algorithm
View on Wikipediafrom Wikipedia
 | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (August 2013) |
| Class | Parsing |
|---|---|
| Data structure | Stack |
| Worst-case performance | |
| Worst-case space complexity |
In computer science, the shunting yard algorithm is a method for parsing arithmetical or logical expressions, or a combination of both, 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).[1] The algorithm was invented by Edsger Dijkstra, first published in November 1961,[2] and named because its operation resembles that of a railroad shunting yard.
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 "3 + 4" or "3 + 4 × (2 − 1)". 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) "3 4 +" and "3 4 2 1 − × +", respectively.
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.
The shunting yard algorithm was later generalized into operator-precedence parsing.
A simple conversion
[edit]- Input: 3 + 4
- 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: 3 4 +
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
[edit]
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 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).
The algorithm in detail
[edit]/* 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 tokens to be read: read a token if the token is: - a number: put it into the output queue - a function: push it onto the operator stack - an operator o1: while ( there is an operator o2 at the top of the operator stack which is not a left parenthesis, and (o2 has greater precedence than o1 or (o1 and o2 have the same precedence and o1 is left-associative)) ): pop o2 from the operator stack into the output queue push o1 onto the operator stack - a ",": 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 left parenthesis (i.e. "("): push it onto the operator stack - a right parenthesis (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
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), while making sure to change the associativity condition to right.
Detailed examples
[edit]Input: 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3
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: sin ( max ( 2, 3 ) ÷ 3 × π )
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 The operator at the top of the stack is a left parenthesis 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 Function at top of the stack ÷ 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 Pop stack to output 2 3 max 3 ÷ π × sin Function at top of the stack end Pop entire stack to output 2 3 max 3 ÷ π × sin
See also
[edit]References
[edit]- ^ Theodore Norvell (1999). "Parsing Expressions by Recursive Descent". www.engr.mun.ca. Retrieved 2020-12-28.
- ^ 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.
External links
[edit]- Dijkstra's original description of the Shunting yard algorithm
- Literate Programs implementation in C
- Demonstration of Shunting yard algorithm in Rust
- 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
Shunting yard algorithm
View on Grokipediafrom Grokipedia
The Shunting-yard algorithm is a method for transforming mathematical expressions from infix notation (e.g., 3 + 4 * 2) to postfix notation (e.g., 3 4 2 * +), ensuring proper operator precedence and associativity through the use of a stack to manage operators and operands.[1] Developed by computer scientist Edsger W. Dijkstra, it processes input tokens sequentially, outputting operands immediately while delaying operators until their precedence dictates, and handles parentheses by treating them as priority boundaries.[2] The name derives from its analogy to the operations of a railroad shunting yard, where trains are rearranged, though this terminology was applied retrospectively to Dijkstra's 1961 description.[2]
Dijkstra introduced the algorithm in his work on building an ALGOL 60 translator for the Electrologica X1 computer, emphasizing efficient, immediate translation without storing the entire expression, which was crucial for the era's limited memory constraints.[1] In the algorithm, each operator is assigned a precedence level (e.g., multiplication higher than addition) and pushed onto an operator stack; when a lower-precedence operator arrives, higher-precedence ones are popped and output first, mimicking a queue-like rearrangement.[2] Parentheses are managed by pushing an opening parenthesis onto the stack (with minimal precedence) and, upon encountering a closing one, popping operators until the matching opening is found, thus isolating subexpressions.[1]
The algorithm's simplicity and effectiveness have made it a foundational tool in computer science, particularly for parsing arithmetic expressions in compilers, interpreters, and calculators that support Reverse Polish Notation (RPN).[3] It extends naturally to handle unary operators, function calls, and relational operators by adjusting precedence rules, and variants address left- versus right-associativity for operators like exponentiation.[2] Beyond mathematics, it influences broader syntactic analysis in programming languages, contributing to the design of recursive descent parsers and expression trees in modern software.[4]
These levels are conventional in many programming languages and expression parsers, with numeric values assigned for comparison (higher numbers indicate higher precedence).[18]
In infix parsing, precedence and associativity dictate implicit grouping of operands and operators, preventing ambiguous interpretations without explicit parentheses; the shunting yard algorithm simulates this grouping by comparing operator precedences during stack operations to produce an equivalent postfix sequence.[18] For instance, the expression 2 + 3 * 4 is resolved as 2 + (3 * 4) due to the higher precedence of *, yielding a value of 14 rather than (2 + 3) * 4 = 20.[18] Similarly, 9 - 5 - 2 follows left associativity to become (9 - 5) - 2 = 2, while 2 ^ 3 ^ 2 is grouped as 2 ^ (3 ^ 2) = 2 ^ 9 = 512 under right associativity.[18]
This pseudocode handles binary operators and parentheses correctly, producing a postfix output ready for evaluation.[1][2]
The implementation assumes complete tokenization of the input expression beforehand and focuses on well-formed expressions without unary operators or functions; error handling for unmatched parentheses or invalid tokens is omitted for simplicity. The precedence comparison logic relies on a predefined table associating each operator with a precedence level and associativity, as established in operator grammar definitions.[1]
The time complexity is O(n), where n is the length of the input token sequence, since each token is enqueued or pushed/popped from the stack at most once in a single pass through the input. Space complexity is also O(n) in the worst case, due to the potential size of the operator stack and output queue.
This trace shows how the algorithm delays the lower-precedence + until after the higher-precedence × is processed, correctly grouping the multiplication first.[1]
To verify, evaluate the postfix expression using a stack: push 3, push 4, push 2; encounter ×, pop 2 and 4, compute 8, push 8; encounter +, pop 8 and 3, compute 11, push 11. The final stack value is 11, matching the infix evaluation .[1]
This step-by-step evolution visually demonstrates the stack's role: the opening parenthesis suspends normal precedence rules within the subexpression "3 + 4", treating it as a single unit by popping the '+' only upon encountering the closing parenthesis, after which the multiplication applies to that result before the final subtraction.[2]
A key insight of the algorithm lies in how parentheses temporarily override operator precedences and associativities, allowing subexpressions to be resolved independently as atomic units before reintegrating into the broader expression.[2] This mechanism ensures correct ordering without recursive parsing, relying solely on stack operations to mimic the shunting of train cars in Dijkstra's original analogy.
To verify correctness, evaluate the resulting postfix expression "3 4 + 2 * 1 -": first, 3 + 4 = 7; then, 7 * 2 = 14; finally, 14 - 1 = 13, matching the infix evaluation of ((3 + 4) * 2) - 1 = 13.[2]
Introduction and Background
Overview and Motivation
The shunting yard algorithm is a stack-based parsing technique for converting mathematical expressions from infix notation to postfix notation, also known as Reverse Polish Notation (RPN).[4] It was developed by Edsger W. Dijkstra in 1960 as part of efforts to implement the world's first ALGOL 60 compiler and first described in 1961.[4] The name derives from its analogy to a railroad shunting yard, where train cars (representing operators and operands) are rearranged between tracks (stacks and output) to assemble the correct order.[5] Infix notation, the standard human-readable form where operators appear between operands (e.g., 2 + 3), introduces ambiguity due to varying operator precedence and associativity, often requiring parentheses to clarify grouping.[6] Postfix notation resolves this by placing operators after their operands (e.g., 2 3 +), eliminating the need for parentheses and enabling unambiguous evaluation through a simple stack-based process.[7] The primary motivation for the algorithm is to facilitate efficient, non-recursive parsing and evaluation of expressions, which is particularly valuable in resource-constrained environments.[4] It powers applications in calculators for handling user input, interpreters for dynamic expression evaluation, and compilers for building abstract syntax trees during code analysis.[8]Historical Context
The Shunting Yard algorithm was developed by Edsger W. Dijkstra in 1960, in collaboration with Jaap Zonneveld, as part of the world's first ALGOL 60 compiler for the Electrologica X1 computer, which became operational that summer. It was first described in his Mathematisch Centrum report MR 35, titled "Algol 60 translation: An Algol 60 translator for the X1 and making a translator for Algol 60," where Dijkstra outlined methods for handling infix notation in compilers.[9] The algorithm also appeared in his 1961 article "Making a Translator for ALGOL 60," published in the APIC Bulletin, emphasizing practical implementation for early computing systems.[10] Dijkstra named the algorithm after the operations in a railroad shunting yard, where incoming trains representing operators and operands are systematically rearranged into desired output sequences using temporary sidings that function analogously to a stack. This railway-inspired analogy highlighted the algorithm's use of a stack to manage operator precedence during expression parsing, providing an intuitive model for rearranging elements without recursion. The design drew from Dijkstra's experience with the Electrologica X1 computer, addressing the need for efficient, machine-independent expression handling in resource-constrained environments.[9] Developed amid the rise of ALGOL 60, the algorithm emerged before the broad adoption of formal context-free grammars for parsing, offering a lightweight, iterative alternative for evaluating arithmetic expressions in compilers. It was quickly integrated into early ALGOL implementations, such as the Dijkstra-Zonneveld compiler for the Electrologica X1, which relied on stack-based techniques to process infix expressions without full recursive descent.[11] This adoption facilitated reliable expression evaluation in the nascent field of compiler design, influencing subsequent tools for languages emphasizing infix notation. The algorithm's simplicity and efficiency ensured its enduring impact, remaining a foundational component in modern parsing libraries, expression evaluators, and scripting engines, as evidenced by its continued reference in computational linguistics and software development resources.[12]Fundamental Concepts
Expression Notations
Infix notation represents the standard mathematical expression format used by humans, where an operator is placed between its two operands, as in the expression . This notation requires parentheses to disambiguate the order of operations when multiple operators are involved, for example, to ensure addition precedes multiplication.[13] Prefix notation, also known as Polish notation, positions the operator before its operands, such as for addition. Developed by Polish logician Jan Łukasiewicz in 1924 to simplify logical expressions by eliminating parentheses entirely, it processes from left to right but can feel less intuitive for everyday arithmetic due to the reversed operator placement. For instance, the expression becomes .[14][15] Postfix notation, or Reverse Polish notation, places the operator after its operands, as in for addition. Proposed in 1954 by Arthur Burks, Don Warren, and Jesse Wright for mechanical computation, and independently by Friedrich L. Bauer and Edsger W. Dijkstra, it similarly avoids parentheses and resolves operator order unambiguously through operand sequence. An example is converting to .[16] The Shunting Yard algorithm primarily converts infix expressions to postfix notation to facilitate stack-based evaluation by computers, where postfix form allows direct processing without checking operator precedence during execution. Infix notation's reliance on precedence rules introduces ambiguity that requires explicit handling, whereas postfix eliminates this need, enabling simpler, more efficient parsing in compilers and interpreters. For a basic case like , the infix form contrasts with the postfix , highlighting how the latter directly specifies the operation sequence.[13][17]Operator Precedence and Associativity
In infix notation, operator precedence establishes a hierarchy that determines the order of evaluation for operators in an expression when parentheses are absent, ensuring that higher-precedence operators are applied before lower ones to resolve ambiguities.[18] For common arithmetic operators, exponentiation (^) holds the highest precedence, followed by multiplication (*) and division (/), with addition (+) and subtraction (-) at the lowest level.[18] Associativity specifies how operators of equal precedence are grouped when they appear sequentially in an expression, either left-to-right or right-to-left.[18] Most arithmetic operators, including +, -, *, and /, are left-associative, meaning expressions like A - B - C are parsed as (A - B) - C.[18] In contrast, the exponentiation operator (^) is typically right-associative, so A ^ B ^ C is interpreted as A ^ (B ^ C).[18] The following table summarizes the standard precedence levels and associativity for common arithmetic operators:| Operator | Precedence Level | Associativity |
|---|---|---|
| ^ | Highest (3) | Right |
| , / | High (2) | Left |
| + , - | Lowest (1) | Left |
Algorithm Description
Step-by-Step Process
The Shunting Yard algorithm processes an infix mathematical expression, represented as a sequence of tokens including operands, operators, and parentheses, to convert it into postfix notation. This conversion facilitates unambiguous evaluation by eliminating the need for parentheses in the output form. The algorithm relies on two primary data structures: an output queue that collects the postfix tokens and an operator stack that temporarily holds operators and left parentheses during processing.[2] The process begins by scanning the input tokens from left to right. When an operand (such as a number or variable) is encountered, it is immediately appended to the output queue, as operands maintain their order in postfix notation. Left parentheses are pushed directly onto the operator stack, serving as markers to group subexpressions. Right parentheses trigger the popping of operators from the stack to the output queue until a matching left parenthesis is found at the top of the stack; the left parenthesis is then discarded without being added to the output.[19][2] For operator tokens, the algorithm compares the current operator's precedence and associativity with those of the operators already on the stack. While the stack is not empty, the top is not a left parenthesis, and the top operator has higher precedence than the current one (or equal precedence if the operators are left-associative), the top operator is popped and appended to the output queue. If the top has lower precedence or equal precedence for right-associative operators, the current operator is pushed onto the stack. This ensures that higher-precedence operators are output before lower ones, respecting the order of operations, while associativity determines whether equal-precedence operators are resolved left-to-right (by popping) or right-to-left (by pushing).[2][20] Upon reaching the end of the input, any remaining operators on the stack are popped in reverse order (last-in, first-out) and appended to the output queue, completing the postfix expression. This final step ensures all pending operations are included, as there are no further tokens to trigger their release. The resulting output queue represents the fully converted postfix notation, ready for stack-based evaluation.[19][2]Pseudocode Implementation
The shunting yard algorithm is typically implemented using two data structures: an output queue to hold the postfix notation and a stack to manage operators and parentheses. The process assumes that the input expression has been tokenized into a sequence of operands, operators, and parentheses, with operator precedence and associativity predefined (e.g., multiplication has higher precedence than addition, and most operators are left-associative).[1] The following pseudocode outlines the core implementation, processing each token in a single pass:function shuntingYard(inputTokens):
outputQueue = empty queue // for postfix tokens
operatorStack = empty stack // for operators and parentheses
for each token in inputTokens:
if token is an [operand](/page/Operand) (e.g., number or variable):
outputQueue.enqueue(token)
else if token is an operator:
while (operatorStack is not empty and
top of operatorStack is not '(' and
(precedence(token) < precedence(top of operatorStack) or
(precedence(token) == precedence(top of operatorStack) and
token is left-associative))):
outputQueue.enqueue(operatorStack.pop())
operatorStack.push(token)
else if token == '(':
operatorStack.push(token)
else if token == ')':
while (operatorStack is not empty and
top of operatorStack != '('):
outputQueue.enqueue(operatorStack.pop())
if operatorStack is not empty: // discard matching '('
operatorStack.pop()
while operatorStack is not empty:
outputQueue.enqueue(operatorStack.pop())
return outputQueue // postfix expression
function shuntingYard(inputTokens):
outputQueue = empty queue // for postfix tokens
operatorStack = empty stack // for operators and parentheses
for each token in inputTokens:
if token is an [operand](/page/Operand) (e.g., number or variable):
outputQueue.enqueue(token)
else if token is an operator:
while (operatorStack is not empty and
top of operatorStack is not '(' and
(precedence(token) < precedence(top of operatorStack) or
(precedence(token) == precedence(top of operatorStack) and
token is left-associative))):
outputQueue.enqueue(operatorStack.pop())
operatorStack.push(token)
else if token == '(':
operatorStack.push(token)
else if token == ')':
while (operatorStack is not empty and
top of operatorStack != '('):
outputQueue.enqueue(operatorStack.pop())
if operatorStack is not empty: // discard matching '('
operatorStack.pop()
while operatorStack is not empty:
outputQueue.enqueue(operatorStack.pop())
return outputQueue // postfix expression
Practical Examples
Basic Infix to Postfix Conversion
The shunting-yard algorithm converts infix expressions to postfix notation by processing tokens from left to right, using a stack to manage operators based on their precedence and associativity.[1] Consider the basic infix expression , where the tokens are the operand 3, operator +, operand 4, operator × (with higher precedence than +), and operand 2.[1] This example demonstrates the algorithm's enforcement of operator precedence without parentheses, resulting in the postfix expression ( 3\ 4\ 2\ \times\ +\ ), which evaluates to 11. The conversion process begins with an empty output queue and an empty operator stack. The first token, 3 (an operand), is directly added to the output. The next token, + (an operator), is pushed onto the stack since the stack is empty. The token 4 (operand) follows, added to the output. Upon encountering × (operator), its higher precedence (priority 10 for multiplication versus 9 for addition) prevents popping the +; thus, × is pushed onto the stack.[1] The final token, 2 (operand), is added to the output. At the end of input, all remaining operators are popped from the stack in last-in-first-out order: × first, then +, yielding the complete postfix output. The following table traces the stack and output states after each token:| Token | Action | Stack | Output |
|---|---|---|---|
| 3 | Output operand | [] | 3 |
| + | Push operator | [+] | 3 |
| 4 | Output operand | [+] | 3 4 |
| × | Push operator (higher precedence) | [+ ×] | 3 4 |
| 2 | Output operand | [+ ×] | 3 4 2 |
| End | Pop all operators | [] | 3 4 2 × + |
Expressions with Parentheses and Multiple Operators
To illustrate the shunting yard algorithm's capability in managing grouped subexpressions alongside multiple binary operators, consider the infix expression "(3 + 4) * 2 - 1", where standard operator precedences apply: addition and subtraction have lower precedence than multiplication, and all are left-associative.[2] This example tokenizes into: '(', '3', '+', '4', ')', '*', '2', '-', '1'. The algorithm processes these tokens sequentially, using a stack for operators and parentheses, and an output queue for operands and resolved operators. The trace unfolds as follows, with the stack evolving to enforce grouping and precedence:| Token | Action | Stack | Output |
|---|---|---|---|
| ( | Push opening parenthesis | ( | |
| 3 | Output operand | ( | 3 |
| + | Push operator (no higher-precedence operators above '(') | ( + | 3 |
| 4 | Output operand | ( + | 3 4 |
| ) | Pop until matching '(', outputting operators; discard parentheses | 3 4 + | |
| * | Push operator (stack empty) | * | 3 4 + |
| 2 | Output operand | * | 3 4 + 2 |
| - | Current '-' has lower precedence than top ''; pop '' to output, then push '-' (left-associativity ensures sequential resolution) | - | 3 4 + 2 * |
| 1 | Output operand | - | 3 4 + 2 * 1 |
| (end) | Pop remaining operators | 3 4 + 2 * 1 - |
Advanced Case with Unary Operators
The shunting-yard algorithm, originally designed for binary operators, requires modifications to handle unary operators such as negation (-A), which apply to a single operand. These operators are typically distinguished from their binary counterparts through lexical analysis or contextual rules: a minus sign is unary if it follows the start of an expression, a left parenthesis, or another operator, but binary if it follows an operand. In implementations, unary operators are assigned the highest precedence level, exceeding that of all binary operators, to ensure they bind tightly to their operand. Additionally, unary operators are treated as right-associative to correctly interpret expressions like -3^2 as -(3^2) rather than (-3)^2.[21][22] To incorporate unary operators into the algorithm, the pseudocode from the basic process is adapted by introducing a separate token type or flag for unary minus during input tokenization. When a unary operator is encountered, it is pushed onto the operator stack with its elevated precedence value. The popping rule remains similar: while the stack's top operator has greater or equal precedence (considering associativity), it is outputted. This ensures unary operators are resolved immediately after their operand in the postfix output. For instance, in the expression "2 * -3 + 1", the unary minus precedes the operand 3 and receives higher precedence than multiplication or addition, resulting in the postfix notation "2 3 - * 1 +", where the negation applies directly to 3 before multiplication.[21] Consider the more complex example "-(3 + 4) * 2". Tokenization identifies the initial minus as unary due to its position at the start. The algorithm processes as follows: push the unary minus onto the stack; push '('; output 3; push +; output 4; upon encountering ')', pop + to output, yielding "3 4 +", and discard the matching '(' , leaving the unary minus on the stack; then, upon encountering *, pop unary minus to output (higher precedence than *), yielding "3 4 + -", and push *; output 2; finally at end, pop * to output, producing the full postfix "3 4 + - 2 *". This trace demonstrates how the unary operator's high precedence and right-associativity nest it correctly around the parenthesized subexpression, a handling rule not present in the original binary-only formulation.[22][21] Such extensions address limitations in basic coverage by enabling the algorithm to parse realistic mathematical expressions involving negation or other unary operations, commonly used in compilers and calculators. Precedence tables must explicitly define unary levels above binary ones, such as unary > exponentiation > multiplication/division > addition/subtraction.[21]Applications and Extensions
Use in Parsers and Compilers
The shunting yard algorithm plays a key role in calculators and interpreters by converting infix expressions entered by users into postfix notation, enabling efficient evaluation without recursive descent or complex grammar rules. This approach is particularly useful in systems that natively employ reverse Polish notation (RPN) for computation, such as HP calculators, where algebraic input is transformed to match the stack-based execution model.[23] In compiler front-ends for languages like C and Java, the algorithm parses arithmetic and logical expressions during the lexical and syntactic analysis phases, producing postfix output that facilitates the generation of intermediate code or machine instructions. The resulting postfix sequence simplifies operator precedence handling and supports code optimization passes.[23][24] The postfix notation generated by the algorithm often serves as an intermediate representation for constructing abstract syntax trees (ASTs), where operators and operands are organized into a hierarchical structure for semantic analysis and code generation in compilers. This integration allows for straightforward traversal and transformation of expression structures.[24] Practical implementations appear in query languages like SQL, where adaptations of the shunting yard algorithm process WHERE clauses and relational expressions, converting them to postfix for optimized query evaluation in database systems.[25] With a time complexity of O(n), where n is the length of the input expression in tokens, the algorithm's linear performance ensures it is well-suited for real-time parsing in interactive environments like calculators and web-based interpreters.Handling Functions and Variants
The shunting-yard algorithm can be extended to handle functions by treating them as prefix unary operators with the highest precedence, allowing the parsing of mathematical expressions involving calls likesin(x). Upon encountering a function name, such as sin, it is pushed onto the operator stack. The subsequent opening parenthesis is handled as in the standard algorithm, with arguments processed recursively within the parentheses. When the closing parenthesis is reached, operators are popped from the stack to the output queue until the opening parenthesis is encountered, after which the function is popped and appended to the output, often accompanied by an argument count to enable proper evaluation in postfix form. This ensures that the arguments are output before the function in the resulting Reverse Polish Notation (RPN).[26]
For example, the infix expression sin(3 + 4) is tokenized as sin, (, 3, +, 4, ). The algorithm outputs 3 4 + sin, where the addition is resolved first, followed by the function application. This approach is common in scientific computing parsers, where functions like sin, cos, or log are integrated seamlessly with binary operators.[26]
A variant for prefix functions modifies the stack management to accommodate n-ary operators, such as user-defined functions with multiple arguments separated by commas. In this extension, an additional stack or counter tracks the number of arguments within parentheses; the function is only popped upon the closing parenthesis after confirming the expected argument count, enabling support for expressions like max(2, 3, 4). This requires updating the parentheses-handling logic to increment the argument count on commas and validate arity during popping.[27]
Other variants include hybrids combining the shunting-yard algorithm with Pratt parsing for improved error recovery in ambiguous or complex grammars. Pratt parsing, a top-down operator precedence method, leverages recursion to climb precedence levels, effectively simulating the shunting-yard's explicit stack via the call stack, which facilitates better localization of syntax errors without full backtracking. While recursive descent parsing offers an alternative for expression handling through mutually recursive functions tailored to grammar rules, the shunting-yard algorithm retains advantages in simplicity and efficiency for purely operator-precedence-based expressions, avoiding the overhead of recursive calls.[28]