Уборочный двор: отсутствует аргумент для оператора

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

Например, 3 - (5 + ) неверно, потому что + отсутствует аргумент.

Непосредственно перед тем, как алгоритм достигает ), стек операторов содержит - ( +, а стек операндов содержит 3 5. Тогда это выглядит так:

  • он извлекает + из стека операторов
  • обнаруживает, что + является бинарным оператором
  • извлекает два операнда, применяет оператор и помещает результат (8) в стек операндов
  • затем он извлекает из стека соответствующий ( и продолжает

Итак, как я могу определить, что в + отсутствует аргумент? дополнительная похвала, если вы также обновите википедию :-)


c++ parsing algorithm wikipedia shunting-yard
person Giovanni Funchal    schedule 20.07.2010    source источник
comment
Я скорее выколю себе глаза, чем обновлю Википедию.   -  person Steven Sudit    schedule 20.07.2010
comment
userweb.cs.utexas.edu/~EWD/MCReps/MR35.PDF это связанное оригинальное описание от Dijikstra - это не сработало?   -  person Paul Nathan    schedule 20.07.2010
comment
@Paul: Эту статью немного трудно читать, ИМО.   -  person    schedule 20.07.2010

Ответы (2)


arrow_upward
5
arrow_downward

Для выражений, состоящих только из бинарных операторов, постфиксное выражение имеет инвариант, заключающийся в том, что в любом префиксе выражения количество операндов > количества операторов, и, в конце концов, эта разница равна ровно единице.

Таким образом, вы можете проверить правильность выражения RPN на каждом этапе маневровой станции, ведя текущий подсчет количества операндов - количества операторов. Если это значение падает ниже единицы или в конце становится больше единицы, у вас возникает ошибка.

Он не указывает на ошибку, но, по крайней мере, сообщает, что она есть.

(Примечание: я не пытался доказать вышеуказанный факт, но, похоже, это сработает)

person Community    schedule 20.07.2010
comment
+1 Свойство можно легко доказать с помощью структурной индукции допустимого выражения, состоящего только из числовых операндов и бинарных операторов. - person Eyal Schneider; 20.07.2010
comment
У меня также есть унарные операторы. Спасибо за ответ. - person Giovanni Funchal; 20.07.2010

arrow_upward
1
arrow_downward

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

Когда вы начинаете читать выражение, ожидайте префиксного оператора или операнда. Если вы читаете префиксный оператор, ожидайте префиксного оператора, операнда или открывающей скобки.

Если вы читаете операнд, ожидайте постфиксного или инфиксного оператора или закрывающей скобки.

Если вы читаете постфиксный оператор, ожидайте и инфиксный оператор или закрывающую скобку.

Если вы читаете инфиксный оператор, ожидайте префиксного оператора, операнда или открывающей скобки.

Если вы читаете открывающую скобку, ожидайте префиксного оператора, операнда или открывающей скобки.

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

Вы можете легко превратить эти «если» в переключатель. :)

person Calmarius    schedule 11.12.2010