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

Посмотреть архив целиком

Лабораторная работа № 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. Если ik, перейти к 2.

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


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


Задание

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


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

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

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

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

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

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

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

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

8. z = AB\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+C22+C34+...,

где 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 или “-”).


Таблица 3

0

0

0

1

1

0

0

0

0

0

0

0

1

1

0

1

0

0

0

0

0

0

0

1

0

1

1

0


Предположим, имеется входной ключ NYNY, который мы трансформируем в форме 0101. Далее выполняется поразрядная логическая операция “И” над этим ключом и первым столбцом таблицы 3. Результат дает 0101.

Сравним этот результат с первым столбцом таблицы.

3. Очевидно, что совпадение отсутствует. Этот процесс повторяется с каждым следующим столбцом таблицы 2 и выполняется сравнение с соответствующим столбцом таблицы 3. В рассматриваемом примере ключ 0101 приводит к выбору правила R3.


Таблица решающих правил и дерево решений

Рассмотрим полную решающую таблицу с ограниченным входом на три условия вида


1


2


3


4


5


6


7


8

q1

q2

q3

Y

X

Y

Y

Y

N

Y

N

Y

Y

N

N

N

Y

Y

N

Y

N

N

N

Y

N

N

N










действия

A1

A2

A2

A3

A1

A1

A1

A1


Отвечающее этой таблице дерево решений можно представить в виде, когда в узлах ставятся условия, а дуги - выходящие из них метки Y или N. Не концевые вершины задают условия (вопросы), ответом из которых являются метки исходящих из них дуг. Концевые элементы (листья) отвечают действиям, которые нужно произвести. Часто здесь ставятся адреса передачи управления на подпрограммы выполнения действий, поэтому концевые листья часто называют вектором передачи. Отсюда имеем:

Легко видеть, что если q1 и q2 имеют значение Y, то q3 не требуется запрашивать. Выход не зависит от ответа на вопрос. Аналогичная ситуация возникает, если на q1 получен ответ N. Поэтому можно сократить дерево, как показано далее.


Случайные файлы

Файл
referat.doc
79698.rtf
96266.rtf
MatAnS4.doc
3478.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.