Можно ли использовать алгоритм шунтирующего двора для проверки таких (недопустимых) выражений? [Дубликат]

Question

Можно ли использовать алгоритм шунтирующего двора для проверки таких (недопустимых) выражений? [Дубликат]

Я отвечу ужасным, нарисованным рукой комиком. Второе изображение является причиной того, что result является undefined в вашем примере кода.

3

algorithm validation language-agnostic expression shunting-yard

задан denver 14 April 2015 в 18:38

2 ответа

Хорошая дискуссия по алгоритмам Shunting Yard http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm В представленном там алгоритме используется ключевая идея стека операторов но имеет некоторую грамматику, чтобы знать, что следует ожидать дальше. Он имеет две основные функции E(), которые ожидают выражения и P(), которые ожидают либо префиксный оператор, переменную, число, скобки и функции.

Если мы говорим, что P обозначает некоторую последовательность префикса, а B - двоичный оператор, то любое выражение будет иметь вид

P B P B P

т.е. вы либо ожидаете последовательность префикса, либо двоичный оператор. Формально грамматика

E -> P (B P)*

, а P будет

P -> -P | variable | constant | etc.

. Это означает psudocode как

E() {
    P()
    while next token is a binary op:
         read next op
         push onto stack and do the shunting yard logic
         P()
    if any tokens remain report error
    pop remaining operators off the stack
}

P() {
    if next token is constant or variable:
         add to output
    else if next token is unary minus: 
         push uminus onto operator stack
         P()
}

. Вы можете развернуть это, чтобы обрабатывать другие унарные операторы, функции, скобки, суффиксные операторы.

2

ответ дан 0xcaff 4 September 2018 в 08:10

1

– denver 15 April 2015 в 13:55

Другие вопросы по тегам:

algorithm validation language-agnostic expression shunting-yard

Похожие вопросы:

score 2 · Accepted Answer

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

Support two states, ExpectOperand and ExpectOperator.

Set State to ExpectOperand
While there are tokens to read:
    If token is a constant (number)
        Error if state is not ExpectOperand.
        Push token to output queue.
        Set state to ExpectOperator.
    If token is a variable.
        Error if state is not ExpectOperand.
        Push token to output queue.
        Set state to ExpectOperator.
    If token is an argument separator (a comma).
        Error if state is not ExpectOperator.
        Until the top of the operator stack is a left parenthesis  (don't pop the left parenthesis).
            Push the top token of the stack to the output queue.
            If no left parenthesis is encountered then error.  Either the separator was misplaced or the parentheses were mismatched.
        Set state to ExpectOperand.
    If token is a unary operator.
        Error if the state is not ExpectOperand.
        Push the token to the operator stack.
        Set the state to ExpectOperand.
    If the token is a binary operator.
        Error if the state is not ExpectOperator.
        While there is an operator token at the top of the operator stack and either the current token is left-associative and of lower then or equal precedence to the operator on the stack, or the current token is right associative and of lower precedence than the operator on the stack.
            Pop the operator from the operator stack and push it onto the output queue.
        Push the current operator onto the operator stack.
        Set the state to ExpectOperand. 
    If the token is a Function.
        Error if the state is not ExpectOperand.  
        Push the token onto the operator stack.
        Set the state to ExpectOperand.
    If the token is a open parentheses.
        Error if the state is not ExpectOperand.
        Push the token onto the operator stack.
        Set the state to ExpectOperand.
    If the token is a close parentheses.
         Error if the state is not ExpectOperator.
         Until the token at the top of the operator stack is a left parenthesis.
             Pop the token off of the operator stack and push it onto the output queue.
         Pop the left parenthesis off of the operator stack and discard.
         If the token at the top of the operator stack is a function then pop it and push it onto the output queue.
         Set the state to ExpectOperator.
At this point you have processed all the input tokens.
While there are tokens on the operator stack.
    Pop the next token from the operator stack and push it onto the output queue.
    If a parenthesis is encountered then error.  There are mismatched parenthesis.

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