2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Обратная польская нотация
Сообщение18.06.2019, 13:25 
В общем алгоритм перевода в ОПН такой:

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

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

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

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

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

 
 
 
 Re: Обратная польская нотация
Сообщение18.06.2019, 13:35 
Не
Цитата:
если его приоритет ниже или равный - знак из стека уходит в массив чисел
, а "пока ...". Там не условный оператор, а цикл. В вашем примере минус вытолкнет из стека и умножение и плюс. Результат будет правильный.

 
 
 
 Re: Обратная польская нотация
Сообщение18.06.2019, 13:59 
То есть должен выталкивать, до тех пор, пока его приоритет ниже?

 
 
 
 Re: Обратная польская нотация
Сообщение18.06.2019, 14:15 
Ниже или равен.

 
 
 
 Re: Обратная польская нотация
Сообщение18.06.2019, 14:19 
Спасибо.

 
 
 
 Re: Обратная польская нотация
Сообщение18.06.2019, 18:18 
Приходите ещё когда добавите операцию возведения в степень.

 
 
 
 Re: Обратная польская нотация
Сообщение18.06.2019, 18:43 
arseniiv в сообщении #1399975 писал(а):
Приходите ещё когда добавите операцию возведения в степень.

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

 
 
 
 Re: Обратная польская нотация
Сообщение18.06.2019, 19:22 
Именно.

 
 
 
 Re: Обратная польская нотация
Сообщение18.06.2019, 20:45 
arseniiv в сообщении #1399975 писал(а):
Приходите ещё когда добавите операцию возведения в степень.

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

Изображение
Изображение

 
 
 
 Re: Обратная польская нотация
Сообщение18.06.2019, 21:04 
Сравните:
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).

 
 
 
 Re: Обратная польская нотация
Сообщение18.06.2019, 21:17 
Во, блин...

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

 
 
 
 Re: Обратная польская нотация
Сообщение18.06.2019, 21:42 
slavav в сообщении #1400013 писал(а):
Все операции до сих пор были левоассоциативными. Возведение в степень - правоассоциативная.

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

 
 
 
 Re: Обратная польская нотация
Сообщение18.06.2019, 21:49 
Правильно — это именно 7625597484987? И $3-3-3$ даёт $-3$, и всё без учёта ассоциирования? Странно.

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

 
 
 [ Сообщений: 28 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group