# Практика. Калькулятор алгебраических выражений ## Описание проекта Необходимо реализовать функцию `calc()`. Она принимает единственный аргумент — строку. Это алгебраическое выражение, состоящее из чисел, символов математических операций и скобок. Например: ``` 81.0-(2.5+1)/3 ``` Если в числе есть дробная часть, то она отделяется точкой: `71.45`. Допустимы числа с опущенной целой или дробной частью: `.5`, `22.`. В таких случаях опущенная часть считается равной нулю. Математическими операциями могут быть: сумма `+`, разность `-`, произведение `*`, деление `/`. Приоритет операций умножения и деления выше, чем сложения и вычитания. Все перечисленные операции [левоассоциативны:](https://ru.wikipedia.org/wiki/%D0%9E%D1%87%D0%B5%D1%80%D1%91%D0%B4%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9) при отсутствии скобок выражение с операциями одинакового приоритета вычисляется слева направо. Если бы среди операций были правоассоциативные, это бы немного усложнило код решения. Функция `calc()` должна вернуть вещественное число — результат вычисленного выражения. Либо `None`, если выражение составлено некорректно. Считаем, что входных данных, приводящих к делению на ноль, не будет. ## Примеры Корректно составленное выражение: ``` (1-2.8)*3 ``` Значение функции `calc()`: ``` -5.4 ``` Выражение с пропущенной закрывающей скобкой: ``` (16/2*3 ``` Выражение с недопустимыми символами (пробелами, буквами `a` и `b`): ``` 5*a + b ``` Выражение с нарушенной последовательностью математических операций: ``` 10++2 ``` Выражение, в котором неправильно записаны числа: ``` 1.2.3-..5 ``` Так как в этих четырех выражениях есть ошибки, функция `calc()` для них должна вернуть `None`. ## Тестирование Вы можете дописать свои варианты алгебраических выражений в скрипт `calc.py` и проверить, как ведет себя функция `calc()` на различных входных данных. Чтобы запустить скрипт `calc.py`, нажмите кнопку «Запустить». Когда функция `calc()` будет готова к тестированию, нажмите кнопку «Отправить на проверку». По ней запустятся юнит-тесты из файла `test_calc.py`. В этом же файле можно посмотреть ожидаемые значения функции для набора алгебраических выражений. ## Теория Калькулятор алгебраических выражений — классическое задание, которое дают студентам, обучающимся программированию. Поэтому если вы знаете, как выполнить проект, можете сразу перейти к написанию кода и пропустить этот раздел. Здесь будет рассмотрен один из подходов к решению. ## Алгоритм вычисления выражения Декомпозируем вычисление алгебраического выражения на три подзадачи: токенизация, перевод в постфиксную форму, вычисление выражения в постфиксной форме. ### 1. Токенизация **Токенизация** — лексический анализ строки, разбиение ее на токены. В контексте нашей задачи токен — это неделимая составляющая арифметического выражения: математическая операция, число (операнд), скобка. Входные данные для токенизации — строка с выражением. Например: ``` 9.5-(1+3) ``` На выходе — список токенов: ``` ┌───────┐┌────────┐┌───────┐┌───────┐┌────────┐┌───────┐┌───────┐ │ 9.5 ││ - ││ ( ││ 1 ││ + ││ 3 ││ ) │ └───────┘└────────┘└───────┘└───────┘└────────┘└───────┘└───────┘ число операция скобка число операция число скобка ``` Токенизацию строки удобно проводить с помощью конечного автомата (КА). Упрощенно он [описывается](https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82) как устройство, принимающее конечное число состояний. КА читает по одному символу за раз некую входную последовательность. В зависимости от текущего состояния и прочитанного символа КА меняет свое состояние. При переходе между состояниями он может выполнять дополнительную работу. КА незаменим в случаях, когда требуется удобно и гибко описать последовательность обработки входных данных, перехода между состояниями и выполнения при этом каких-то действий. Составим КА для токенизации арифметического выражения. Его входная последовательность — это строка из цифр, точки и символов `+`, `-`, `*`, `/`, `(`, `)`. Любой другой символ будем считать ошибочным. Возможные состояния КА: начало работы; прочитан односимвольный токен; накапливается целая часть числа; накапливается дробная часть числа; произошла ошибка. Односимвольный токен — это скобка либо математическая операция. Опишем этот КА таблицей переходов: | Текущее состояние | Прочитанный символ | Новое состояние | | ---------------------------------- | ------------------ | ---------------------------------- | | Начало работы | Цифра | Накапливается целая часть числа | | | Точка | Накапливается дробная часть числа | | | Операция | Прочитан односимвольный токен | | | Скобка | Прочитан односимвольный токен | | | Другой | Ошибка | | Прочитан односимвольный токен | Цифра | Накапливается целая часть числа | | | Точка | Накапливается дробная часть числа | | | Операция | Прочитан односимвольный токен | | | Скобка | Прочитан односимвольный токен | | | Другой | Ошибка | | Накапливается целая часть числа | Цифра | Накапливается целая часть числа | | | Точка | Накапливается дробная часть числа | | | Операция | Прочитан односимвольный токен | | | Скобка | Прочитан односимвольный токен | | | Другой | Ошибка | | Накапливается дробная часть числа | Цифра | Накапливается дробная часть числа | | | Точка | Ошибка | | | Операция | Прочитан односимвольный токен | | | Скобка | Прочитан односимвольный токен | | | Другой | Ошибка | При чтении ошибочного символа КА из любого состояния переходит в состояние ошибки. При чтении точки из состояния накопления целой части числа КА переходит к накоплению дробной части. А из состояния накопления дробной части — в состояние ошибки. Потому что в записи одного числа может быть только одна точка. Обратите внимание, что КА умеет определять только два типа ошибок, которые могут быть допущены в алгебраическом выражении: если прочитан неожиданный символ (например, буква `a`) или если в числе присутствует больше одной точки. И это абсолютно нормально: более сложные ошибки должны определяться на следующих этапах разбора алгебраического выражения. Единственная задача КА — разбить строку на последовательность корректных токенов. В таблицу переходов можно было бы добавить столбец «Действие» и в нем описать функции, которые должны вызываться при переходе между состояниями. Например, при переходе в состояние «Ошибка» требуется прерывать обработку токенов и возвращать `None`. ### 3. Перевод инфиксной формы выражения в постфиксную Инфиксная запись выражения означает, что математические операции идут между числами, а скобки изменяют приоритет вычислений: ``` 1+2 ``` Алгоритмизировать вычисление выражения в инфиксной записи вполне реально. Но сделать это для постфиксной записи гораздо проще. Постфиксная запись предполагает, что в выражении сначала идут числа, а затем — операции: ``` 1 2 + ``` Постфиксная форма записи также [известна как](https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D0%BB%D1%8C%D1%81%D0%BA%D0%B0%D1%8F_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D1%8C) обратная бесскобочная запись или польская инверсная запись. Входные данные для построения постфиксной формы — это набор токенов, на которые разобрано выражение в инфиксной форме. Например, выражение `9.5-(1+3)`, представленное токенами: ``` ┌───────┐┌────────┐┌───────┐┌───────┐┌────────┐┌───────┐┌───────┐ │ 9.5 ││ - ││ ( ││ 1 ││ + ││ 3 ││ ) │ └───────┘└────────┘└───────┘└───────┘└────────┘└───────┘└───────┘ число операция скобка число операция число скобка ``` После перевода выражения в постфиксную форму на выходе мы получим последовательность токенов, идущих уже в другом порядке. Причем скобок среди них не будет: ``` ┌───────┐┌────────┐┌───────┐┌────────┐┌────────┐ │ 9.5 ││ 1 ││ 3 ││ + ││ - │ └───────┘└────────┘└───────┘└────────┘└────────┘ число число число операция операция ``` Выражение `9.5-(1+3)` в постфиксной записи выглядит как `9.5 1 3 + -`. Для преобразования инфиксной формы в постфиксную используется [алгоритм Дейкстры](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BE%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%B0%D0%BD%D1%86%D0%B8%D0%B8) «Сортировочная станция». Такое название он получил из-за сходства с действиями на железнодорожных сортировочных станциях. И вот как он выглядит применительно к нашей задаче, то есть для алгебраических выражений, в которых допустимы только бинарные левоассоциативные операции. **Шаг 1.** В цикле проходим по токенам: — Если токен — число, добавляем его к выходному списку токенов. — Если токен — открывающая скобка, помещаем его в стек. — Если токен — закрывающая скобка: пока верхним элементом стека не станет открывающая скобка, перекладываем из него токены в выходной список. Открывающая скобка удаляется из стека и не добавляется в выходной список. Если стек закончился и в нем не обнаружена открывающая скобка, то в алгебраическом выражении допущена ошибка: не согласованы скобки. — Если токен — математическая операция: пока операция на вершине стека имеет больший или равный приоритет, перемещаем токены из стека в выходной список. Затем помещаем токен с данной операцией в стек. **Шаг 2.** Когда входная последовательность токенов закончилась, выталкиваем из стека все токены в выходной список. При этом стек должен содержать только токены операций. Если это не так, то в алгебраическом выражении не согласованы скобки. После выполнения этих двух шагов в выходном списке сформировано алгебраическое выражение в постфиксной форме. ### 4. Вычисление выражения в постфиксной форме На предыдущем этапе был получен список токенов алгебраического выражения в постфиксной форме. Осталось получить результат этого выражения. Воспользуемся [стековым алгоритмом](https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D0%BB%D1%8C%D1%81%D0%BA%D0%B0%D1%8F_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D1%8C#%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BD%D0%B0_%D1%81%D1%82%D0%B5%D0%BA%D0%B5) вычисления выражения в постфиксной форме: В цикле проходим по токенам: — Если токен — число, то он помещается в стек. — Если токен — математическая операция, то она выполняется. Для этого извлекается необходимое количество операндов из стека, к ним применяется операция, и результат вычисления помещается в стек. Важно помнить, что значение на вершине стека — это правый операнд, а не левый. После выполнения этого цикла в стеке должно остаться единственное значение. Это и есть результат алгебраического выражения.