SisProg2 (565140)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лабораторная работа № 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. Положить 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. Предусмотреть проверку длины стека на переполнение.

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

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

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

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

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

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

дать 90;

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

дать 70;

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

дать 80;

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

дать 60;

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

дать 0;

и т.д.

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

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

Здесь 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ⁿ возрастает как экспонента.

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

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

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

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

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

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

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

Таблица 1

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

Таблица 2

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов лабораторной работы