How to get an AST tree from Polish notation?

Question

Algorithms

The task is algorithmic and without reference to any language. At the input, reverse Polish notation includes left-associative operators, functions with an arbitrary number of parameters, and numbers. At the output, you need to get an AST tree. Any references and answers in the style of "mine was in such and such a book" are welcome.

Answer 1

sequentially read the expression, for each lexeme according to its type:
number -> create a node (NUMBER, value), put it on the stack;
unary operator -> remove a node (child) from the stack, create a node (UNARY OPERATION, type, child), put a new node on the stack;
binary operator -> remove two nodes from the stack (child1 and child2), create a node (BINARYOPERATION, type, child1, child2), put a new node on the stack;
function -> remove N nodes from the stack according to the number of function arguments (child1,... descendantN), create a node (FUNCTION, name, descendant1,... descendantN), put a new node on the stack;
At the end of the work on the correct expression, one node should lie on the stack, and it will be the root of the tree.

Answer 2

At the input, reverse Polish notation includes operators, functions, brackets and numbers.

There are no brackets in RPN.
And what is there to think? You need to drag the stack of met terminal symbols and ready nodes, and when an operator or function appears, create a new node, remove as many elements from the stack as the incoming operator / function expects and make them children, and add the newly created node back to the stack.

Answer 3

It is not entirely clear why there are brackets in Polish notation, and what they can mean in it.
For a regular Polish notation with operators and numbers, you can simply use the algorithm for calculating it. Only the result of the operations will not be values, but subtrees.