Реализицая обратной польской нотации, как быть с унарным минусом?

Question

[bakunovdo]

Я пытаюсь решить одну кату, где надо распасить строчку с математическим выраженем.
И нашел что подобное решается с помощью ОПН, ее и взял за основу, но с унарным минусом там предлагается либо замена символа либо преобразования выражения, например для -3 в ОПН -> 0 3 - . Я остановился на замене символа, заменю на ±.
Проблема с выражениями вида: -(-1 + 2) , в моей реализации польской это будет как ± ± 1 2 +. как вставлять правильно унарник?
И приложу свой код. Я просто очень хочу уже решить эту задачу с парсером. Пару дней ее мучаю. В кате осталось всего 2 теста пройти, надо как то учесть унарный перед скобками, как не знаю. Я так понимаю у меня не там вставляется ±.

Comments

[Akina]

Проблема с выражениями вида: -(-5 + 2) , в Польской это будет как ± ± 1 2 +.

Да ну? А по-моему, ± + 2 ± 5. ЕМНИП в польской нотации оператор не может быть в конце в принципе. Единица же, внезапно заменившая пятёрку - надо понимать, обычная очепятка.

[bakunovdo]

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

[Lynn «Кофеман»]

Наоборот, в ОПН сначала операнды, потом операция, так что для -(-5+2) должно быть
5 +- 2 + +-

[Akina]

Пардон, спутал обратную польскую в названии темы с прямой (префиксной) в тексте вопроса, где собственно и смотрел.

В обратной польской это будет 5 ± 2 + ±.

А показанное ± ± 1 2 + в принципе не может быть обратной польской записью (у которой операнды располагаются перед оператором, т.е. она всегда начинается операндом и всегда завершается оператором).

как быть с унарными операторами

Унарный минус - это просто краткая запись "0 -"., считай, что там пропущенный ноль.

[Денис Загаевский]

Akina, нет, это не просто короткая запись. У унарного минуса приоритет выше, чем у умножения, это тоже важно.

bakunovdo, "замена" это норм, но я бы на твоём месте ушёл от символов, заменив их специальными объектами - токенами.

[bakunovdo]

Денис Загаевский, мне кажется это сложнее выйдет, и затратнее

[Денис Загаевский]

bakunovdo, в каком смысле затратнее?

[bakunovdo]

Денис Загаевский, скорее хотел сказать, что токенизацию и потом парсер делать для такой задачки, это overhead

[Денис Загаевский]

bakunovdo, ну фиг знает. Рекурсивный спуск по выражению пишется примерно не приходя в сознание. Зато будет точно работать нормально, а не на соплях.

Answer 1

[Wataru]

Если обратная нотация, то знак ± должен, как и бинарные операции, идти после операндов. Тогда -(-1 + 2) становится 1 ± 2 + ±. По ± надо менять знак числа на верхушке стека.

Соответственно в парсере, если видите унарный минус перед скобками, то переводите скобки в нотацию, а потом дописываете ±.

Comments

[bakunovdo]

Спасибо, что то становится на правильные места у меня, когда обрабатываю ее как операцию. и теперь -(-1 + 2) обрабатывает верно.
А как быть с 4.75 - -6 ? Правильно должно быть 4.75 6 ± - (такое срабатывает только если оберну -6 в скобки. Но у меня результат получается в ОПН такой: 4.75 - 6 ±, какая последовательность?

[Wataru]

bakunovdo, Да, правильная ОПН 4.75 6 ± -. Чтобы она получалась надо так делать: если "-" идет после числа, или закрывающей скобки, то сначала парсите один терм дальше и потом ставите "-". Если "-" после операции, открывающей скобки или в начале строки - то, опять, парсите терм за ним и потом ставите "±".

[bakunovdo]

Wataru, вообщем, я отмечу это решение, спасибо вам за подсказки, но похоже у меня не получится решить, не знаю как это в мой алгоритм нотации внести)