Алгоритм Дейкстры перевода в ПОЛИЗ выражений

Будем считать, что ПОЛИЗ выражения будет формироваться в массиве, содержащем лексемы — элементы ПОЛИЗа, и при переводе в ПОЛИЗ будет использоваться вспомогательный стек, также содержащий элементы ПОЛИЗа — операции, имена функций и круглые скобки.

1. Выражение просматривается один раз слева направо.

2. Пока есть непрочитанные лексемы входного выражения, выполняем действия:

а) Читаем очередную лексему.

б) Если лексема является числом или переменной, добавляем ее в ПОЛИЗ-массив.

в) Если лексема является символом функции, помещаем ее в стек.

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

д) Если лексема является операцией θ, тогда: 1) пока приоритет θ меньше либо равен приоритету операции, находящейся на вершине стека (для лево-ассоциативных операций), или приоритет θ строго меньше приоритета операции, находящейся на вершине стека (для право- ассоциативных операций) выталкиваем верхние элементы стека в ПОЛИЗ-массив; 2) помещаем операцию θ в стек.

е) Если лексема является открывающей скобкой, помещаем ее в стек.

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

3. Когда просмотр входного выражения завершен, выталкиваем все оставшиеся в стеке символы в ПОЛИЗ-массив. (В стеке должны были оставаться только символы операций; если это не так, значит в выражении не согласованы скобки.)

Алгоритм интерпретации с помощью стека

ПОЛИЗ просматривается поэлементно слева направо. В стеке хранятся значения промежуточных вычислений и результат.

(1) если очередной элемент — операнд, то его значение заносится в стек;

(2) если очередной элемент — операция, то на "вершине" стека сейчас находятся ее операнды (это следует из определения ПОЛИЗа и предшествующих действий алгоритма); они извлекаются из стека, над ними выполняется операция, результат снова заносится в стек;

(3) когда выражение, записанное в ПОЛИЗе, прочитано, в стеке останется один элемент — это значение всего выражения.

Технология разработки программного обеспечения

Процедурное программирование. Основные принципы выполнения разработки: принцип нисходящей разработки, собственно структурное программирование, принцип сквозного структурного контроля. Процедурная декомпозиция. Метод пошаговой детализации.

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

Структурное программирование представляет собой совокупность рекомендуемых технологических приёмов, охватывающих выполнение всех этапов разработки программного обеспечения.

Основные принципы выполнения разработки:

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

· Собственно, структурное программирование, рекомендующее определенные структуры алгоритмов и стиль программирования (чем нагляднее текст программы, тем меньше вероятность ошибки);

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

В основе структурного программирования лежит декомпозиция (разбиение на части) сложных систем с целью последующей реализации в виде отдельных небольших (до40–50операторов) подпрограмм. В отличие от используемого ранее интуитивного подхода к декомпозиции, структурный подход требовал представления задачи в виде иерархии подзадач простейшей структуры, для получения которой рекомендовалось применять метод пошаговой детализации. С появлением других принципов декомпозиции (объектного, логического и т.д.) данный способ получил название процедурной декомпозиции.

Метод пошаговой детализации:

1. Определяется общая структура программы в виде одного из трёх вариантов: последовательного, условного или циклического выполнения подзадач.

2. Каждая подзадача, в свою очередь, разбивается на подзадачи с использованием тех же структур.

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