- •1.1.2 Классификация структур данных
- •1.1.3 Обозначения и договоренности
- •1.1.4 Множества.
- •1.1.5 Прямоугольные структуры. Массивы
- •Лекция 2
- •2.1 Прямоугольные структуры. Таблицы
- •2.2 Реализация с использованием параллельных массивов (статическое представление таблицы)
- •2.3 Реализация операций для неупорядоченной таблицы с использованием статической памяти
- •2.4 Динамическая память. Куча
- •2.5 Операции над указателями
- •2.6 Геометрическая интерпретация
- •2.7 Динамическая цепочка
- •2.8 Реализация операций для неупорядоченной таблицы с использованием динамической памяти
- •3.2 Обратная польская (постфиксная) запись
- •Лекция 4
- •4.1 Списковые структуры. Линейный список
- •Атом есть линейный список (атомарный);
- •Атом есть линейный список (атомарный);
- •4.2 Об операции "расчленение"
- •4.3 Логическое описание линейного списка.
- •4.4 Вычисление значения арифметического выражения
- •Лекция 5
- •5.1 Деревья
- •5.2 Бинарные деревья
- •5.5 Дерево двоичного поиска
- •7.2 Инструментальные средства. Архивация файлов (пока без сжатия)
- •7.3 Программы хранения и обработки информации
- •7.4 Код Цезаря
- •7.5 Упаковка текста
- •7.6 Код Хаффмана
- •7.7 Код Хемминга
- •7.8 Вектор Айлиффа
- •Вектор Айлиффа
- •Лекция 8
- •8.1 Сортировка – перестановка элементов линейной структуры
- •8.2 Алгоритмы сортировки Три класса алгоритмов сортировки (включением, выбором, обменом)
- •8.2.1 Сортировка простым включением.
- •9.2 Источники погрешностей
- •9.3 Классификация погрешностей
- •9.4 Терминология
- •FoRmula traNslation (станд.66, станд.77(*))
- •10.0 Бланк для записи текста программы на Фортране
- •10.1 Элементы языка
- •10.2 Типы данных и операции
- •10.3 Описание переменных и констант
- •10.4 Арифметические операции
- •11.3 Операторы присваивания
- •11.4 Оператор continue
- •11.5 Оператор безусловной передачи управления
- •11.6 Вычисляемый оператор передачи управления
- •11.7 Оператор передачи управления по предписанию
- •11.8 Арифметический оператор условной передачи управления
- •11.9 Логический оператор условной передачи управления
- •11.10 Структурный оператор условной передачи управления*
- •11.11 Оператор цикла с параметром
- •Лекция 12
- •12.1 Реализация стандартных структур
- •12.2 Операции ввода/вывода
- •12.3 Операторы ввода/вывода
- •12.4 Оператор формата (format)
- •12.5 Логическая запись
- •12.6 Взаимодействие операторов в/в и оператора format.
- •Расширенная форма оператора read
- •12.7 Управляющие символы при печати
- •12.8 Представление целого и действительного в памяти.
- •12.9 Оператор data
- •12.10 Сравнение текстовых данных
- •12.11 Функции для данных типа character
- •Лекция 13
- •13.1 Программные единицы
- •13.2 Библиотечные и встроенные функции
- •13.3 Оператор-функция
- •Правило соответствия: Списки формальных и фактических параметров согласованы по количеству, типу и порядку следования. Пример
- •13.4 Подпрограмма-функция
- •13.5 Подпрограмма-процедура
- •О соответствии фактических и формальных параметров
- •13.6 Операторы external и intrinsic
- •Пример (параметр-переменная и параметр-значение)
- •14.3 Операторы ввода и вывода.
- •14.4 Параметры операторов ввода и вывода
- •Открытие (присоединение) файла.
- •14.5 Операторы open и close
- •14.6 Оператор read
- •14.7 Оператор write
- •14.8 Другие операторы
3.2 Обратная польская (постфиксная) запись
Привычное определение арифметического выражения:
Арифметическая константа или инициализированная арифметическая переменная является арифметическим выражением.
Если А и В – арифметические выражения, то А#В и (А#В) – арифметические выражения.
Привычная форма записи арифметического выражения
((a+b*(c-e)/(d+f))/(a*b))/c
Арифметическое выражение в форме обратной польской записи (ПФ):
Арифметическая константа или инициализированная арифметическая переменная является арифметическим выражением ПФ.
Если А и В – арифметические выражения ПФ, то АВ # – арифметическое выражение ПФ.
Постфиксная форма записи того же арифметического выражения
a b c e - * d f + / + a b * / c /
Как получить обратную польскую запись?
Рекурсивное решение: Если арифметическое выражение является арифметической константой или инициализированной арифметической переменной, то по определению это и есть арифметическое выражение ПФ. Если арифметическое выражение имеет вид А#В или (А#В), то нужно записать ПФ для А, далее приписать ПФ для В, а затем записать знак операции #.
((a+b*(c-e)/(d+f))/(a*b))/c
(((a+((b*(c-e))/(d+f)))/(a*b))/c)
(((a+((b*(c-e))/(d+f)))/(a*b))/c)
((a+((b*(c-e))/(d+f)))/(a*b))c/
((a+((b*(c-e))/(d+f)))/(a*b))c/
((a+((b*(c-e))/(d+f)))/(a*b))c/
(a+((b*(c-e))/(d+f)))(a*b)/c/
(a+((b*(c-e))/(d+f)))(a*b)/c/
(a+((b*(c-e))/(d+f)))(a*b)/c/
a((b*(c-e))/(d+f))+ab*/c/
a((b*(c-e))/(d+f))+ab*/c/
a((b*(c-e))/(d+f))+ab*/c/
a(b*(c-e))(d+f)/+ab*/c/
a(b*(c-e))(d+f)/+ab*/c/
a(b*(c-e))(d+f)/+ab*/c/
ab(c-e)*df+/+ab*/c/
ab(c-e)*df+/+ab*/c/
ab(c-e)*df+/+ab*/c/
abce-*df+/+ab*/c/
abce-*df+/+ab*/c/
Задача.
Вычислить значение арифметического выражения, записанного в виде обратной польской записи.
Решение.
Создаем пустой стек. Читаем арифметическое выражение ПФ слева направо. Если встречается константа или имя инициализированной переменной, то в стек вталкивается соответствующее значение. Если встречается знак арифметической операции, то из стека выбираются два значения, над ними выполняется операция (первое значение – правый операнд, второе значение – левый операнд), результат операции вталкивается в стек.
Докажите, что в результате такой обработки правильного выражения ПФ в вершине стека будет лежать значение арифметического выражения, других записей в стеке не будет.
Пусть a=1, b=2, c=3, d=4, e=5, f=6, тогда алгоритм вычисления выражения
a b c e - * d f + / + a b * / c / реализуется так:
Номер действия |
Содержание стека |
Обратная польская запись |
|
|
1,2,3,5,-,*,4,6,+,/,+,1,2,*,/,3,/ |
|
1 |
2,3,5,-,*,4,6,+,/,+,1,2,*,/,3,/ |
|
1,2 |
3,5,-,*,4,6,+,/,+,1,2,*,/,3,/ |
|
1,2,3 |
5,-,*,4,6,+,/,+,1,2,*,/,3,/ |
1 |
1,2,3,5 |
-,*,4,6,+,/,+,1,2,*,/,3,/ |
2 |
1,2,-2 |
*,4,6,+,/,+,1,2,*,/,3,/ |
|
1,-4 |
4,6,+,/,+,1,2,*,/,3,/ |
|
1,-4,4 |
6,+,/,+,1,2,*,/,3,/ |
3 |
1,-4,4,6 |
+,/,+,1,2,*,/,3,/ |
4 |
1,-4,10 |
/,+,1,2,*,/,3,/ |
5 |
1,-0.4 |
+,1,2,*,/,3,/ |
|
0.6 |
1,2,*,/,3,/ |
|
0.6,1 |
2,*,/,3,/ |
6 |
0.6,1,2 |
*,/,3,/ |
7 |
0.6,2 |
/,3,/ |
|
0.3 |
3,/ |
8 |
0.3,3 |
/ |
|
0.1 |
|