Вычисление арифметического выражения через бинарное дерево

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

Один из вариантов реализации этой операции приведен ниже.

Здесь используется функция IsNumber, которая возвращает 1, если узел является листом и содержит число, и 0 в противном случае.

Рисунок 9 – Функция, определяющая, является ли узел листом

Ниже на рисунке 10 приведем один из вариантом процедуры вычисления арифметического выражения.

Рисунок 10 – Пример вычисления арифметического выражения

 

3.3 Контрольные вопросы

 

1. Что такое синтаксическое дерево разбора?

2. Какие основные способы разбора и расчета арифметических выражений?

3. Для каких случаев используется префиксная, инфиксная и постфиксная запись?

4 Требования к выполнению домашнего задания

Задание

 

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

Примерные варианты заданий приведены в приложении А.

Указания к выполнению работы

 

Все логически завершенные фрагменты алгоритма необходимо оформить в виде подпрограмм.

При разработке интерфейса программы следует предусмотреть:

· указание типа, формата и диапазона вводимых данных;

· указание действий, выполняемых программой;

· наличие пояснений при выводе результата;

· наличие меню для выбора действий, выполняемых программой.

При тестировании программы необходимо:

· проверить правильность ввода и вывода данных (т.е. их соответствие требуемому типу и формату). Обеспечить адекватную реакцию программы на неверный ввод данных;

· обеспечить вывод сообщений при отсутствии входных данных («пустой ввод»);

· проверить правильность выполнения операций;

· предусмотреть вывод сообщения при попытке выполнения недопустимых операций;

· проверить различные варианты задания переменных в выражении (с клавиатуры и рандомно):

· предусмотреть расчет выражения с переменными разного типа;

 

 

1. Что такое синтаксическое дерево разбора?

2. Какие основные способы разбора и расчета арифметических выражений?

3. Для каких случаев используется префиксная, инфиксная и постфиксная запись?

 

Требования к отчету

 

В отчете по домашнему заданию должны быть сделаны выводы о том, какие достоинства и недостатки имеет метод разбора и расчета арифметического выражения через бинарные деревья (например, в сравнении с разбором и расчетом с помощью стека).

 

В отчете по домашнему заданию должны быть даны ответы на контрольные вопросы.

 

Отчет по домашнему заданию должен включать в себя:

1. Титульный лист;

2. Цели домашнего задания;

3. Теоретическая часть с ответами на контрольные вопросы;

4. Задание в соответствии с вариантом;

5. Графическое отображение дерева в соответствии с вариантом;

6. Код программы с комментариями;

7. Тесты программы с пояснениями;

8. Выводы.

Требования к защите

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

Заключение

 

В процессе выполнения домашнего задания по теме «Бинарные деревья» студенты получат краткие теоретические и справочные сведения по построению и обработке бинарных деревьев с помощью динамических структур данных. Рассмотрят примеры решения задачи разбора арифметических выражений с применением бинарных деревьев.

В результате выполнения домашнего задания студенты освоят приемы работы с динамическими бинарными деревьями поиска на языке программирования С++. Получат практические навыки применения бинарных деревьев для вычисления арифметических выражений.

 Список рекомендуемой литературы

1. Иванова Г. С. Основы программирования. М.: Издательство МГТУ им. Н.Э. Баумана, 2001. С. 238–253.

2. Г.В. Ваныкина, Т.О. Сундукова Структуры и алгоритмы компьютерной обработки данных /– М: Изд-во Интуит, 2011. – 211 с.

3. Михалкович С. С. Основы программирования: Динамические массивы. Списки. Ассоциативные массивы. Деревья. Хеш-таблицы. — Ростов н/Д.: УПЛ ЮФУ, 2007. — 48 с.

4. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – М.: Мир, 1989. – 392 с.

5. Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. М.: Изд-во Вильямс, 2001. – 253 с.

6. Ахо А., Хопкрофт Д.,. Ульман Д. Структуры данных и алгоритмы: Пер. с англ. М.:
Издат. дом «Вильямс», 2000. С. 77–99.

7. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и
анализ / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с

8. Керниган Б., Пайк Р. Практика программирования: Пер. с англ. СПб.: Невский диалект, 2001. С. 83–90.

 

 

Приложение А. Варианты заданий

Номер варианта соответствует порядковому номеру студента в алфавитном списке группы.

ВАРИАНТ	ЗАДАНИЕ	ВАРИАНТ	ЗАДАНИЕ
1	(1+ a)*(2-3*(7- b))	16	(3*(x-4)-8)*(6-2*y)
2	(3 *x+4) - (y * 7- (-4 +2))	17	(7/(a+3))/(4-(1+3b))
3	(6- 4*(b+2)/4) /(7-a)	18	(3/f-7)*(4-2*(8*g+5))
4	(8+9*w)/(7*(3-t)-2)	19	(1-(8-5*x))/(3-(7+3*y))
5	(6-3*(z+4)+2)*(5-k)	20	((2*a+5)/3)- 2 *(7-b)
6	(7-n)/(8+2*(9+m)+4)	21	(2-9)*((1+ p)*7)/(k+3)
7	(f+1)*(6/(1+g)+4)	22	(b* (c-7)/3)-5*((4-c)+1)
8	(k*4-2)/(1+8*(h-3))	23	3+((5-m)*3/7+(n-9)*8)
9	(6*(1+3*b))*(7+a)	24	(a-4)*8-(2+b+8/a)/2
10	(9*(a-1))/(4+3/(b+7))	25	(4-k)*(9-5*(z+2)+1)
11	(4/(3+x))*(y/2+7)	26	(8-(2*k+3))/(7/p+4)
12	(2*(m-3))*(3-2*(n+2))	27	(7-2*n*(9+m)+)/(8+4*m)
13	(x/2+7)*(7*(y-4)+3)	28	(3+8/(b+4))/(6*(a-3))
14	(5/p+2)/(4-(3*k+1))	29	(2*(7-t)-4)/ (8+9*w/2)
15	(8*a+2)*((6*b-5)/3)	30	(k -9)* (k+5)/ ((6 + p)*4)