обработка цепных унарных операторов в маневровом дворе - PullRequest
Новая
       37

обработка цепных унарных операторов в маневровом дворе

0 голосов
/ 31 октября 2018

Я посмотрел на вики-страницу для маневрового двора , поскольку у меня была проблема с обработкой цепочек унарных операторов минус в моем маневровом дворе, но алгоритм вики не справился с этим.

Алгоритм Wiki для справки: 

/* This implementation does not implement composite functions,functions with variable number of arguments, and unary operators. */

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

Предположим, у меня есть следующее выражение ---1, я ожидаю, что вывод rpn будет 1---, однако на самом деле происходит следующее:

итерация 1: operator stack: [] output queue: []

токен, который нужно прочитать - это -, поэтому мы помещаем в стек операторов

итерация 2: operator stack: [-] output queue: []

маркер, который нужно прочитать - -. В стеке операторов -, и мы должны поместить его в очередь вывода. Затем мы помещаем токен в стек операторов.

итерация 3: operator stack: [-] output queue: [-]

ОШИБКА - у нас еще не должно быть - в очереди вывода. (Продолжать не буду, так как бессмысленно)

...