Метод Е.В.Дикстры основан на использовании стека с приоритетами, позволяющего изменить порядок следования знаков операций в выражении так, что получается обратная польская запись. Простейший вариант этого метода применим только к простым арифметическим и логическим выражениям, содержащим простые переменные, знаки арифметических и логических операций, знаки операций отношения и круглые скобки.

Ограничители Приоритеты ( [ if 0 = ) ] then else 1 принадлежность к множеству 2 "или" 3 "и" 4 "отрицание" 5 > >= = # =< < 6 + - 7 * / 8 Таблица 1

Каждому ограничителю, входящему в выражение, присваивается приоритет (табл. 1). Для знаков операций приоритеты возрастают пв порядке, обратном старшинству операций. Скобки имеют низший приоритет. Арифметическое или логическое выражение рассматривается как входная строка символов. Входная строка просматривается слева направо. Операнды переписываются в выходную строку, а знаки операций помещаются вначале в стек операций. Если приоритет входного знака равен нулю или больше приоритета знака, находящегося в вершине стека, то новый знак добавляется к вершине стека. В противном случае из стека "выталкивается" и переписывается в выходную строку знак, находящийся в вершине, а также следующие за ним знаки с приоритетами, большими или равными приоритету входного знака. После этого входной знак добавляется к вершине стека. Особенности имеет лишь обработка скобок. Открывающая круглая скобка, имеющая "особый" приоритет ноль, просто записывается в вершину стека и не выталкивает ни одного знака. в то же время ее не может вытолкнуть ни один знак, кроме закрывающей скобки.

Закрывающая скобка имеет приоритет 1, не превосходящий приоритета любой операции. Поэтому появление закрывающей скобки вызовет выталкивание всех знаков до ближайшей открывающей скобки включительно. В стек закрывающая скобка не записывается.

Открывающая и закрывающая скобки как бы взаимно уничтожаются и в вызодную строку не переносятся. После просмотра всех символов входной строки происходит выталкивание всех оставшихся в стеке символов и дописывание их к выходной строке.