Обратная польская нотация

[FomaNeverov]

В общем алгоритм перевода в ОПН такой:

- число всегда отправляется в массив чисел
- первый знак всегда отправляется в стек знаков
- следующий знак сравнивается с уже находящимся в стеке: если его приоритет ниже или равный - знак из стека уходит в массив чисел, а "следующий" занимает его место в стеке. Если выше - просто добавляется в стек
- если строка заканчивается - остаток из стека переводится в массив.

Но этот алгоритм ошибается в строке типа: 1+2*3-4. В результате получается: 1 2 3 * 4 - +, тогда как правильное решение: 1 2 3 * + 4 - . Это происходит в полном соответствии с алгоритмом: в стек попадают знаки + и *, минус выталкивает более приоритетный * в массив чисел и занимает его место, в конце строки - и + переходят в массив чисел.

Где ошибка в алгоритме, что нужно поменять, что-бы он заработал правильно? Как это правильно сформулировать? Ну например, я бы предложил (костыль): если в стеке перед умножением находится минус или плюс - в массив выталкиваются оба знака. Но будет ли это всегда работать?

[Pphantom]

А переизобретать "сортировочную станцию" Дейкстры нужно по каким-то содержательным причинам или просто лень поинтересоваться уже имеющимися решениями?

P.S. Хотя, похоже, проблема даже не в переизобретении, а просто в непонимании алгоритма.

[slavav]

Не

Цитата:

если его приоритет ниже или равный - знак из стека уходит в массив чисел

, а "пока ...". Там не условный оператор, а цикл. В вашем примере минус вытолкнет из стека и умножение и плюс. Результат будет правильный.

[FomaNeverov]

То есть должен выталкивать, до тех пор, пока его приоритет ниже?

[slavav]

Ниже или равен.

[FomaNeverov]

Спасибо.

[arseniiv]

Приходите ещё когда добавите операцию возведения в степень.

[slavav]

arseniiv в сообщении #1399975 писал(а):

Приходите ещё когда добавите операцию возведения в степень.

Вы про правоассоциативность?

[arseniiv]

Именно.

[FomaNeverov]

arseniiv в сообщении #1399975 писал(а):

Приходите ещё когда добавите операцию возведения в степень.

А в чём там проблема? Приоритет возведения в степень выше, чем умножения/деления. Вроде всё работает:

[slavav]

Сравните:
3 - 3 - 3 $\to$ 3 3 - 3 - и
3 ^ 3 ^ 3 $\to$ 3 3 3 ^ ^.

Все операции до сих пор были левоассоциативными. Возведение в степень - правоассоциативная.

Расставляя скобки:
3 - 3 - 3 $\to$ (3 - 3) - 3 и
3 ^ 3 ^ 3 $\to$ 3 ^ (3 ^ 3).

[FomaNeverov]

Во, блин...

[arseniiv]

Можно добавить, насколько я помню, уже поминавшийся алгоритм сортировочной станции умеет даже не только ассоциативность учитывать и постфиксные операции, но даже обрабатывать простой синтаксис для функций: что-нибудь типа atanxy(2, 3). И на таком можно будет уехать весьма далеко, прежде чем понадобится какой-то более изощрённый парсинг.

[FomaNeverov]

slavav в сообщении #1400013 писал(а):

Все операции до сих пор были левоассоциативными. Возведение в степень - правоассоциативная.

А можно более сложное выражение для проверки? 3-3-3 и 3^3^3 показывает правильно.

[arseniiv]

Правильно — это именно 7625597484987? И $3-3-3$ даёт $-3$, и всё без учёта ассоциирования? Странно.

FomaNeverov в сообщении #1400015 писал(а):

Во, блин...

Кучу полезных отработанных вещей же легко найти. Хотите парсер — погуглите parsing algorithms (упомянутый тоже бы нашёлся, я его в своё время нашёл из ничего). Их куча и древних, и современных, разных цветов и даже готовые библиотеки. Простой и гибкий наколенный велосипед можно написать с помощью Pratt parsers, хотя если для вашего языка есть парсерные комбинаторы, это куда удобнее. Но не все библиотеки комбинаторов дают хорошо реагирующий на ошибки разбора парсер (с точки зрения понятности пользователю, где не так), плюс иногда можно написать весьма медленный код, проверяющий много лишнего (как и с велосипедом с нуля). Наконец алгоритмы, берущие готовую грамматику и компилирующие из неё автоматы. Но это уже полноценный микроскоп не для гвоздей. Имплементировать их и парсерные комбинаторы на коленке тоже не следует. А вот при надобности писать токенизатор его можно будет сделать с помощью регулярных выражений (хорошо если компилируемых и имеющих sticky mode).