Кіріспе
Инфикс белгісімен синтаксисті постфикс белгісіне талдау алгоритмі. Компьютер ғылымында, штангалық алаң алгоритмі – инфикс белгісінде берілген арифметикалық немесе логикалық өрнектерді, немесе олардың комбинациясын талдау әдісі. Ол постфикс белгісінен (Реверс поляк белгісі – RPN) тұратын жол немесе абстрактты синтаксистік ағаш (AST) құра алады. Алгоритмді Эдсгер Дейкстра ойлап тапты және оны "штангалық алаң" алгоритмі деп атады, себебі оның жұмысы теміржол шаңға тарту алаңының жұмысына ұқсас. Дейкстра бұл алгоритмді алғаш рет Математикалық орталықтың MR 34/61 есебінде сипаттады. RPN есептеуі сияқты, штангалық алаң алгоритмі де стекке негізделген. Инфикс өрнектер – көптеген адамдар қолданатын математикалық жазу формасы, мысалы "3 + 4" немесе "3 + 4 × (2 − 1)". Айналдыру үшін екі мәтіндік айнымалы (жол) қолданылады: кіріс және шығыс. Сондай-ақ, шығыс кезегіне әлі қосылмаған операторларды сақтайтын стек бар. Айналдыру үшін бағдарлама әрбір символды ретімен оқиды және осы символға сәйкес әрекет етеді. Жоғарыдағы мысалдардың нәтижесі (кері поляк белгісінде) тиісінше "3 4 +" және "3 4 2 1 − × +" болады. Штангалық алаң алгоритмі барлық жарамды инфикс өрнектерді дұрыс талдайды, бірақ барлық жарамсыз өрнектерді қабылдамайды. Мысалы, "1 2 +" жарамды инфикс өрнегі емес, бірақ "1 + 2" деп талданады. Дегенмен, алгоритм сәйкес келмейтін жақшаларды қабылдамайды. Кейіннен штангалық алаң алгоритмі операторлардың басымдығын талдауға жалпыландырылды.
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 and named the "shunting yard" algorithm because its operation resembles that of a railroad shunting yard. Dijkstra first described the shunting yard algorithm in the Mathematisch Centrum report MR 34/61. 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.
Графикалық сурет
Үш жолды темір жол торабын пайдалана отырып, алгоритмнің графикалық иллюстрациясы. Кіріс бір кезде бір символ бойынша өңделеді: егер айнымалы немесе сан табылса, ол тікелей шығысқа а), с), е), h) көшіріледі. Егер символ оператор болса, ол оператор стегіне b), d), f) салынады. Егер оператордың басымдылығы стектің үстіндегі операторлардың басымдылығынан төмен болса немесе басымдылықтар тең болса және оператор сол жақтан байланысты болса, онда ол оператор стектен алынып, шығысқа g) қосылады. Соңында, стектен қалған операторлар алынып, i) шығысына қосылады.