Shunting-yard: отсутствующий аргумент оператору

Question

Я реализую shunting-yard algorithm. У меня возникают проблемы с обнаружением, когда отсутствуют аргументы операторам. wikipedia entry очень плохо по этой теме, и их код также вылетает для примера ниже.

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Если вы читаете оператор-оператор постфикса и оператор инфикса или закрывающая скобка.

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

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

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

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