арифметическое выражение

1. Трансляция арифметического выражения. Динамические структуры данных (стек). МАТЕРИАЛЫ К ЛАБ.РАБОТЕ

2020
Барышева ИВ
1

2. Арифметическое выражение Постфиксная форма представления Польская инверсная запись ПолИЗ

Пример
a * b/(x^2+y^2) - c*k^(a-b*d/(x+y)) -35*a^z^(a-b)+17
Вопросы:
1. Как рассматривать выражение представленное строкой
2. Как определить однозначный порядок выполнения операций
3. Как представить выражение в виде последовательности
элементарных операций
4. Как определяется допустимый набор операций
2

3. Польская инверсная запись ПолИЗ

Пример
a * b/(x^2+y^2) - c*k^(a-b*d/(x+y)) -35*a^z^(a-b)+17
Полиз:
a b * x 2 ^ y 2 ^ + / c k a b d * x y + / - ^ * - 35 a z ^ a b - ^ * - 17 +
*
С
Т
Е
К
/
(
^
/
(
+
^
*
^
(
Правила:
1. Операнд в полиз и таблицу
переменных
2. «(» в стек
3. «)» «выставляет» из стека в полиз
все операции до соответствующей
«(»
/
-
-
*
3

4. Польская инверсная запись ПолИЗ

Пример
a * b/(x^2+y^2) - c*k^(a-b*d/(x+y)) -35*a^z^(a-b)+17
Полиз:
a b * x 2 ^ y 2 ^ + / c k a b d * x y + / - ^ * - 35 a z ^ a b - ^ * - 17 +
-
С
Т
Е
К
*
^
-
*
^
-
*
^
-
*
^
+
(
(
-
-
/
(
+
-
*
^
(
-
*
старый
Правила:
4. Операция «выставляет» в полиз из
стека все более «важные» или
равнозначные операции
5. пункт 4 для равнозначных операций
обеспечивает выполнение слева
направо последовательности
операций одинаковой «важности» 4

5.

Приоритеты операций и реализация пункта 4
первого этапа
. Операция «выставляет» в полиз из стека все более
«важные» или равнозначные операции
4
Name
Value
Приоритет верхушки стека
Name
Value
Приоритет верхушки стека
+
1
3
-
1
>=
+
-
3
<=
*
2
*
2
/
2
/
2
^
3
^
1
приоритета очередного
операнда
арифметического
выражения
приоритета очередного
операнда
арифметического
выражения
Операция из стека заносится в полиз
5

6. Польская инверсная запись ПолИЗ

Полиз:
a b * x 2 ^ y 2 ^ + / c k a b d * x y + / - ^ * - 35 a z ^ a b - ^ * - 17 +
Name
Value
a
b
a * b/(x^2+y^2) - c*k^(a-b*d/(x+y)) -35*a^z^(a-b)+17
x
2
2
y
k
d
35
35
z
17
Для определения значения выражения
необходимо заполнить поле «Value» для
переменных
17
6

7. Арифметическое выражение. Счет

Полиз:
a b * x 2 ^ y 2 ^ + / c k a b d * x y + / - ^ * - 35 a z ^ a b - ^ * - 17 +
Правила:
1. Операнд ищется в таблице переменных, найденное значение заносится в
стек
2. Для выполнения операции:
1. Из стека считывают значение правого операнда R
2. Из стека считывают значение левого операнда L
3. Выполняется операция Ri=L Θ R
4. Ri заносится в стек
С
Т
Е
К
a
b
R1
x
2
R=b
L=a
R1=L Θ R
7

8. Арифметическое выражение. Счет

Полиз:
a b * x 2 ^ y 2 ^ + / c k a b d * x y + / - ^ * - 35 a z ^ a b - ^ * - 17 +
С
Т
Е
К
R1
x
2
R1
R2
y
R1
R2
R3
R1
R4
R5
c
k
a
b
R5
c
k
a
R6
2
R2 = x^2
R3 = y^2
R4 = R2 + R3
R5 = R1 / R4
R6 = b * d
d
8

9. Арифметическое выражение. Счет

Полиз:
a b * x 2 ^ y 2 ^ + / c k a b d * x y + / - ^ * - 35 a z ^ a b - ^ * - 17 +
С
Т
Е
К
R5
c
R5
c
R5
k
a
R6
x
k
a
R6
R7
c
k
a
R8
R5
c
k
R9
R5
c
R10
R5
R11
y
перенос
R5
c
k
a
R6
R7 = x + y
R8 = R6 / R7
R9 = a - R8
R10 = k ^ R9
R11 = c * R10
9

10. Арифметическое выражение. Счет

Полиз:
a b * x 2 ^ y 2 ^ + / c k a b d * x y + / - ^ * - 35 a z ^ a b - ^ * - 17 +
С
Т
Е
К
R12 35
a
R12
R13
35
R12
35
R13
R12
35
R15
R12
R16
R17
17
R18
z
перенос
a
R14
b
R5
R11
R12 = R5 – R11
R13 = a ^ z
R14 = a – b
R15 = R13 ^ R14
R16 = 35 * R15
R17 = R12 – R16
R18 = R17 -17
10

11.

Порядок действий при обработке
Этап
арифметического выражения
компиляции
Таблица операндов
Имя операнда
Исходное
арифметическое
выражение
Массив
лексем
Значение
операнда
Обратная польская запись
+-* /^()
Стек записей вида
«операция приоритет»
Значение
арифметического
выражения
Стек значений
операндов
Таблица приоритетов операций
Имя операции
Приоритет
операции
Этап исполнения
11

12.

Цели проекта:
1.Познакомиться с динамическими структурами данных (стек).
2.Познакомится с одним из методов обработки арифметических
выражений на компьютере.
3. Разработать приложение, которое бы предоставляло
пользователю возможности:
12

13.

Цели проекта:
Разработать приложение, которое бы предоставляло
пользователю возможности:
a.Ввести арифметическое выражение с использованием как
изменяемых (переменные), так и постоянных (константы)
операндов и различных операций.
b. Просматривать обратную польскую запись для этого
выражения.
c. Изменять значение переменных операндов.
d. Вычислять значение арифметического выражения на основе
значений операндов.
13

14.

Задание на лабораторную работу
14

15.

Структура проекта
class TRecord
запись вида «Имя –
значение»
class Poliz
обратная польская запись
Таблица
операндов
Таблица
приоритетов
Массив элементов обратной
польской записи
class TTable
множество
записей
class TStack
стек
class ArithmeticExpression
арифметическое выражение
Содержит методы для
работы с элементами
обратной польской записи
(подсчет значения
выражения)
Главный файл проекта с
формой (Windows Forms)
15

16. Динамическая структура стек

Динамическая структура
S=(Mi, p1,p2),
в которой отношение следования p1, (следующий) реализовано операцией «вставки», а
отношение следования p2 (предыдущий) – операцией «исключения», организованными по
правилу LIFO («последним зашел – первым вышел») называется стек.
исключение
исключение
исключение
511
вставка
345
M0 пустой стек
M1
вставка
206
вставка
206
345
345
M2
M3
16

17. Динамическая структура стек на массиве

Посмотреть и изъять
элемент можно
только последний
■■■■■■
Добавлять элементы
можно только после
последнего
Понятие стек определяет
способ доступа к информации
при любой структуре хранения
17

18. Динамическая структура таблица

Динамическая структура
S=(Mi, p1,p2,p3),
в которой помимо операции «вставки» p1 (следующий) и операции «исключения» p2
(предыдущий) реализовано отношение «иметь имя» с помощью операции поиска
называется таблица.
Существует четыре способа организации таблицы, отличающиеся структурой хранения, алгоритмом
поиска, местом куда, можно «включить» новые записи:
1. Неупорядоченная
(просматриваемая)
2. Сортированная
3. Хеш – таблица
4. Деревья поиска

19.

Неупорядоченные (просматриваемые) таблицы
Структура хранения - массив
count
size
mem
1. Поиск линейный
Сложность по времени
T~(N/2)
2. Вставка – поиск и
mem[count++] = {Key, info}
3. Удаление – поиск и
mem[l]=mem[--count]
19

20.

Упорядоченные таблицы
Структура хранения – упорядоченный массив
count
size
mem
1. Поиск бинарный
Сложность по времени
T~log2(N/2)
2. Вставка – поиск, сдвиг и
mem[l]= {Key, info}
count++
3. Удаление – поиск, сдвиг и
mem[i+1]=mem[i]
--count
20

21.

Хеш - таблицы
1. Структура хранения - массив
L= F(Key)
mem[L]={Key,info}
коллизия
size
L= F(Key2)
mem[L]={Key2,info}
mem
21

22.

Хеш - таблицы
1. Структура хранения – массив, разрешение коллизии –
открытое перемешивание
L= F(Key)
mem[L]={Key,info}
Dl – взаимно просто size
size
L= F(Key2)
mem[L]={Key2,info}
mem
22

23.

Хеш - таблицы
2. Структура хранения – массив указателей, разрешение
коллизии – цепочки
Сложность по времени
Null
Null
size
Null
Null
Null
вставки, удаления и поиска
при хорошо подобранной
хеш-функции может быть 1,
T~ (N/2)
Возрастает сложность по
памяти
Null
mem
23

24.

AVL деревья - таблицы
1. Структура хранения – бинарное дерево
Start
Left
Key
Info
Right
1. Поиск бинарный
Сложность по времени
T~log2(N/2)
2. Вставка ~поиск + перепаковка
3. Удаление ~ поиск +
перепаковка
24

25.

Критерии выбора способа организации
таблицы
1.Размеры
2.Частота исполнения операций вставки и удаления
Наш выбор –просматриваемая таблица
25

26.

Класс «Польская инверсная запись»
Поля класса:
1.Строковый массив для Полиз
2.Его длина
3.Число элементов в Полиз
4.Стек записей вида «операция-приоритет»
5.Таблица приоритетов
6.Таблица переменных
26

27.

Класс «Польская инверсная запись»
Поля для упрощения передачи
информации между методами
класса:
1.Массив лексем
2.Его длина
3.Число лексем
27

28.

Класс «Польская инверсная запись»
Закрытые методы класса:
1. Преобразование строки, содержащей
арифметическое выражение в массив лексем
2. Формирование таблицы операций
3. Методы «разгружающие» алгоритм
получения Полиз
4. Алгоритм получения Полиз
28

29.

Класс «Польская инверсная запись»
Закрытые методы класса:
Методы «разгружающие» алгоритм получения Полиз
1. Обработка конца строки
2. Обработка операнда
3. Обработка левой скобки
4. Обработка правой скобки
5. Обработка операции
29

30.

Класс «Польская инверсная запись»
Открытые методы класса:
1. Обязательные
1. Конструктор
2. Деструктор
3. Конструктор копирования
4. Перегрузка операции «=»
2. Необходимые
1. Возврат элемента массива Полиз по номеру и
реальной длины массива
2. Возврат строки Полиз
3. Возврат указателя на таблицу операндов и ее
реальной длины
30

31.

Класс «Арифметическое выражение»
Поля класса:
Объект класса «Польская инверсная запись»
Открытые методы класса:
1. Обязательные
1. Конструктор
2. Деструктор
3. Конструктор копирования
4. Перегрузка операции «=»
31

32.

Класс «Арифметическое выражение»
Открытые методы класса:
Необходимые
1. Возврат строки Полиз
2. Возврат указателя на таблицу операндов и
ее реальной длины
3. Вычисление арифметического выражения
32

33.

Порядок сдачи лабораторной работы:
1.Контрольная работа – допуск
2.Тестер класса «стек»
3.Тестер класса «таблица»
4.Тестер класса «полиз»
5.Тестер класса «ар. выр-е»
6.Работа на форме
7.Отчет
33