shunting-yard algorithm
E79783
The shunting-yard algorithm is a method for parsing mathematical expressions and converting infix notation to postfix (or prefix) form using a stack-based procedure.
Statements (45)
| Predicate | Object |
|---|---|
| instanceOf |
algorithm
ⓘ
expression parsing technique ⓘ parsing algorithm ⓘ |
| alternativeTo | recursive descent parsing for expressions ⓘ |
| canHandle |
binary operators
ⓘ
function argument separators ⓘ function calls ⓘ unary operators ⓘ |
| category | deterministic algorithm ⓘ |
| designedBy | Edsger W. Dijkstra ⓘ |
| documentedIn | Edsger Dijkstra's writings on ALGOL and expression parsing ⓘ |
| evaluationStrategy | non-recursive ⓘ |
| field |
compiler construction
ⓘ
computer science ⓘ programming languages ⓘ |
| handles |
left-associative operators
ⓘ
right-associative operators ⓘ |
| hasPurpose |
convert infix notation to postfix notation
ⓘ
convert infix notation to prefix notation ⓘ parse mathematical expressions ⓘ |
| input | sequence of tokens representing an expression ⓘ |
| inspiredBy | railway shunting process ⓘ |
| introducedIn | 1960s ⓘ |
| namedAfter | railway shunting yard ⓘ |
| operatesOn | infix expressions ⓘ |
| output | sequence of tokens in postfix order ⓘ |
| processingOrder | left-to-right scan of input tokens ⓘ |
| produces |
Reverse Polish Notation
ⓘ
surface form:
Reverse Polish notation
postfix expressions ⓘ prefix expressions ⓘ |
| relatedTo |
Reverse Polish Notation
ⓘ
surface form:
Reverse Polish notation
expression evaluation ⓘ operator-precedence parsing ⓘ stack-based evaluation ⓘ |
| requires |
definition of operator associativity
ⓘ
definition of operator precedence ⓘ |
| supports |
operator associativity
ⓘ
operator precedence ⓘ parentheses in expressions ⓘ |
| timeComplexity | O(n) ⓘ |
| typicalUse |
calculators
ⓘ
compilers ⓘ interpreters ⓘ |
| usesDataStructure |
queue
ⓘ
stack ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.