Оценивание: перевод: стандартная задача, 20 баллов, вычисление: стандартная задача, 20 баллов.
- Перевести выражение в обратную польскую запись.
- Посчитать значение выражения (если оно не содержит переменных).
Выражение содержит следующие термы: бинарные арифметические операции +, -, *, скобки, целые числа, переменные (последовательность латинских букв и цифр, начинается с буквы). Также реализовать операции из таблицы 1. Для упрощения можно принимать входное выражение с термами, разделенными пробелами.
* Доп. задание: реализовать операцию унарный минус.
Пример.
| Выражение | Обратная польская запись | Результат |
| 10 + 2 * 5 | 10 2 5 + * | 20 |
| ( 10 + 2 ) * 5 | 10 2 + 5 * | 60 |
| 15 * — ( 3 — 4 ) | 15 3 4 — u- * | 15 |
примечание: унарная операция стоит в начале формулы, после скобки или знака операции, в обратной польской записи унарный минус требуется записать по другому, например u- или каким-то другим символом, чтобы отличить от бинарного минуса.
Варианты.
| Номер | Бинарная операция | Функция 1 | Функция 2 | Функция 3 | ФИО |
| 1 | % | abs | sqr | cube | Кваша |
| 2 | / | sqrt | cube | pow10 | Илларионова |
| 3 | ^ | sign | abs | pow10 | Недомовный |
| 4 | % | abs | sqrt | sign | Бровко |
| 5 | / | sqr | sqrt | pow2 | Стеблинский |
| 6 | ^ | sign | abs | pow10 | Ковальский |
| 7 | % | cube | sqr | pow10 | Зелинский |
| 8 | / | sqr | pow2 | cube | Григорян |
| 9 | ^ | fact | sign | pow10 | Байков |
| 10 | % | pow2 | abs | cube | Калачёв |
| 11 | / | sqr | fact | pow10 | Куленюк |
| 12 | ^ | cube | pow2 | pow10 | |
| 13 | & | fact | abs | cube | |
| 14 | | | cube | fact | pow10 | |
| 15 | & | fact | sqrt | abs | |
| 16 | | | sqrt | abs | pow10 | |
| 17 | & | sign | sqr | pow10 | |
| 18 | | | cube | sqr | sign | |
| 19 | & | abs | sqrt | sqr | |
| 20 | | | sqrt | cube | pow10 |
% — остаток по модулю, / — деление нацело, ^ — возведение в степень, & — поразрядное И, | — поразрядное ИЛИ
abs – модуль, sign – знак числа (-1, 0, 1), sqr – возведение в квадрат, sqrt – квадратный корень, округленный до целого, cube – куб числа, fact – факториал числа, pow2 – два в степени аргумент функции, pow10 — десять в степени аргумент функции.
Здесь представлены некоторые материалы по стекам и очередям, в первую очередь лекция по алгоритму сортировочной станции перевода выражений в обратную запись (wiki): слайды лекции на Google Drive.
Может быть, Вам пригодятся эти материалы: Лекция Примеры АТД (Disjoint Set Union, Список), линейные структуры в Java Collection Framework, Справочник по Java Collections Framework, Структуры данных в картинках. ArrayList.