3
Можно ли оценить дерево выражений (pre/postfix) без использования стека? Имел этот вопрос, говоря о деревьях в классе алгоритмов в школе. Я думаю, что нет.Оценка дерева выражений без стека
A
ответ
0
Да, вы можете.
Сделайте breadth first traversal дерева (как поиск, но делайте через все дерево). Вы можете сделать это с помощью vector/queue/list в итеративном режиме.
Как только вы закончите, вы можете вернуться назад по списку/вектору/очереди, сгенерированным на предыдущем шаге. В каждой точке вычислите значение узла в списке. Поскольку у вас есть все дети, которые уже были посещены (вы идете назад), все, что вам нужно сделать, это найти их значение и применить инструкции в узле.
Вы подумали об использовании рекурсивного подхода? –
@TimBiegeleisen: подол, без стека. –
Можете ли вы показать нам, как вы оцениваете дерево, используя стек? Я немного смущен. –