Маневровый двор: недостающий аргумент оператору

Question

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

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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

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

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

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