алгоритм маневрового двора, есть ли изменения?

Question

Я реализовал алгоритм маневрового двора на C ++ 11 в соответствии с тем, что упоминается в википедии:

Эта реализация не реализует составные функции, функции с переменным числом аргументов, и унарные операторы.

while there are tokens to be read:
    read a token.
    if the token is a number, then:
        push it to the output queue.
    else if the token is a function then:
        push it onto the operator stack 
    else if the token is an operator then:
        while ((there is a operator at the top of the operator stack)
              and ((the operator at the top of the operator stack has greater precedence)
               or (the operator at the top of the operator stack has equal precedence and the token is left associative))
              and (the operator at the top of the operator stack is not a left parenthesis)):
            pop operators from the operator stack onto the output queue.
        push it onto the operator stack.
    else if the token is a left parenthesis (i.e. "("), then:
        push it onto the operator stack.
    else if the token is a right parenthesis (i.e. ")"), then:
        while the operator at the top of the operator stack is not a left parenthesis:
            pop the operator from the operator stack onto the output queue.
        /* If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. */
        if there is a left parenthesis at the top of the operator stack, then:
            pop the operator from the operator stack and discard it
/* After while loop, if operator stack not null, pop everything to output queue */
if there are no more tokens to read then:
    while there are still operator tokens on the stack:
        /* If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. */
        pop the operator from the operator stack onto the output queue.
exit.

Как вы можете видеть, упоминалось, что этот алгоритм не работает с унарным оператором, предположим, что у меня есть один !, который сильнее всех других операторов, какие изменения я должен внести в свой алгоритм, если таковые имеются?

Некоторые Допустимые Примеры использования оператора !:

!1
! 1
! (1)
!(  1 + 2)

Плюс один небольшой вопрос, работает ли этот алгоритм иметь дело с неправильным синтаксисом, например 1==2 (я предполагал, что да)?

Answer 1

Вопрос 1:

Для того, чтобы ваш алгоритм работал, вы должны проанализировать префикс оператор ! перед инфиксными операторами , просто рассматривая его как открытую скобку ( (тогда вам нужно настроить виртуальную машину стека, чтобы разрешить такой оператор). Я предлагаю переместить проверку if на скобку перед оператором инфикса (она не сильно меняется, но более читаема). Я также скажу, что если вы хотите достичь таких вещей, как операторный приоритет , постфиксные операторы и операторы миксфикса все вместе, вам следует переключиться на парсер Pratt (с которым намного проще работать).

Вопрос 2:

Парсер здесь не обрабатывает операции типа 1 == 2, а только разбирает их. Виртуальная машина на основе стека имеет дело с ними, и 1 == 2 - прекрасное сравнение, поскольку предполагается, что она возвращает false. Это, если вы планируете использовать логические выражения, а также арифметические c выражения.

РЕДАКТИРОВАТЬ 1:

«твик» (который частично решает проблему): рассматривайте оператор как правоассоциативный и сделайте его приоритет выше, чем у других операторов.

РЕДАКТИРОВАТЬ 2:

Это (как указано в комментарии от @ dure ) - это просто настройка, так как il заставит синтаксический анализатор анализировать операторы префикса и постфикса без различия и требует дополнительных усилий, чтобы избежать ошибок.