# Практика. Калькулятор алгебраических выражений ## Описание проекта Необходимо реализовать функцию `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()` должна вернуть вещественное число — результат вычисленного выражения. Либо ошибку, отличную от `nil`, если выражение составлено некорректно. Считаем, что входных данных, приводящих к делению на ноль, не будет. ## Примеры Корректно составленное выражение: ``` (1-2.8)*3 ``` Значение функции `calc()`: ``` -5.4 ``` Выражение с пропущенной закрывающей скобкой: ``` (16/2*3 ``` Выражение с недопустимыми символами (пробелами, буквами `a` и `b`): ``` 5*a + b ``` Выражение с нарушенной последовательностью математических операций: ``` 10++2 ``` Выражение, в котором неправильно записаны числа: ``` 1.2.3-..5 ``` Так как в этих четырех выражениях есть ошибки, функция `calc()` для них должна вернуть ошибку, отличную от `nil`. ## Тестирование Вы можете дописать свои варианты алгебраических выражений в файле `main.go` и проверить, как ведет себя функция `calc()` на различных входных данных. Чтобы скомпилировать и запустить программу с точкой входа в `main.go`, нажмите кнопку «Запустить». Когда функция `calc()` будет готова к тестированию, нажмите кнопку «Отправить на проверку». По ней запустятся юнит-тесты из файла `main_test.go`. В этом же файле можно посмотреть ожидаемые значения функции для набора алгебраических выражений. ## Теория Калькулятор алгебраических выражений — классическое задание, которое дают студентам, обучающимся программированию. Поэтому если вы знаете, как выполнить проект, можете сразу перейти к написанию кода и пропустить этот раздел. Здесь будет рассмотрен один из подходов к решению. ## Алгоритм вычисления выражения Декомпозируем вычисление алгебраического выражения на три подзадачи: - токенизация, - синтаксический анализ, - вычисление выражения. ### 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`) или если в числе присутствует больше одной точки. И это абсолютно нормально: более сложные ошибки должны определяться на следующих этапах разбора алгебраического выражения. Единственная задача КА — разбить строку на последовательность корректных токенов. В таблицу переходов можно было бы добавить столбец «Действие» и в нем описать функции, которые должны вызываться при переходе между состояниями. Например, при переходе в состояние «Ошибка» требуется прерывать обработку токенов и возвращать ошибку. ### 2. Синтаксический анализ В нашем случае этап синтаксического анализа нужен для того, чтобы построить **AST**. AST расшифровывается как **abstract syntax tree**, **абстрактное синтаксическое дерево**. На входе мы имеем список токенов, на выходе — AST. Листьями AST являются операнды. Родительские узлы — операции. Для выражения `9.5-(1+3)` AST выглядит следующим образом: ``` start └─ - ├─ 9.5 └─ + ├─ 1 └─ 3 ``` Здесь для наглядности в качестве корня используется метка `start`. Однако это необязательно. Для генерации AST рекомендуется воспользоваться [грамматикой](https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0). **Грамматика** — это способ описания языка. Грамматика выделяет некоторые подмножества из множества всех слов некоторого конечного алфавита. В нашем случае грамматика имеет следующий вид: ``` expr = expr "+" term | expr "-" term | term term = term "*" factor | term "/" factor | factor factor = "(" expr ")" | number ``` Основываясь на этой грамматике, необходимо определить, представлено ли выражение в форме `expr`. Символ `|` можно читать как логическое `ИЛИ`. Таким образом, по первой строчке можно заключить следующее. Если выражение представлено в форме `term`, `expr "+" term`, либо `expr "-" term`, то это выражение в форме `expr`. Символы, указанные в кавычках, должны стоять в выражении буквально. Аналогично для двух других строк. Слово `number` означает любое число. Предполагая, что вам дали на вход правильное выражение, разберите его по этой грамматике. Попутно сгенерируйте AST. Например, пусть выражение `9.5-(1+3)` в форме `expr`. Тогда оно должно быть в одной из трех форм, представленных грамматикой. Нужно проверить каждую из них. **Шаг 1**. Как мы видим, выражение в форме `expr "-" term`. Здесь в качестве `expr` выступает `9.5`, а в качестве `term` — `(1+3)`. Поэтому мы должны сгенировать `AST` с вершиной `-` и операндами: `expr` и `term`, каждый из которых мы разберем в следующих шагах. **Шаг 2**. Операнд `expr`, равный `9.5`, представляет собой `term`, который является `factor`. Он в свою очередь — `number`. Возвращаем `9.5` в качестве листа дерева, полученного на первом шаге. **Шаг 3**. Операнд `term`, равный `(1+3)`, представляет собой `factor` в виде `"(" expr ")`. Необходимо разобрать выражение `expr` и вернуть в качестве листа дерева полученное поддерево. Если выражение невозможно разобрать по этой грамматике, то оно некорректное. В этом случае верните ошибку. **Подсказка**. Рекурсию в первых двух правилах грамматики можно раскрыть через цикл. Тогда получим: ``` expr = term ["+","-"] term ["+","-"] ... term term = factor ["*","/"] factor ["*","/"] ... factor factor = number | "(" expr ")" ``` Выражение ["+","-"] означает, что в этом месте стоит либо "+", либо "-". Аналогично — для ["*","/"]. Многоточие `...` означает «и так далее». ### 3. Вычисление выражения На предыдущем этапе было получено абстрактное синтаксическое дерево. Осталось рекурсивно пройти по дереву и вычислить результат выражения. ## Структура программы ``` . ├── cmd │ ├── main.go │ └── main_test.go ├── internal │ ├── cast │ │ └── cast.go │ ├── cerrors │ │ └── cerrors.go │ ├── command │ │ ├── command.go │ │ ├── lexer.go │ │ ├── parser.go │ │ └── solver.go │ └── lexemes │ │ └── lexemes.go ├── go.mod └── go.sum ``` ### main.go Пакет `main`. Здесь содержится функция `calc()` и ее вызов из функции `main()`. ### main_test.go Пакет `main`. Здесь содержатся тесты. Их трогать не нужно. ### cast.go Пакет `cast`, состоящий из единственного файла. Он должен реализовывать работу с AST. Здесь рекомендуется сделать структуру для AST и функции по работе с ней. * `NewAst` — функция для создания нового пустого AST * `MustAppendNode` — функция, добавляющая новый узел к существующему узлу дерева по его `id`, либо вызывающая панику, в случае неудачи * `MustAppend` — функция, добавляющая поддерево к существующему узлу дерева по его `id`, либо вызывающая панику в случае неудачи * `Print` — функция, выводящая AST на экран ### cerrors.go Пакет `cerrors`. Здесь должен содержаться список ошибок, которые могут произойти. Вы можете возвращать любые разумные значения ошибок, лишь бы они были отличны от `nil`. ### command.go Пакет `command`. Здесь должна быть объявлена структура с тремя полями: алгебраическое выражение в сыром виде, в виде токенов и в виде AST. ### lexer.go Пакет `command`. Здесь должен быть реализован КА для разбора арифметического выражения на токены. ### parser.go Пакет `command`. Здесь должен быть реализован синтаксический анализ. Необходимо разобрать токены в AST. ### solver.go Пакет `command`. Здесь должен быть реализован решатель, вычисляющий результат выражения на основе AST. ### lexemes.go Пакет `lexemes`, состоящий из единственного файла. Должен содержать структуру токена и другие константы. Токен состоит из типа токена и его значения.