Пишу программу на C под консоль - строковый калькулятор (пока всего 4 арифметических действия: +,  -,  *,  /). Работает по известному принципу - считываем строку, преобразуем в арифметическое выражение, выводим подсчитанный результат.
Думала реализовать это с помощью  обратной польской нотации ( с использованием односвязного списка и  стекового пpиоpитета опеpаций), но столкнулась с кое-какими проблемами, самая главная из которых, с унарным минусом. Искала в инете варианты решения, но ничего удобоваримого не нашлось.
Например, вот такое арифметическое выражение подсчитывается правильно: (2-1)*(5+4) - 1.
А такое уже нет: 7*(-8). Такое, тоже, нет: (-5)*(-9). Ошибка возникает именно из-за этих приоритетов в стеке. Коротко опишу принцип этой ОПН на 2-ом примере (7*(-8)), потому что, вряд ли, кто-нибудь спешл фо ми полезет его вспоминать =):
1. Считываем первый символ, так как это число, записываем его в выходную строку;
2. Умножить - (имеет самый высокий приоритет (у "поделить" такой же), далее идут "плюс" и "минус", самый низкий приоритет имеет '('). Стек, куда мы записываем операции (т. е. +,  -,  *,  / или (), еще пуст, поэтому мы заносим в него *;
3. ( - открывающую скобку всегода заносим в стек;
4. Минус - т. к. он имеет приоритет выше, чем у открывающей скобки, то мы и его заносим в стек;
5. 8 - записываем в выходную строку;
6. ) - т. к. это закрывающая скобка, то мы выталкиваем из стека операции и записываем их в выходную строку, пока не наткнёмся на открывающую скобку.
Выражение закончилось, а в стеке еще осталась не переписанная в выходную строку операция *. Записываем ее туда.
В итоге, мы получили такое вот выражение: 78-*
Далее я использовала такой алгоритм вычисления полученных после ОПН выражений:
1. Если очередной символ выходной строки - число, то кладем его в стек. 
2. Если очередной символ - знак операции, то извлекаем из стека два верхних числа, используем их в качестве операндов для этой операции, затем кладем результат обратно в стек. 
В конце в стеке остаётся одно число - результатом выражения.
А здесь, получается вот что: 7-8 = -1. 
Вот так вот, не знаю, что придумать. Переделывать не хочется, да и времени нет. Посоветуйте что-нибудь, пжлста. =)

Разумным было бы в процессе преобразования в ОПН использовать в качестве выходных данных не строку, а массив(а точнее vector).
Что-то вроде этого:

Тогда ты сможешь во время вычислений различать обычный минус от унарного минуса.
Как отличить унарные плюс/минус от обычных на этапе преобразования в ОПН: заведи булеву переменную atStart, которая будет равна true  тогда и только тогда, когда ты находишься в самом начале выражения или сразу за открывающейся скобкой. Тогда, когда ты встретишь плюс или минус, то atStart будет true когда встретивший оператор унарный и false иначе.

Это сообщение отредактировал(а) archimed7592 - 8.9.2007, 06:30

Спасибо, хороший совет. Но я не стала переделывать, просто посчитала, как ты и советовал, унарные минусы, если они идут в самом начале выражения или сразу после открывающей скобки. В стек эти минуса не добавляла. Потом в конце, при подсчете итогого результата просто делала проверку на четность этих унарных минусов, если их оказывалось нечетное количество, то просто домножала результат на -1.

Это сообщение отредактировал(а) marra - 8.9.2007, 15:35

Ну и посчитай своим калькулятором сколько будет 1+2*(-3)  

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

Да, ты прав.    Сделала с заменой на спецсимвол и выводом в ту же строку. Вроде, нормально считает. Осталось еще как-нибудь реализовать подсчет вещественных чисел, потому как работает этот калькулятор только с int(ами). Не уверена, что ОПН для этого подойдет, хотя я еще не пробовала. Тебе еще раз спасибо. =)

Подойдёт. Подойдёт даже для вычисления очень сложных выражений, содержащих и переменные и ф-ции аля sin/cos.

Покажи как ты считываешь число сейчас.

Число я считываю так:
(создание входной строки)

Возникало много проблем потом в момент создания выходной строки, потому что, например, нужно было как-то правильно реагировать на ввод чисел большИх разрядов (100, 1000 и т. д.) и вещественных, потому что ОПН это как-то не предусматривает. Поэтому я делала вот что: сначала пробегалась по входной строке, если встречалось число, то переписывала его в выходную строку и после ставила спецсимвол, если натыкалась на точку, то просто ее переписывала в выходную строку (например, при считывании выражения 7-8 получалось 7!8!-,  а 1.2+3.5 => 1.2!3.5!+). Потом, во время работы со стеком и полученной выходной строкой - я бегала по строке, пока не наталкивалась на этот спецсимвол (!), подсчитывала количество знаков до запятой, если встречалась точка, то и количество знаков после запятой. Потом возвращалась в начало строки, и те числа, что шли до запятой, по порядку умножались на 10, возведенное в степень, равную соответственно количеству знаков до запятой, а степень уменьшалась для каждого следующего числа на единицу. То же самое для чисел после запятой, только они делились на 10 в нужной степени, а степень увеличивалась. Потом, полученные результаты складывались и записывались в стек (например, запись числа 12.23 выглядела как сложение двух чисел = 12+0.23). Не знаю, понятно ли я объяснила. =)

Это сообщение отредактировал(а) marra - 11.9.2007, 16:56

ОПН - это всего лишь способ записи выражений и это не обязательно должна быть строка. К примеру, как я уже показывал - можно хранить данные в векторе объектов - тогда никаких "проблем" с разрядам и десятичной точкой не будет.


Я особо не вникал, но вечатление сложилось плачевное.
Писать за тебя не буду(у меня в принципе валяется где-то не одна версия этих калькуляторов на С++, C# и Java, если не ошибаюсь), но идеей помогу: разбей ф-циональность на несколько ф-ций. К примеру:
преобразование инфиксное выражение -> постфиксное(ОПН)
getToken - выдирает из строки очередную лексему
parseToken - парсит лексему
processToken - обрабатывает лексему