Бинарные деревья, построить дерево на основе предварительного заказа

Question

построить дерево, учитывая его порядок, достаточно просто. Но, допустим, вы должны построить дерево на основе его предварительного заказа (например, + + y z + * x y z).

Легко видеть, что + является корнем, и как продолжить в левом поддереве оттуда. Но ... как вы узнаете, когда вы должны "переключиться" на правильное поддерево?

Answer 1

Обычно заказ считается трудным случаем.

Для предварительного заказа у вас просто будет такая грамматика.

expr ::= operator expr expr | var

За оператором следует точно два правильно сформированных выражения . Это можно легко проанализировать с помощью рекурсии

Если вы проанализируете дерево и получите переменную, верните переменную. Если вы анализируете дерево и получаете оператора, анализируйте два следующих дерева как поддерево справа / слева.