Как из польской нотации получить АСТ дерево?

Question

[Vovaka]

Задача алгоритмическая и без привязки к какому либо языку. На входе обратная польская запись включающая в себя операторы лево-ассоциативные, функции с произвольным числом параметров и числа. На выходе необходимо получить АСТ дерево. Приветствуются любые отсылки и ответы в стиле "помоему было в такой-то книге".

Answer 1

[Rsa97]

последовательно читаем выражение, для каждой лексемы по её типу:
число -> создать ноду (ЧИСЛО, значение), положить её на стек;
унарный оператор -> снять со стека ноду (потомок), создать ноду (УНАРНАЯОПЕРАЦИЯ, тип, потомок), положить новую ноду на стек;
бинарный оператор -> снять со стека две ноды (потомок1 и потомок2), создать ноду (БИНАРНАЯОПЕРАЦИЯ, тип, потомок1, потомок2), положить новую ноду на стек;
функция -> снять со стека N нод по числу аргументов функции (потомок1,... потомокN), создать ноду (ФУНКЦИЯ, имя, потомок1,... потомокN), положить новую ноду на стек;

В конце работы по корректному выражению на стеке должна лежать одна нода, она и будет корнем дерева.

Answer 2

[jcmvbkbc]

На входе обратная польская запись включающая в себя операторы, функции, скобочки и числа.

Нет скобочек в RPN.

И что тут думать? Нужно тащить стек встреченных терминальных символов и готовых узлов, а при появлении оператора или функции создавать новый узел, снимать со стека столько элементов сколько ожидает пришедший оператор/функция и делать их его детьми, и добавлять обратно в стек только что созданный узел.

Comments

[Vovaka]

да. сейчас подправлю. Но суть та же.

Answer 3

[tsarevfs]

Не совсем понятно зачем в польской нотации скобочки, и что они в ней могут означать.
Для обычной польской записи с операторами и числами можно просто использовать алгоритм ее вычисления. Только результатом операций будут не значения а поддеревья.

Comments

[Vovaka]

Ок. Как ?

[Миша Кринкин]

@Vovaka а здесь en.wikipedia.org/wiki/Reverse_Polish_notation поискать не пробовали?

[tsarevfs]

@Vovaka Ахо, Ульман, "Компиляторы. Принципы, технологии, инструментарий" 2.3.1 постфиксная запись. Только, например, вместо суммы записываешь что-то вроде Node("add", a, b)