SisProg2 (565140)

Файл №565140 SisProg2 (Ещё что-то по лабораторным работам)SisProg2 (565140)2016-04-08СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

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

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

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

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

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

Оператор

Приоритет

( ;

)

=

+ -

* /

* *

0

1

2

3

4

5

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

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

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

2. Положить S/ =si. Если 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 -  + =.

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

n1  n2 , где

n1 и n2 - имена переменных, а знак  означает некоторый оператор. Результат разбора, описанный в 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=si. Если S - оператор, перейти к 4.

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

4. Вытолкнуть n2 ; вытолкнуть n1 ; поместить n1 S n2 в 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 условий, то общее число правил в таблице 2n. Это позволяет теоретически заранее проверить общее число возможных исходов и выяснить, полна ли таблица. Ручная проверка затруднительна, т.к. 2n возрастает как экспонента.

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

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 тире, то оно заменило 2n правил решений.

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

Например, в рассмотренном в начале примере можно оставить в таблице правила 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

где Ri - индикаторы правил. В соответствии с этой таблицей строятся две вспомогательные. В первой из них (Таблица 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 или “-”).

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

Тип файла
Документ
Размер
159 Kb
Тип материала
Предмет
Высшее учебное заведение

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

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

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

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

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

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6392
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее