Структуры данных: применение стеков
Оценка выражения и синтаксический анализ Калькуляторы, использующие обратную польскую запись, используют структуру стека для хранения значений. Выражения могут быть представлены в префиксной, постфиксной или инфиксной нотации, а преобразование из одной формы в другую может быть выполнено с использованием стека. Многие компиляторы используют стек для анализа синтаксиса выражений, программных блоков и т. д. перед переводом в низкоуровневый код. Большинство языков программирования являются контекстно-свободными языками, что позволяет их анализировать с помощью стековых машин. Поиск с возвратом (Backtracking) Другое важное применение стеков - поиск с возвратом (backtracking). Рассмотрим простой пример поиска правильного пути в лабиринте. Есть ряд точек, от начальной точки до пункта назначения. Начнем с одной точки. Чтобы добраться до конечного пункта, есть несколько путей. Предположим, мы выбрали случайный путь. Следуя определенному пути, мы понимаем, что выбранный нами путь неверен. По...