Обязательно ли конвертировать из инфикса в постфикс и затем строить AST на математических оценщиках?

Question

Я делаю синтаксический анализатор математических выражений, который анализирует текст в абстрактном синтаксическом дереве (и я не очень разбираюсь в этом).

Я читал в Википедии, что можно использовать Алгоритм маневрового двора для анализа линейной последовательности токенов в Обратная польская запись или в AST на себе, но я не смогчтобы найти примеры прямого infix-to-AST анализа с помощью Shunting-yard.

Сейчас я использую Shunting-yard для преобразования из infix в postfix нотация и затем использование такого вывода для построения AST.

Это хорошая практика, чтобы преобразовать выражение в postfix нотацию и затем построить AST из него или ябыть немного неуклюжим?

Answer 1

Чтобы шунтирующий завод напрямую генерировал AST, вывод должен быть изменен на стек узлов.

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

Самое большое изменение - это то, что происходит, когда оператор выталкивается из стека операторов.Если это двоичный оператор, то последние два узла в выходном стеке выталкиваются, новый двоичный узел создается с этими узлами в качестве дочерних и перемещается обратно в выходной стек.

В псевдокоде

Stack<Node> output
Stack<Operator> operators

function popOperator
    Operator op = operators.pop()
    Node right = output.pop()
    Node left = output.pop()
    Node n = makeNode( op, left, right )
    output.push(n)