Handling дополнительные операторы в маневровых дворе

Question

Учитывая вход так: 3+4+ алгоритм превращает его к 3 4 + +

я могу найти ошибку, когда пришло время, чтобы выполнить выражение постфикса. Но можно ли это заметить во время конверсии?

(статья Wikipedia и интернет-статей, которые я читал, не обрабатывать этот случай)

Благодарим вас

Answer 1

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

регулярное выражение выглядит следующим образом:

PRE* OP POST* (INF PRE* OP POST*)* 

где:

PRE is a prefix operator or (
POST is a postfix operator or) 
INF is an infix operator 
OP is an operand (a literal or a variable name) 

Связанная с вами страница в Википедии включает вызовы функций, но не subscript подписи массива; если вы хотите обрабатывать эти случаи, то:

PRE is a prefix operator or (
POST is a postfix operator or) or ] 
INF is an infix operator or (or , 
OP is an operand, including function names 

Одна вещь, чтобы отметить в вышеописанном что PRE и INF в непересекающихся контекстах; то есть, если PRE действительно, то INF нет, и наоборот. Это означает, что использование одного и того же символа как для префиксного оператора, так и для инфиксного оператора недвусмысленно. Кроме того, PRE и POST находятся в непересекающихся контекстах, поэтому вы можете использовать один и тот же символ для операторов префикса и постфикса. Однако вы не можете использовать один и тот же символ для операторов postfix и infix. В качестве примера, рассмотрим C/C++ операторы:

- prefix or infix 
+ prefix or infix 
-- prefix or postfix 
++ prefix or postfix 

Я неявно использовал эту функцию выше, чтобы ( использоваться либо в качестве выражения окуня (эффективно приставкой) и как вызов функции (инфиксной, потому что он идет между имя функции и список аргументов, оператор «вызов»)

это наиболее распространенный для реализации, что регулярное выражение в качестве государственной машины, потому что есть только два состояния:

+-----+   +-----+ 
|State|-----OP---->|State| 
| 1 |<----INF----| 2 | 
|  |---+  |  |---+ 
+-----+ |  +-----+ | 
    ^ PRE  ^ POST 
    |  |   |  | 
    +------+   +------+ 

Мы могли бы назвать. Состояние 1 "Требуется операнд" и State 2 "имеют операнд". Простая реализация просто разделила алгоритм маневрового двора, представленный в википедии на две петли, что-то вроде этого (если вам не нравится goto, его можно устранить, но на самом деле это самый ясный способ представить конечный автомат).

want_operand: 
    read a token. If there are no more tokens, announce an error. 
    if the token is an prefix operator or an '(': 
    mark it as prefix and push it onto the operator stack 
    goto want_operand 
    if the token is an operand (identifier or variable): 
    add it to the output queue 
    goto have_operand 
    if the token is anything else, announce an error and stop. (**) 

have_operand: 
    read a token 
    if there are no more tokens: 
    pop all operators off the stack, adding each one to the output queue. 
    if a `(` is found on the stack, announce an error and stop. 
    if the token is a postfix operator: 
    mark it as postfix and add it to the output queue 
    goto have_operand. 
    if the token is a ')': 
    while the top of the stack is not '(': 
     pop an operator off the stack and add it to the output queue 
    if the stack becomes empty, announce an error and stop. 
    if the '(' is marked infix, add a "call" operator to the output queue (*) 
    pop the '(' off the top of the stack 
    goto have_operand 
    if the token is a ',': 
    while the top of the stack is not '(': 
     pop an operator off the stack and add it to the output queue 
    if the stack becomes empty, announce an error 
    goto want_operand 
    if the token is an infix operator: 
    (see the wikipeda entry for precedence handling) 
    (normally, all prefix operators are considered to have higher precedence 
    than infix operators.) 
    got to want_operand 
    otherwise, token is an operand. Announce an error 

(*) The procedure as described above does not deal gracefully with parameter lists; 
    when the postfix expression is being evaluated and a "call" operator is found, it's 
    not clear how many arguments need to be evaluated. It might be that function names 
    are clearly identifiable, so that the evaluator can just attach arguments to the 
    "call" until a function name is found. But a cleaner solution is for the "," handler 
    to increment the argument count of the "call" operator (that is, the open 
    parenthesis marked as "infix"). The ")" handler also needs to increment the 
    argument count. 

(**) The state machine as presented does not correctly handle function calls with 0 
    arguments. This call will show up as a ")" read in the want_operand state and with 
    a "call" operator on top of the stack. If the "call" operator is marked with an 
    argument count, as above, then the argument count must be 0 when the ")" is read, 
    and in this case, unlike the have_operand case, the argument count must not be 
    incremented.