Angel_thunder
8.12.2003 14:48
Помогите с задачей!
Дан текстовый файл (input.txt). В нём на языке Паскаль написано математическое выражение. Что то вроде:
A:=3*(5+2) - B;
B:=12-C;
C:=3;
Необходимо подсчитать результат выражения (верхнего!). Учительница сказала использовать какой то алгоритм ... но вот какой и где его достать не сказала ;D.
Буду очень признателен, если подскажите, что это за алгоритм .... а ещё лучше если напишите прогу ;) ... хотя зная алгоритм прогу несложно написать!
Заранее благодарен!
А это возможно.Ты ничего не напутал.............
Программирование линейного вычислительного процесса!
trminator
8.12.2003 19:57
Я так думаю, для начала нужно получить одно арифметическое выражение 3*(5+2)-(12-3), затем его разобрать.
Как разбирать: назначь каждой арифметической операции какой-то приоритет. Например:
+ = 1
- = 2
* = 3
/ = 4
Скобки пусть этот приоритет, допустим, увеличивают в 10 раз.
Получится: 3 3 5 10 2 2 12 20 3,
где полужирным выделены коды операций. Потом строишь дерево разбора (двоичное, разумеется) этого выражения: находишь операцию с самым маленьким кодом (в этом примере это "-" - код 2), это будет вершина дерева. Левым поддеревом будет та часть, что слева, правым - та, что справа. Так повторяешь для каждого поддерева, пока все выражение не будет разобрано.
Потом вычислить выражение очень просто: берешь какой-либо узел-операцию с двумя листьями-операндами, листья прибиваешь, а узел делаешь операндом. Получается такое дерево:
[img]http://www.cs.karelia.ru/~pevgonen/sample.gif[/img]
рисунок ^
можно узел-оператор со знаком + заменить на операнд 7, а листья прибить. Аналогично и узел, в котором из 12 вычитается 3 - заменяем его на 9. И так далее, пока от дерева не останется один корень
Лексический анализ выражений
+
(напр.) польская запись
Angel_thunder
9.12.2003 13:08
Большое спасибо за алгоритм .... теперь мне не придётся здавать экзамен по ИВТ! :D