Python-сообщество

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

Задана строка, содержащая арифметическое выражение. В записи допускаются цифры, символы ‘+’, ‘-‘, ‘*’, ‘/’, ‘.’ и круглые скобки. Вычислить выражение. При вычислении выражения следует учитывать порядок выполнения арифметических действий. Если выражение вычислить невозможно – выдать сообщение об ошибке.
Исходные данные
В единственной строке находится арифметическое выражение. В выражении могут использоваться символы 0-9, +, -, *, / и пробел.
Результат
В единственной строке вывода вывести значение выражения или «ERROR» если выражение содержит ошибки или не может быть вычислено.
Пример
Исходные данные
2+2*2-(2/2+2)
Результат
3

Singularity

В алгоритме будет использоваться два стека: стек операций (в котором будет храниться информация об арифметических действиях, производимых при вычислении) и стек операндов (в котором будет храниться информация о числах, над которыми производятся действия). Как следует из назначения стека операндов, его элементы должны быть такого типа, который может хранить действительные числа (в записи выражения допустима десятичная точка). Стек операций удобно сделать символьным.
Алгоритм вычисления выражения строится следующим образом. Посимвольно просматривается исходная строка. Если текущий элемент строки – цифра, то выделяется число, в запись которого она входит, и заносится в стек операндов. Если встречается символ открытой скобки или операции умножения или деления, то они заносятся в стек операций. Если встречаются операции сложения, вычитания или закрытой скобки, то запускается процедура вычисления уже разобранной и находящейся в стеках части выражения. После этого операции сложения и вычитания заносятся в стек операций, а закрытая скобка удаляется вместе с соответствующей ей открытой. Если в стеке операций соответствующая открытая скобка отсутствует после частичного вычисления выражения, то в записи выражения допущена ошибка и выводится соответствующее сообщение. При достижении конца строки вычисляется оставшаяся в стеках разобранная часть выражения.
Вычисление частично разобранного выражения происходит следующим образом. До тех пор, пока в стеке операций находятся операции и очередная из них - не открытая скобка, со стека операндов снимается два числа (первое число - это второй операнд, а второе из снимаемых чисел - первый, т.к. в стеке порядок следования элементов меняется на противоположный) и над ними производится соответствующее действие. Результат вычисления заносится в стек операндов и в дальнейшем используется как операнд при вычислении следующих операций. Следует обратить внимание на отслеживание деления на 0, т.к. это действие считается недопустимым и должно приводить в выдаче сообщения об ошибке. Вычисления проводятся до первой открытой скобки в стеке операций по причине того, что действия в скобках выполняются до всех остальных действий. Таким образом, пока не будет получено число, равное результату выполнения действий в скобках, выполнение остальных операций временно откладывается (они запоминаются в стеке).
После достижения конца строки необходимо снять результат вычислений со стека операндов и проверить, не осталось ли значений в стеках. Если стеки не пусты, то в выражении были допущены ошибки, и необходимо вывести соответствующее сообщение.

stack = []
stack.append(something)
stack.pop()

Отредактировано Singularity (Март 12, 2014 20:08:34)

Singularity

Zubr
посмотреть есть ли там что-то кроме цифр и точки

Спасибо за наводки, буду думать.

Zubr
Вот я не пойму как в строке EXPRESION проверить числа там или нет

Singularity
мне лень это делать. Погугли наверно кто-то уже такое делал

py.user.next

Zubr
А скажите название книги?

Zubr
Появилась еще идея с обратной польской записью.

Отредактировано py.user.next (Март 13, 2014 11:34:44)

Прикреплённый файлы:
progmat.jpg (98,6 KБ)