Арифметическое выражение - выражение, в котором операндами являются объекты, над которыми выполняются арифметические операции. Например,
(1 + 2) / (3 + 4 * 6.7) - 5.3 * 4.4
При такой форме записи (называемой инфиксной, где знаки операций стоят между операндами) порядок действий определяется расстановкой скобок и приоритетом операций. Постфиксная (или обратная польская) форма записи не содержит скобок, а знаки операций следуют после соответствующих операндов. Тогда для приведённого примера постфиксная форма будет иметь вид:
1 2 + 3 4 6.7 * + / 5.3 4.4 * -
Обратная польская нотация была разработана австралийским ученым Чарльзом Хэмблином в середине 50-х годов прошлого столетия на основе польской нотации, которая была предложена в 1920 году польским математиком Яном Лукасевичем. Эта нотация лежит в основе организации вычислений для арифметических выражений. Известный ученый Эдсгер Дейкстра предложил алгоритм для перевода выражений из инфиксной в постфиксную форму. Данный алгоритм основан на использовании стека.
Данный алгоритм основан на использовании стека. На вход алгоритма поступает строка символов, на выходе должна быть получена строка с постфиксной формой. Каждой операции и скобкам приписывается приоритет:
( - 0
) - 1
+- - 2
*/ - 3
Предполагается, что входная строка содержит синтаксически правильное выражение.
Входная строка просматривается посимвольно слева направо до достижения конца строки. Операндами будем считать любую последовательность символов входной строки, не совпадающую со знаками определённых в таблице операций. Операнды по мере их появления переписываются в выходную строку. При появлении во входной строке операции, происходит вычисление приоритета данной операции. Знак данной операции помещается в стек, если:
- Приоритет операции равен 0 (это '(' ),
- Приоритет операции строго больше приоритета операции, лежащей на вершине стека,
- Стек пуст.
В противном случае из стека извлекаются все знаки операций с приоритетом больше или равным приоритету текущей операции. Они переписываются в выходную строку, после чего знак текущей операции помещается в стек. Имеется особенность в обработке закрывающей скобки. Появление закрывающей скобки во входной строке приводит к выталкиванию и записи в выходную строку всех знаков операций до появления открывающей скобки. Открывающая скобка из стека выталкивается, но в выходную строку не записывается. Таким образом, ни открывающая, ни закрывающая скобки в выходную строку не попадают. После просмотра всей входной строки происходит последовательное извлечение всех элементов стека с одновременной записью знаков операций, извлекаемых из стека, в выходную строку.
Разработать функцию infix2prefix, преобразующую запись арифметического выражения в инфиксной форме в запись того же выражения, но в постфиксной форме
Примечание
Функцию можно использовать следующим образом:
#include "postfix.h"
int main()
{
std::string s1("2 + 6 * 3 / (4 - 2)");
std::string s2=infix2prefix(s1);
std::cout << s2; // 2 6 3 * 4 2 - / +
}
Примечание
Предполагается, что в записи арифметического выражения используются только цифры, знаки операций, скобки и десятичная точка. Числа записаны только положительные, они могут быть как целые, так и вещественные. Скобки расставлены корректно. Глубина вложения скобок - не более 100. Количество операций в выражении - не более 200.
Написать демонстрационную программу с использованием преобразования
- include/MyStack.h - заголовочный файл для шаблона класса MyStack.
- include/postfix.h - заголовочный файл для создаваемой функции.
- src/postfix.cpp - файл с реализацией функции.
- main.cpp - домонстрационная программы для работы с функцией.
- Бакурский Андрей Сергеевич 19 ПИ-1 b1
- Балаян Роман Каренович 19 ПИ-1 b2
- Бекина Светлана Сергеевна 19 ПИ-2 b3
- Боряев Сергей Сергеевич 19 ПИ-1 b4
- Бурцев Роман Андреевич 19 ПИ-1 b5
- Варгин Дмитрий Александрович 19 ПИ-1 b6
- Вотинова Ксения Константиновна 19 ПИ-1 b7
- Герасимов Алексей Александрович 19 ПИ-1 b8
- Грачев Александр Евгеньевич 19 ПИ-1 b9
- Долгополов Алексей Геннадьевич 19 ПИ-1 b10
- Думаревская Татьяна Николаевна 19 ПИ-2 b11
- Емшанов Павел Андреевич 19 ПИ-1 b12
- Игумнова Наталья Дмитриевна 19 ПИ-2 b13
- Климов Алексей Сергеевич 19 ПИ-1 b14
- Лукичева Полина Александровна 19 ПИ-1 b15
- Лупехина Людмила Евгеньевна 19 ПИ-1 b16
- Макаров Вадим Дмитриевич 19 ПИ-1 b17
- Мурзинов Михаил Денисович 19 ПИ-1 b18
- Николаева Олеся Игоревна 19 ПИ-1 b19
- Османов Ислам Рамилевич 19 ПИ-1 b20
- Павлова Дарья Андреевна 19 ПИ-1 b21
- Сапожников Андрей Михайлович 19 ПИ-1 b22
- Сафронов Иван Дмитриевич 19 ПИ-1 b23
- Смирнов Григорий Андреевич 19 ПИ-1 b24
- Стоянов Станислав Степанович 19 ПИ-1 b25
- Трухин Егор Сергеевич 19 ПИ-1 b26
- Ускова Елена Максимовна 19 ПИ-1 b27
- Успенский Владимир Иванович 19 ПИ-1 b28
- Хорошилова Марина Александровна 19 ПИ-1 b29
- Баранов Илья Андреевич 19 ПИ-2 b30
- Бекусов Михаил Александрович 19 ПИ-2 b31
- Бодров Егор Алексеевич 19 ПИ-2 b32
- Бредихин Максим Владимирович 19 ПИ-2 b33
- Даняев Артем Андреевич 19 ПИ-2 b34
- Дыряев Даниил Александрович 19 ПИ-2 b35
- Зиганшин Никита Русланович 19 ПИ-2 b36
- Конина Татьяна Дмитриевна 19 ПИ-2 b37
- Костин Андрей Олегович 19 ПИ-2 b38
- Мингбоев Худайберди Абдухаким угли 19 ПИ-2 b39
- Моисеев Роман Михайлович 19 ПИ-2 b40
- Моничева Арина Александровна 19 ПИ-1 b41
- Мушка Никита Андреевич 19 ПИ-2 b42
- Николаев Иван Александрович 19 ПИ-2 b43
- Ожиганова Полина Максимовна 19 ПИ-2 b44
- Рыжова Ирина Игоревна 19 ПИ-2 b45
- Салахов Рамазан Маратович 19 ПИ-2 b46
- Семаев Никита Юрьевич 19 ПИ-2 b47
- Скугаревский Александр Сергеевич 19 ПИ-2 b48
- Столбов Ярослав Владиславович 19 ПИ-2 b49
- Таценко Алексей Михайлович 19 ПИ-1 b50
- Таценко Илья Михайлович 19 ПИ-1 b51
- Тюлин Игорь Викторович 19 ПИ-2 b52
- Фатин Максим Романович 19 ПИ-2 b53
- Хорошавина Екатерина Андреевна 19 ПИ-2 b54
- Цветков Дмитрий Алексеевич 19 ПИ-2 b55
- Шарунов Евгений Александрович 19 ПИ-2 b56
- Шатилов Виктор Алексеевич 19 ПИ-2 b57
- Широков Александр Анатольевич 19 ПИ-2 b58
- Стифеев Никита Андреевич 19 ПИ-2 b59
- Малинин Дмитрий Дмитриевич 19 ПМИ-2 b60
- Бакланов Алексей Александрович 19 ПМИ-2 b61
- Баринов Даниил Сергеевич 19 ПМИ-1 b62
- Богомазов Михаил Васильевич 19 ПМИ-1 b63
- Бугров Лев Валерьевич 19 ПМИ-1 b64
- Бузанов Егор Андреевич 19 ПМИ-1 b65
- Варлачёв Валерий Максимович 19 ПМИ-1 b66
- Голованов Денис Максимович 19 ПМИ-1 b67
- Дробот Елизавета Денисовна 19 ПМИ-1 b68
- Жаравина Полина Дмитриевна 19 ПМИ-1 b69
- Зайцев Тимур Олегович 19 ПМИ-1 b70
- Кабанов Денис Сергеевич 19 ПМИ-1 b71
- Канев Владислав Олегович 19 ПМИ-1 b72
- Карцева Мария Дмитриевна 19 ПМИ-1 b73
- Касьянов Никита Юрьевич 19 ПМИ-1 b74
- Козлова Дарья Андреевна 19 ПМИ-1 b75
- Кузнецов Михаил Дмитриевич 19 ПМИ-1 b76
- Лавров Артём Романович 19 ПМИ-1 b77
- Матвеев Андрей Сергеевич 19 ПМИ-1 b78
- Машанова Карина Алексеевна 19 ПМИ-1 b79
- Наумов Никита Александрович 19 ПМИ-1 b80
- Нещеткин Глеб Максимович 19 ПМИ-1 b81
- Пасманик Ирина Дмитриевна 19 ПМИ-1 b82
- Рогозян Анастасия Тимофеевна 19 ПМИ-1 b83
- Соболев Данил Александрович 19 ПМИ-1 b84
- Софронов Валерий Александрович 19 ПМИ-1 b85
- Трутнев Алексей Игоревич 19 ПМИ-1 b86
- Тумаков Вадим Сергеевич 19 ПМИ-1 b87
- Фролова Ольга Михайловна 19 ПМИ-1 b88
- Шарибжанова Диана Рашидовна 19 ПМИ-1 b89
- Щеникова Анна Юрьевна 19 ПМИ-1 b90
- Андросов Вадим Дмитриевич 19 ПМИ-2 b91
- Бирина Елизавета Сергеевна 19 ПМИ-2 b92
- Булатов Дмитрий Александрович 19 ПМИ-2 b93
- Демашов Никита Александрович 19 ПМИ-2 b94
- Добряев Иван Александрович 19 ПМИ-2 b95
- Дрожжачих Евгений Валерьевич 19 ПМИ-2 b96
- Егорова Кристина Олеговна 19 ПМИ-2 b97
- Загоскин Владислав Андреевич 19 ПМИ-2 b98
- Зарубина Ирина Михайловна 19 ПМИ-2 b99
- Иванов Даниил Андреевич 19 ПМИ-2 b100
- Клыков Антон Романович 19 ПМИ-2 b101
- Королев Денис Витальевич 19 ПМИ-2 b102
- Краюшкина Екатерина Алексеевна 19 ПМИ-2 b103
- Назаров Вячеслав Андреевич 19 ПМИ-2 b104
- Оленев Дмитрий Сергеевич 19 ПМИ-2 b105
- Панина Полина Сергеевна 19 ПМИ-2 b106
- Прыгаев Денис Алексеевич 19 ПМИ-2 b107
- Рогов Андрей Дмитриевич 19 ПМИ-2 b108
- Симонова Арина Валерьевна 19 ПМИ-2 b109
- Созинов Кирилл Игоревич 19 ПМИ-2 b110
- Титова Нина Ивановна 19 ПМИ-2 b111
- Уртюков Илья Алексеевич 19 ПМИ-2 b112
- Хорев Егор Алексеевич 19 ПМИ-2 b113
- Шабаршин Леонид Георгиевич 19 ПМИ-2 b114
Для выполнения работы необходимо:
- Выполнить fork репозитария в свой аккаунт.
- Выполнить клонирование репозитария из своего аккаунта к себе на локальную машину (
git clone
). - Создать ветку git с индивидуальным номером (
git branch имя_ветки
). - Сделать ветку активной (
git checkout имя
). - Необходимо разместить как исходные файлы с решениями задач, поместив cpp файлы в src, а заголовочные - в include.
- Добавить файлы в хранилище (
git add
). - Выполнить фиксацию изменений (
git commit -m "комментарий"
). - Отправить содержимое ветки в свой удаленный репозитарий (
git push origin имя_ветки
). - Создать пул-запрос в репозитарий группы и ждать результата от GitHub Actions.