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