ЛАБОРАТОРНАЯ РАБОТА 5

ПРЕОБРАЗОВАНИЕ И ВЫЧИСЛЕНИЕ АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ С ПОМОЩЬЮ СТЕКА

Введение

Инфиксная запись (нотация) – обычная форма записи математических выражений, в которой знаки операций расположены между операндами. Вычисления производят в соответствии с приоритетом операций.

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

Например, инфиксная запись: 7-2*3, ПОЛИЗ: 7 2 3 * - .

Алгоритм вычисления:

· выражение читается слева направо;

· когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке из записи;

· результат операции заменяет в выражении последовательность её операндов и её знак, после чего выражение вычисляется дальше по тому же правилу;

· результатом вычисления выражения становится результат последней вычисленной операции (в примере равен 1).

Префикснаязапись (польская запись) – это форма записи логических, арифметических и алгебраических выражений. Здесь оператор располагается слева от операндов.

Например, инфиксная запись: (5-6)*7, префиксная запись: * - 5 6 7.

Стек – (англ. Stack – стопка) – структура данных с методом доступа к элементам структуры LIFO (англ. Last In – First Out, «последним пришел – первым вышел»).

Добавление элемента, называемое проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху).

Удаление элемента, называемое также выталкиванием (pop), возможно также только из вершины стека, при этом второй сверху элемент становится верхним.

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

Кроме того, в данной работе будет продолжено изучение новых компонентов среды Builder. Здесь будут использованы следующие интерфейсные компоненты: ImageList – список изображений, ActionList - диспетчер действий, ToolBar – инструментальная панель.

Алгоритмы

Преобразование инфиксной записи в постфиксную запись

Инфиксная запись (тип – строка) является исходной; при преобразовании каждый символ рассматривается поочередно.

1.Если символ или последовательность символов – число или переменная (операнд), то он помещается в выходную строку – постфиксную запись.

2.Если очередной символ – знак операции (+, -, *, /), или открывающая скобка, то приоритет данной операции сравнивают с приоритетом операции на вершине стека. Операции умножения и деления имеют приоритет, равный 2, операции сложения и вычитания имеют приоритет, равный 1, а открывающая скобка - равный 3. После получения символа проверяется стек.

а.Если стек пуст, или находящийся на его вершине символ имеет меньший приоритет, чем приоритет текущего символа, то текущий символ помещается в стек.

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

3.Если текуший символ – открывающая скобка, то её помещают в стек.

4.Если текуший символ – закрывающая скобка, то символы из стека извлекают в выходную строку до тех пор, пока в стеке не появится открывающая скобка, которую отбрасывают. Закрывающая скобка также отбрасывается.

5.Если все символы входной строки просмотрены, а в стеке еще остаются знаки операций, то их из стека переносят в выходную строку.

Преобразование инфиксной записи в префиксную запись

1.Реверсируют исходную строку справа налево, сохраняя порядок скобок.

2.Преобразуют полученную строку в постфиксную запись.

3.Снова реверсируют строку справа налево и получают префиксную запись.

Вычисление выражений

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

1.Если очередные символы входной строки – число, то его помещают в стек.

2.Если очередной символ входной строки – знак операции, то из стека извлекают два верхних числа, используют их в качестве операндов для этой операции, а результат помещают в стек.

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