Как бы вы объяснили данный алгоритм Алгоритм сортировочной станции?

В середине нулевых в институте на лекции, посвященной переводу в Обратную Польскую Запись, алгоритм давался как данность.
А объяснение заменялось его трассировкой.

Как бы вы объяснили суть алгоритма, чтобы человек не зубрил шаги алгоритма?

Б>Как бы вы объяснили суть алгоритма, чтобы человек не зубрил шаги алгоритма?

Пусть попробует написать свой. Получится +/- вариант одного из таких алгоритмов.
(кстати нередкая задача на собеседовании чем заменить задачу по развороту списка)

Б>В середине нулевых в институте на лекции, посвященной переводу в Обратную Польскую Запись, алгоритм давался как данность.
Как и все алгоритмы, написанные, например, в Кормене.
Б>А объяснение заменялось его трассировкой.
Б>Как бы вы объяснили суть алгоритма, чтобы человек не зубрил шаги алгоритма?
а) зачем учить такие алгоритмы наизусть?
б) надо просто попробовать написать алгоритм на известном языке и прогнать в отладчике, посмотрев стек

Здравствуйте, m2user, Вы писали:
M>Пусть попробует написать свой. Получится +/- вариант одного из таких алгоритмов.

У меня в таких случаях обычно Метод рекурсивного спуска получается)
Хотя, возможно, если заменить рекурсию на явное использование стека, то получится эквивалентный код

Но, я помню, что когда написал простейшую грамматику для скобочных выражений и закодировал ее, а потом переписал рекурсию на стек, то прямого соответствия не получилось. Оказалось, что как минимум грамматика была немного избыточной (можно лаконичнее), что порождало больше рекурсивных вызовов и больше неочевидных манипуляций со стеком, чем необходимо.

Здравствуйте, Быдлокодер, Вы писали:

Б>Как бы вы объяснили суть алгоритма, чтобы человек не зубрил шаги алгоритма?

Я бы подошёл в несколько приёмов.
1) продемонстрировал бы на чём-то попроще (на обходе списка или дерева, например), как рекурсию со стеком вызовов заменить на цикл со стеком данных
2) продемонстрировал бы, как один и тот же алгоритм разбора (пусть обычный рекурсивный) параметризуется разными исполнителями: генератором полиза, генератором дерева, немедленным вычислителем
3) соединил бы их меж собой

А заодно, показал бы, что у языка арифметических выражений — не просто контекстно-свободная, а операторная грамматика, что позволяет упростить парсер до стека операндов и операторов.
Но это уже потянет за собой не просто Кормена с Дейкстрой, а Ахо с Ульманом.

Здравствуйте, Быдлокодер, Вы писали:

Б>Как бы вы объяснили данный алгоритм Алгоритм сортировочной станции?

Начал бы с того, что объяснил на пальцах алгоритм вычисления значения выражения. Он же интуитивно понятный — вычислили аргумент1, вычислили аргумент2, вычислили результат операции.
А затем перешёл бы от него к алгоритму построения программы в RPN, где помимо значений в "стек" можно складывать операции.

Удобнее объяснять этот алгоритм не над входной цепочкой, а над AST.
Уже потом мы берём и объединяем алгоритм построения AST с алгоритмом преобразования AST в RPN, т.к. само дерево нам не нужно.