Shunting yard algorithm
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]
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 A + B. This notation requires parentheses to disambiguate the order of operations when multiple operators are involved, for example, (A + B) \times C to ensure addition precedes multiplication.[13]
Prefix notation, also known as Polish notation, positions the operator before its operands, such as + A B 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 A + (B \times C) becomes + A \times B C.[14][15]
Postfix notation, or Reverse Polish notation, places the operator after its operands, as in A B + 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 A + B \times C converting to A B C \times +.[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 $2 + 3, the infix form contrasts with the postfix $2 3 +, 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](/page/Queue) // for postfix tokens
operatorStack = empty [stack](/page/Stack) // for operators and parentheses
for each [token](/page/Token) in inputTokens:
if [token](/page/Token) is an [operand](/page/Operand) (e.g., number or [variable](/page/Variable)):
outputQueue.enqueue([token](/page/Token))
else if [token](/page/Token) is an [operator](/page/Operator):
while (operatorStack is not empty and
top of operatorStack is not '(' and
(precedence([token](/page/Token)) < precedence(top of operatorStack) or
(precedence([token](/page/Token)) == precedence(top of operatorStack) and
[token](/page/Token) is left-associative))):
outputQueue.enqueue(operatorStack.pop())
operatorStack.push([token](/page/Token))
else if [token](/page/Token) == '(':
operatorStack.push([token](/page/Token))
else if [token](/page/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](/page/Queue) // for postfix tokens
operatorStack = empty [stack](/page/Stack) // for operators and parentheses
for each [token](/page/Token) in inputTokens:
if [token](/page/Token) is an [operand](/page/Operand) (e.g., number or [variable](/page/Variable)):
outputQueue.enqueue([token](/page/Token))
else if [token](/page/Token) is an [operator](/page/Operator):
while (operatorStack is not empty and
top of operatorStack is not '(' and
(precedence([token](/page/Token)) < precedence(top of operatorStack) or
(precedence([token](/page/Token)) == precedence(top of operatorStack) and
[token](/page/Token) is left-associative))):
outputQueue.enqueue(operatorStack.pop())
operatorStack.push([token](/page/Token))
else if [token](/page/Token) == '(':
operatorStack.push([token](/page/Token))
else if [token](/page/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
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.
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 $3 + 4 \times 2, 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 like sin(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]
Limitations and Common Modifications
The basic shunting-yard algorithm is designed for parsing simple infix expressions with binary operators of varying precedence and associativity, but it has notable limitations in handling more complex or ambiguous inputs. It assumes well-formed expressions that are either fully parenthesized or unambiguous in their operator usage, and lacks inherent support for error detection or recovery, such as identifying unmatched parentheses or extraneous tokens; for instance, it may process invalid inputs like "1 2 +" without rejection unless additional checks are added post-parsing.[4] Furthermore, the algorithm does not natively support advanced constructs like pre- or post-increment operators, conditional expressions (e.g., ternary operators), or unary operators without modifications, potentially leading to incorrect parsing in languages with such features.[4]
A key issue arises with operators of equal precedence, where the algorithm enforces strict left-associativity by default (popping operators from the stack until a lower-precedence one is encountered), which may not align with language-specific rules requiring right-associativity, such as exponentiation or assignment operators; this can result in incorrect grouping unless associativity is explicitly handled in the comparison logic.[4]
Common modifications address these shortcomings by integrating the algorithm with a lexer for tokenization, which preprocesses input to distinguish unary from binary operators via lookahead (e.g., treating a leading minus as unary) or state tracking.[4] Error recovery can be enhanced by validating the final output stack—ensuring exactly one expression tree remains—and inserting error tokens for mismatched elements during processing.[4] For unary operators and functions, extensions push them onto the operator stack with adjusted precedence rules, while variable-arity functions require tracking argument counts before popping.[4]
Compared to recursive descent parsing, the shunting-yard algorithm offers a non-recursive, stack-based approach that efficiently handles operator precedence without deep call stacks, making it advantageous for expression evaluation in resource-constrained environments; however, recursive descent provides greater flexibility for integrating semantic actions, better error reporting, and easier extension to broader context-free grammars beyond simple expressions.[29]
In modern applications, the algorithm is adapted for parsing in regex engines by tuning precedence for operators like union, concatenation, and Kleene star, often inserting implicit concatenation tokens to convert infix regex patterns to postfix for subsequent NFA construction.[30] Similar tweaks enable its use in query languages like relational algebra within database management systems, where operator stacks manage set operations with custom associativity.