Практическая работа №10

Разработка калькулятора при помощи обратной польской записи

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

Основные теоретические положения

Обратная польская запись (ОПЗ) / Постфиксная нотация

Обратная польская запись (ОПЗ), или постфиксная нотация, — это форма записи математических выражений, в которой операторы располагаются после своих операндов. В отличие от привычной инфиксной нотации (где оператор находится между операндами, например, 2 + 3), ОПЗ не требует использования скобок для определения порядка выполнения операций, поскольку порядок однозначно задается расположением операторов и операндов.

Нотация	Пример	Описание
Инфиксная	`(2 + 3) * 4`	Оператор находится между операндами. Требует скобок и правил приоритета.
Постфиксная (ОПЗ)	`2 3 + 4 *`	Оператор находится после операндов. Порядок вычисления однозначен.

Преимущества ОПЗ:

Устранение скобок: Выражения не требуют скобок, что упрощает парсинг.
Простота вычисления: Алгоритм вычисления ОПЗ-выражения очень прост и основан на использовании стека.

Роль структуры данных Стек

Структура данных стек (LIFO — Last In, First Out) является ключевой для работы с ОПЗ. Она используется в двух основных процессах:

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

Алгоритмы реализации

1. Алгоритм преобразования инфиксного выражения в ОПЗ (Алгоритм сортировочной станции)

Этот алгоритм, известный как Алгоритм сортировочной станции (Shunting-yard algorithm), использует два основных компонента: входную строку (инфиксное выражение), стек для операторов и выходную строку (ОПЗ-выражение).

Детальные шаги алгоритма:

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

Пример пошагового преобразования: 2 + 3 * 4

Входной символ	Стек операторов	Выход (ОПЗ)	Примечание
`2`	`[]`	`2`	Операнд, сразу в выход
`+`	`[+]`	`2`	Оператор, помещаем в стек
`3`	`[+]`	`2 3`	Операнд, сразу в выход
`*`	`[+, *]`	`2 3`	`*` имеет больший приоритет, чем `+`, помещаем в стек
`4`	`[+, *]`	`2 3 4`	Операнд, сразу в выход
Конец	`[+, *]`	`2 3 4 * +`	Извлекаем оставшиеся операторы: сначала `*`, потом `+`
Итог	`[]`	`2 3 4 * +`

2. Алгоритм вычисления ОПЗ-выражения

Этот алгоритм использует один стек для операндов.

Детальные шаги алгоритма:

Инициализация: Создать пустой стек для операндов.
Чтение элементов: Читать элементы ОПЗ-выражения слева направо (элементы разделены пробелами).
Операнд (число): Если элемент — операнд, поместить его в стек.
Оператор: Если элемент — оператор (например, +, -, *, /):
- Извлечь два верхних операнда из стека (первый извлеченный — operand2, второй — operand1).
- Выполнить операцию: result = operand1 operator operand2.
- Поместить result обратно в стек.
Конец выражения: Когда выражение закончилось, единственный оставшийся элемент в стеке является результатом вычисления.

Пример пошагового вычисления: 2 3 4 * +

Входной элемент	Стек операндов	Операция	Примечание
`2`	`[2]`		Операнд, помещаем в стек
`3`	`[2, 3]`		Операнд, помещаем в стек
`4`	`[2, 3, 4]`		Операнд, помещаем в стек
`*`	`[2, 12]`	`3 * 4 = 12`	Извлекаем 4 и 3, выполняем операцию, помещаем 12
`+`	`[14]`	`2 + 12 = 14`	Извлекаем 12 и 2, выполняем операцию, помещаем 14
Итог	`[14]`		Результат — 14

Пример реализации (C++): Общие принципы

Для реализации калькулятора на C++ рекомендуется использовать стандартный контейнер std::stack из библиотеки <stack>.

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <cmath>
#include <map>

// Псевдокод для реализации:

// 1. Функция определения приоритета оператора:
// int get_precedence(char op) { ... }

// 2. Функция преобразования в ОПЗ:
// std::string infix_to_rpn(const std::string& infix) {
//     // Используем std::stack<char> для операторов
//     // Реализуем логику Алгоритма сортировочной станции
// }

// 3. Функция вычисления ОПЗ:
// double evaluate_rpn(const std::string& rpn_expression) {
//     // Используем std::stack<double> для операндов
//     // Реализуем логику вычисления ОПЗ
// }

// 4. Основная функция main():
// int main() {
//     // Запрашиваем инфиксное выражение
//     // Вызываем infix_to_rpn
//     // Вызываем evaluate_rpn
//     // Выводим результат
// }

Компиляция и запуск программы

g++ calculator.cpp -o calculator
./calculator

Общие требования

Программа должна быть написана на языке C++.
Обязательно использование структуры данных стек для реализации алгоритмов.
Программа должна корректно обрабатывать целые и дробные числа.
Программа должна обрабатывать основные арифметические операции: +, -, *, /.
Программа должна корректно обрабатывать скобки ( и ).
Программа должна выводить промежуточные результаты (ОПЗ-выражение) и конечный результат.

Задания для выполнения

Базовый калькулятор

№	Задача	Описание
1	Преобразование в ОПЗ	Реализуйте функцию, которая принимает инфиксное выражение (строку) и преобразует его в ОПЗ (строку). Поддерживаемые операции: `+`, `-`, `*`, `/`, скобки.
2	Вычисление ОПЗ	Реализуйте функцию, которая принимает ОПЗ-выражение (строку) и вычисляет его значение, используя стек для операндов.
3	Интеграция	Объедините функции: пользователь вводит инфиксное выражение, программа выводит ОПЗ и результат вычисления. Протестируйте на выражениях: `(2 + 3) * 4` и `10 / (5 - 3)`.

Контрольные вопросы

Объясните, почему для вычисления ОПЗ-выражения необходим стек.
В чем основное отличие инфиксной, префиксной и постфиксной нотаций?
Опишите принцип работы “Алгоритма сортировочной станции” (Shunting-yard algorithm).
Какие правила приоритета и ассоциативности операторов необходимо учитывать при преобразовании в ОПЗ?
Как в вашем алгоритме обрабатывается унарный минус?