Лабораторная работа №24 по курсам «Языки и методы программирования»/
«Алгоритмы и структуры данных»: 8 факультет, 1 курс, 2 семестр, 2011/12
учебный год
Составить программу выполнения заданных преобразований арифметических выражений с применением
деревьев. Преобразование выражения в дерево рекомендуется осуществлять одним из известных методов
(Рутисхаузера, Дейкстры и др.). Операнды в обрабатываемых выражениях могут быть целого или веще-
ственного типа (по усмотрению преподавателя). Задания могут быть переформулированы и для булевско-
го типа. Преобразование выражения реализовать в виде набора подпрограмм. Программа должна вводить
и печатать выражения в исходном (текстовом) виде, преобразовывать их в деревья, выполнять заданные
преобразования путем обращения к подпрограммам и печатать результаты в виде дерева и в текстовом
представлении.
Для некоторых задач приводятся примеры, поясняющие постановку задачи. В примерах слева от
стрелки приводится фрагмент выражения до, а справа — после выполнения преобразования. Программа
должна обрабатывать все вхождения сходных фрагментов в анализируемых выражениях, а не только те,
что приведены в примерах.
Программу необходимо проверить на нескольких выражениях, среди которых должны быть выра-
жения, не содержащие преобразуемых элементов, содержащие ровно один такой элемент или несколько
элементов, подлежащих преобразованию, причем в «разных» местах дерева.
Варианты преобразований
1.	Упростить выражения, выполнив сложение:
2 + 3^5, (-2 + b + 4) * к (2 + Ь) * к.
2.	Упростить выражения, выполнив вычитание:
3-5 — -2, 5|5-3'2|5.
3.	Упростить выражения, выполнив умножение:
2*6*2 —> 4*6.
4.	Упростить выражения, выполнив деление:
4 * а/2	2 * а.
5.	Упростить выражения, выполнить возведение чисел в степень с целым показателем:
2 ~ 3 --+ 8.
6.	Упростить выражения, выполнив приведение подобных членов.
7.	Редуцировать выражения, заменив операцию умножения переменной на целое число п на сумму п
слагаемых:
а * 3 а + а + а.
8.	Редуцировать выражения, заменив операцию возведения переменной в целую степень п на произве-
дение п слагаемых:
а ~ 3 —> а * а * а.
9.	Умножение переменной на сумму заменить на сумму произведений.
10.	Умножение переменной на разность заменить на разность произведений.
11.	Вынести общие сомножители (переменные и константы) из суммы.
12.	Вынести общие сомножители (переменные и константы) из разности.
13.	Упростить выражения, убрав из него все произведения, в которых в качестве сомножителя исполь-
зуется нуль.
1
14.	Убрать из выражений все слагаемые, равные нулю.
15.	Убрать из выражений все сомножители, равные единице.
16.	Убрать из частных все делители, равные единице.
17.	Перемножить степени с одинаковыми основаниями (в простейшем случае можно рассматривать ос-
нования, состоящие из одной переменной или константы):
оУ 2 * а ~ к а ~ (2 + к).
18.	Вынести из произведений унарные минусы:
а * (—Ь) * 3	—(а * b * 3), а * (—Ь) * 4 * (—5)	а * b * 4 * 5.
19.	Вынести из частных унарные минусы:
а * (—Ь) * 3	—(а * b * 3), а * (—Ь) * 4 * (—5)	а * b * 4 * 5.
20.	Упростить сложные (многоэтажные) дроби:
(а/b)/с а/(Ъ * с), а/(Ъ/с)	(а/Ъ) * с.
21.	Заменить вычитание на сложение с противоположным числом, т. е. на сложение и унарный минус:
а — b * с а +(—(&* с)).
22.	Выполнить сложение и вычитание дробей:
ajb + с/d (а * d + b * c)/(b * d).
23.	Упростить дробь, сократив в числителе и знаменателе общие переменные и константы:
(а * b * 3)/(3 * b * с) а/с, а/(а *Ь)	1/Ь.
24.	Перемножить дроби:
(а/Ъ) * (с/d))	{а * с)/(b * d).
25.	Заменить степень с суммой в показателе на произведение степеней:
а ~ (b + с) а ~ b * а ~ с.
26.	Заменить степень с разностью в показателе на частное степеней:
а ~ (Ь — с) а ~ Ь/а ~ с.
27.	Заменить дробь со степенью в знаменателе произведением на степень с отрицательным показателем:
а/(Ь ~ с) а *Ь~ (—с).
28.	Поменять местами операнды у операций сложения и умножения. Учитывать приоритет (сначала
выполняется умножение, потом — сложение) и ассоциативность (операции сложения и умножения
левоассоциативны) операций.
29.	Выполнить замену переменной на выражение:
пример замены: а —> г + 4
а + 2 * а i + 4 + 2 * (г + 4).
30.	Упорядочить соседние операнды в операциях сложения и умножения, вынося вперед константы.
Сохранить порядок следования констант и переменных:
а + 3 + b + а * с + 2	3 + 2 + а + b + а * с.
Ч
31.	Лексикографически упорядочить соседние операнды операции сложения и умножения:
2 + b + с + а — а * b 2 + а + b + с — а * Ь.
32.	Подсчитать количество слагаемых или сомножителей на А,-том уровне дерева выражения.
33.	Даны два выражения. Подсчитать количество вхождений первого выражения во второе в качестве
подвыражения. Учесть коммутативность операций сложения и умножения.
34.	Подсчитать число уровней дерева выражения.
35.	Подсчитать количество операндов (переменных и констант) в выражении.
36.	Подсчитать количество переменных, используемых в данном выражении.
37.	Подсчитать количество целых констант, используемых в выражении.
38.	Подсчитать количество операций в данном выражении полагая, что все операции являются бинар-
ными.
39.	Построить новое выражение — копию исходного.
40.	Проверить, идентичны ли два выражения, учитывая коммутативность сложения и умножения, а так-
же возможность раскрытия скобок.
41.	Вычислить значение многочлена от х при заданном х.
42.	Проверить, является ли выражение многочленом от переменной х.
43.	По заданному многочлену от х построить выражение, являющееся производной данного многочлена.
44.	Проверить, упорядочены ли слагаемые заданного многочлена по степеням х в порядке возрастания
или убывания.
45.	Напечатать коэффициенты при степенях х в заданном многочлене в порядке возрастания и убывания
степеней. В случае отсутствия какой-либо степени печатать 0. Слагаемые в исходном многочлене
могут быть неупорядочены по степеням х.
46.	В многочлене
п
“г'г'г
г—О
выполнить замену сц па число i и па выражение сц — I.
47.	Заданы два многочлена. Построить новые многочлены, представляющие собой сумму и разность
данных.
48.	Даны два многочлена
п	п
/и=и в(.х) = '^ь1х\
г—0	г—О
Построить новый многочлен
п
г—О
где	bi), щ = тй1(щ, &Д щ и = (lifbi.
п	п
49.	Дан многочлен /(.г) =	o-i'-i'1  Построить многочлен g(.r) = an-iXl.
г—0	г—О
50.	Умножить многочлен от х на число к.
51.	Поделить многочлен от х на число к.
52.	Умножить многочлен от х на переменную х.
3
п	т
53.	Даны многочлены /(.г) = аг-г'г и з(;г) = У2 Ь}Хг. Умножить многочлен /(.г) на многочлен д(х).
г—0	г—О
п	т
54.	Даны многочлены /(.г) = У2 сцхг и д(х) = Д Ь}Хг. Разделить многочлен /(.г) на многочлен д(х)
г—0	г—О
/(.г) = 2 * х + b * х, д(х) = х 2 + b, f(x) = 3 * х, д(х) = а + х (3 * ;г)/(а + х).
55.	Разложить на множители разность квадратов
а" 2 — b ~ 2 (а — Ь) * (а + Ь).
56.	Свернуть множители в разность квадратов.
57.	Разложить на множители квадрат суммы
(а + Ь) ~ 2 а~ 2 + 2 * а * b + b ~ 2.
58.	Свернуть множители в квадрат суммы.
59.	Разложить на множители квадрат разности
(а — Ь) ~ 2 а~ 2 — 2 * а * b + b ~ 2.
60.	Свернуть множители в квадрат разности.
61.	Разложить на множители сумму кубов.
а~ 3 + b ~ 3 (а + Ь) * (а ~ 2 — а * b + b ~ 2).
62.	Свернуть множители в сумму кубов.
63.	Разложить на множители разность кубов.
а~ 3 — b ~ 3 (а — Ь) * (а ~ 2 + а * b + b ~ 2).
64.	Свернуть множители в разность кубов.
65.	Разложить на множители квадратный трехчлен.
66.	Преобразовать многочлен в стандартный вид, располагая слагаемые заданного многочлена по сте-
пеням х в порядке возрастания или убывания
п
= J2aiX\
i=0
67.	Преобразовать бинарное дерево в n-арное (заменяя соответствующие деревья операций сложения
и умножения)
68.	Преобразовать n-арное дерево в бинарное (заменяя соответствующие деревья операций сложения
и умножения)
99*. Выполнить полное дифференцирование выражения.
4