Metraipolis › archive › dc_6795cb98bcd1

Shunting yard algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Shunting_yard_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T16:49:12.714Z
SHA-256 of the archived text
5c1619603ff1e677715fe97a83dfecb38ecf24dbbd62c00c03bc9cdecb4c2950
Stable URL of this page
https://metraipolis.com/documento/dc_6795cb98bcd1

How to cite

Shunting yard algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Shunting_yard_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_6795cb98bcd1 (Metraipolis archive dc_6795cb98bcd1, sha256 5c1619603ff1e677715fe97a83dfecb38ecf24dbbd62c00c03bc9cdecb4c2950)
BibTeX
@misc{dc6795cb98bcd1,
  title = {Shunting yard algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Shunting_yard_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_6795cb98bcd1; sha256 5c1619603ff1e677715fe97a83dfecb38ecf24dbbd62c00c03bc9cdecb4c2950},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Shunting_yard_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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). The algorithm was invented by Edsger Dijkstra, first published in November 1961, 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.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Shunting yard algorithm» — https://en.wikipedia.org/wiki/Shunting_yard_algorithm
Wikidata Q1199602 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1199602
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Shunting_yard_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1361964542, consultata il 2026-10-15T16:10:47.070Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: f2c6f3fa331432d6495f4c5723cc30bbae1c33fe0072d9d9ab39b340e937d630