Программная инженерия Нижний Новгород 017 Лабораторный

1.5. Перевод арифметического выражения из инфиксной формы записи 
в постфиксную 
В рамках данного задания требуется разработать алгоритм и составить программу для 
перевода арифметического выражения из инфиксной формы записи в постфиксную. 
Инфиксная форма записи характеризуется наличием знаков операций между операндами. 
Например, 
(1+2)/(3+4*6.7)-5.3*4.4 
При такой форме записи порядок действий определяется расстановкой скобок и 
приоритетом операций. Постфиксная форма записи не содержит скобок, а знаки операций 
следуют после соответствующих операндов. Тогда для приведённого примера постфиксная 
форма будет иметь вид: 
1 2+ 3 4 6.7*+/ 5.3 4.4* - 
Так как при такой записи несколько операндов могут следовать подряд, то при выводе они 
разделяются пробелами. 
Как результат программа должна напечатать постфиксную форму выражения или выдать 
сообщение о невозможности построения такой формы в случае обнаружения ошибок при 
расстановке скобок.
1.6. Вычисление арифметического выражения в постфиксной форме 
Для выполнения данного задания необходимо разработать алгоритм и составить 
программу для вычисления арифметического выражения. Программа должна напечатать 
результат вычисления выражения или выдать сообщение о наличии нечисловых операндов. 
1.7. Условия и ограничения 
При выполнении лабораторной работы могут быть использованы следующие основные 
допущения: 

Можно предполагать, что арифметические выражения состоят не более чем из 255 
символов. 

В качестве допустимых арифметических операций можно рассматривать только 
символы + (сложение), - (вычитание), * (умножение), / (деление). 
2. Метод решения 
2.1. Структуры данных 
Как известно, структура данных есть модель данных в виде математической 
структуры
S = (M
1
, …, M
k
, p
1
,…,p
n
),

---

 
38 
где M
1
, …, M
k
– базисные множества, p
1
,…,p
n
– отношения между элементами базисных 
множеств. 
Динамическая структура есть математическая структура, которой соответствует 
частично-упорядоченное (по включению) базовое множество М, элементы которого являются 
структурами данных. При этом отношения включения индуцируются операциями 
преобразования структуры данных. 
Пусть p
1 
– отношение
следования, порождаемое операцией вставки, p
2
– отношение 
следования, порождаемое операцией удаления. Тогда стек есть структура
S = (M, p
1
,p
2
),
в которой

каждый элемент базисного множества есть структура, 

в любой момент существует только один конкретный элемент из M, 

элементы частично упорядочены по включению. 
Таким образом, стек есть динамическая структура, операции вставки и удаления 
переводят стек из одного состояния в другое, а состояние стека характеризуется 
совокупностью хранимых элементов и положением вершины стека. 
В качестве структуры хранения стека предлагается использовать одномерный 
(одноиндексный) массив, размещаемый в динамической области памяти. Для описания 
структуры хранения следует использовать следующие переменные: 
