Как построить двоичное дерево выражений из префикса?

Question

something like this (* (+ 1 2 3) 5)
Оператор типа *, + может иметь более двух операндов.

Answer 1

Чтобы сделать префиксную нотацию с неограниченным количеством операндов, вы должны определить некоторые дополнительные правила для скобок открытия/закрытия (и это не то, что префиксная нотация вообще).

Простой синтаксический анализатор принимает операцию, первый операнд и добавляет другие операнды один за другим. На каждом шаге просто создайте новый операционный узел, левый операнд примет предыдущий (текущий) результат, правый операнд возьмет новый извлеченный операнд.

Продолжайте движение до конца входного или закрывающего кронштейна. Не удаляйте закрывающий кронштейн со входа - его следует обрабатывать в части разбора open-close, а не в синтаксическом анализе.

Принимая операнд прост:

• "(" -> идти глубже и разобрать подвыражению до ")".
• Различные операции -> перейти глубже и разбор выражения под.
• Одну и ту же операционную камеру можно просто игнорировать, но это зависит от вас.
• Константа (или переменная, если у вас есть) -> сделать подвыражение операнда.