Будучи дилетантом в области разработки приложений, я испытал сложности с пониманием алгоритма работы обратной польской нотации, а если быть точнее — алгоритма подготовки стека. Делу так же мало помогли статьи в «интернетах».
Все началось с того, что я затеял создание несложного интерпретатора для собственного проекта. Для решения сложных выражений на выбор было два алгоритма: рекурсивный спуск и обратная польская запись. Очевидная простота и подход к решению задачи (а может и само название) позволили последнему стать предметом для изучения.
Делу помогли две статьи. Одна из них на википедии, а вторая была написана замечательным пользователем хабра, GORKOFF, который объяснил все буквально «на пальцах».
Однако до конца я так и не понял тот важный вопрос: как же построить стек?
Читать полностью »