SisProg2 (Ещё что-то по лабораторным работам)

Лабораторная работа № 5

Перевод инфиксного арифметического выражения

в постфиксную форму

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

Таблица приоритетов для операторов (разделителей) представлена в форме:

Оператор	Приоритет
( ; ) = + - * / * *	0 1 2 3 4 5

На входе имеем входную строку, которая содержит символы идентификаторов переменных и знаков операторов. Символы идентификаторов непосредственно переносятся в выходную строку. Символы операторов попадают в стек, вытесняя из него в выходную строку те операторы, приоритет которых больше или равен приоритету операторов в вершине стека. Исключение составляет открывающая скобка, которая заносится в стек, не вытесняя из него другие ранее попавшие в стек операторы. Закрывающая скобки вытесняет из стека все операторы вплоть до соответствующей открывающей и ликвидируется вместе с ней. Знаки из стека попадают в выходную строку. Знак конца выражения очищает стек и может не вставляться в выходную строку.

Обозначим приоритет символа s через p(s), например, p(+)=3. Запишем выражение в виде . Унарные минус и плюс не используются. Алгоритм перевода можно представить в виде последовательности шагов:

1. Положить i=1.

2. Положить S^/ =s_i. Если S есть (, то перейти к 9.

3. Если S - идентификатор переменной, переслать его в выходную строку и перейти к 10.

4. Если стек пуст, перейти к 9.

5. Взять из вершины стека символ n.

6. Если переслать n в выходную строку и перейти к 5.

7. Если S есть ) или n есть (, то перейти к 10.

8. Занести n в стек.

9. Занести S в стек.

10. Положить i=i+1. Если ik, перейти к 2.

11. Переслать оставшееся содержимое стека в выходную строку. Конец.

Примечание: В алгоритме пропущена обработка символа “;”.

Задание

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

Варианты заданий

1. y = M+KN/(M+K)-(N-1)

2. p= (X+Y) (XZ-Y)-Z/X

3. a =(M+N)/(K-M)+MN

4. x = A (B+C)-B/(C+A)

5. k = (X-Y) Z+X/(Y-Z)

6. x = (A+B)/(C-D)+AC

7. n = K+X/M-(X-K) M

8. z = AB\C+C(2-B+A)

Лабораторная работа № 6

Разбор постфиксной записи

Предположим есть инфиксное выражение ограниченной сложности, например,

A = B  C + D  (E - F).

Постфиксная форма этого выражения имеет вид:

ABC  DEF -  + =.

Предположим, что идентификаторы однобуквенные, операнды имеют ограниченный набор: +, -, , /, . Разбор такого выражения представляет построение таблицы, в строках которой располагаются элементарные подвыражения вида:

n₁  n₂ , где

n₁ и n₂ - имена переменных, а знак  означает некоторый оператор. Результат разбора, описанный в i-ой строке, помещается в рабочую переменную T.i. Так для рассмотренного примера имеем:

Таблица разбора

№ строки	Операнд	Оператор	Операнд
1 2 3 4 5	B E D T.1 A	* - * + =	C F T.2 T.3 T.4

Пусть выражение, которое требуется разложить в форму таблицы разбора, записано в виде: . Алгоритм разбора можно представить последовательностью шагов:

1. Положить i=1; J=1.

2. Положить S=s_i. Если S - оператор, перейти к 4.

3. Протолкнуть S в стек; положить i=i+1; перейти к 2.

4. Вытолкнуть n₂ ; вытолкнуть n₁ ; поместить n₁ S n₂ в J строку таблицы.

5. Если стек пуст, то конец.

6. Положить S = T.J; положить J=J+1; перейти к 3.

Задание

Спроектировать программу разбора постфиксного выражения, сформированного в предыдущей работе, ограниченной сложности при заданном k и заданной глубине стека L. Предусмотреть проверку длины стека на переполнение.

Варианты заданий

№ варианта	Максимальное значение k	Максимальное значение L
	16	7
	12	8
	14	6
	15	7
	16	8
	14	6
	15	7
	17	6

Лабораторная работа № 7

Деревья решений и решающие таблицы

Блок-схемы (структурные схемы) - классическое средство представления логики программ. В ряде случаев такие схемы чрезвычайно сложны из-за большого числа условных операторов. Поэтому, в ряде случаев при решении задач обработки данных и в описании логики работы устройств ЭВМ и выделении ресурсов для конкурирующих процессов целесообразно использовать решающие таблицы. Примеры таких таблиц приведены далее.

Предположим, требуется составить какой-то набор правил для выплаты премии сотрудникам не с потолка, а как-то аргументированный. Из каких-то соображений можно составить меню вида правил:

ЕСЛИ СТАЖ > 10 лет и пол = м возраст > 50

дать 90;

ЕСЛИ СТАЖ > 10 лет и пол = м и возраст  50

дать 70;

ЕСЛИ СТАЖ > 10 лет и пол = ж возраст > 50

дать 80;

ЕСЛИ СТАЖ > 10 лет и пол = ж и возраст  50

дать 60;

ЕСЛИ СТАЖ < 10 лет и пол = ж возраст  50

дать 0;

и т.д.

Эти правила можно представить в виде решающей таблицы:

Решающая таблица

	1	2	3	4	5	6	7	8
Стаж > 10 пол = м возраст > 50	N N N	N N Y	N Y N	N Y Y	Y N N	Y N Y	Y Y Y	Y Y Y
действия	0	0	0	0	60	80	70	90

Здесь Y отвечает “истине” (Да), N - “ложь” (Нет). Y и N можно заменить на 1 и 0, соответственно. Столбец условий правила называется индикатором правила (например, индикатор правила 1 это NNN или 000).

Предположим, требуется определить сумму премии для служащего с условиями: женщина, возраста 55 лет, стаж 23 года. По этим условиям составим “ключ”, который имеет вид YNY. Сопоставляя его последовательно с индикаторами правил, получим, что он сопоставим с индикатором правила 6, следовательно, действие - 80 в премию.

Можно вместо сопоставления с индикаторами воспользоваться методом Вейкота. Здесь выполняется

JUMP = 1+C1+C22+C34+...,

где Cn=1, если n-е условие ключа 1 и 0 в противном случае. Эта величина определяет номер искомого правила, а следовательно, необходимого действия.

Приведенная таблица называется решающей таблицей с “ограниченным” входом. В ней условия представляют логические переменные. В таблицах с “расширенным” входом в каждой клетке условия может содержаться несколько различных ответов. Обычно составляется список возможных значений для каждого условия и в клетки подставляются только номера значений. Поэтому далее ограничения лишь таблицами с ограниченным входом.

Полнота решающей таблицы и ее сокращение

Достоинством таблицы решений является возможность систематической проверки каждой комбинации значений условий. Если правило имеет индикатор из n условий, то общее число правил в таблице 2ⁿ. Это позволяет теоретически заранее проверить общее число возможных исходов и выяснить, полна ли таблица. Ручная проверка затруднительна, т.к. 2ⁿ возрастает как экспонента.

Для сокращения таблицы используется два способа. Первый способ -использование тире, которое обозначает, что значение данного условия несущественно для данного правила. Например, ниже слева изображены два столбца таблицы решений с ограниченным входом:

C1 C2 C3 C4		YY NN NY YY		C1 C2 C3 C4		Y N - N
A1 A2 A3 A4		XX XX		A1 A2 A3 A4		X X

В приведенном случае видно, что условие 3 не играет роли, т.к. в обоих случаях выполняются действия 2 и 4. Используя правило тире, эти два столбца можно слить в один, как это показано справа. Очевидно, что если в одном правиле решений записано n тире, то оно заменило 2ⁿ правил решений.

Второй способ - использование правила “ИНАЧЕ”.

Например, в рассмотренном в начале примере можно оставить в таблице правила 5,6,7,8, а все остальные занести в рубрику правила “ИНАЧЕ”.

	5	6	7	8	“ИНАЧЕ”
Стаж > 10 пол = м возраст > 50	Y N N	Y N Y	Y Y N	Y Y Y
действия	60	80	70	90	0

В этих случаях сокращается число проверок значения входного ключа с индикаторами правил. Если совпадения входного ключа с приведенными в таблице правилами отсутствуют, то выбираются действия из правила “ИНАЧЕ”.

Поиск в сокращенных решающих таблицах

Поиск по “методу маски” Кирка. Рассмотрим следующий пример. Пусть дана таблица с индикаторами вида:

Таблица 1

R1	R2	R3	R4	R5	R6	R7	“ИНАЧЕ”
N	N	N	Y	Y	-	-
N	-	-	-	-	Y	Y
N	Y	N	-	-	N	-
N	N	Y	N	Y	Y	N

где R_i - индикаторы правил. В соответствии с этой таблицей строятся две вспомогательные. В первой из них (Таблица 2) на место позиции, где в первой таблице “-”, ставится 0. В остальных позициях помещаются 1.

Таблица 2

1	1	1	1	1	1	0
1	0	0	0	0	1	1
1	1	1	0	0	1	0
1	1	1	1	1	1	1

В другой (Таблица 3) 1 размещается в каждой позиции, в которой в первой таблице, где размещался Y и 0 - в противном случае (стояло N или “-”).