Алгоритм сортировочной станции

В этом репозитории содержится реализация алгоритма сортировочной станции на языке C++.

Фичи

• Работа с числами с плавающей точкой. Используется тип double.
• Поддержка скобок в выражении.
• Поддержка арифметических операций:
  • '+' сложение
  • '-' вычитание
  • '*' умножение
  • '/' деление
  • '^' возведение в степень
• Поддержка функций. Поддержка n-арных функций:
  • Тригонометрия: sin, cos, tan, cot
  • abs(x) - абсолютное значение x (модуль числа x)
  • sgn(x) - сигнум числа x: sgn(x) = {1 IF x > 0; 0 IF x = 0; -1 IF x < 0}
  • pow(a, b) - аналогично 'a ^ b'
• Поддержка унарного минуса:
  • -(...)
  • -function(...)
  • -a^b = -(a ^ b)

Использование

double Eval::eval(const std::string&)

Вычисляет значение выражения заданного строковым параметром.

Описание алгоритма

Полный алгоритм вычисления выражений (evaluation) состоит из 3 этапов:

1. Разбиение строки на токены (Структура, п. 3).
2. Алгоритм сортировочной станции, трансформация в обратную польскую нотацию (Структура, п. 4).
3. Вычисление выражения в обратной польской нотации (Структура, п. 5).

• Для удобства вычисления реализована композиция всех 3 шагов (Структура, п. 2).

Разбиение на токены (токенизация)

1. В исходной строке пропускаются все пробельные символы (' ', '\n', '\t').
2. Если встречается число, осуществляется попытка сборки числа (eval.cpp: constructNumber).
3. Если встречается оператор:
   1. Осуществляется проверка на унарный минус.
   2. Создаётся токен с указателем на соответствующее представление оператора из OperatorMap operators.
4. Если встречается скобка, создаётся токен с типом, соответствующим скобке (RightBrace, LeftBrace).
5. Если встречается запятая, создаётся токен с типом разделителя аргументов (ArgsSep).
6. Если встречается буквенный символ, осуществляется попытки сборки имени функции (eval.cpp: constructName).
7. Если символ в строке не обработан к этому моменту, выбрасывается ошибка InvalidInput.

На каждом этапе 1-6 осуществляется проверка на то, может ли новый токен с типом Т1 соответствовать предыдущему токену с типом Т2.

Алгоритм сортировочной станции (трансформация в ОПН)

Пока что пусто

Вычисление выражения в ОПН

Пока что пусто

Структура

1. Пространство имён Eval. Далее всё, что в нём определено.
2. double eval(const std::string&) - вычисление выражения заданного строкой.
3. std::vector<Token> tokenize(const std::string&) - токенизация выражения заданного строкой.
4. std::vector<Token> shuntingYard(const std::vector<Token>&) трансформация токенизированного выражения в Обратную Польскую Нотацию. Непосредственно Алгоритм Сортировочной Станции.
5. double eval(const std::vector<Token>&) - вычисление выражения в Обратной Польской Нотации.
6. struct Token - представление минимальной единицы выражения (токена).
   1. enum class Type - тип токена.
      1. Number(0) - число.
      2. Operator - оператор.
      3. Function - имя функции.
      4. LeftBrace - левая скобка: '('.
      5. RightBrace - правая скобка: ')'.
      6. ArgsSep - разделитель аргументов функции ','.
   2. union UValue - возможные значения токена в соответствии с его типом.
      1. double number - если токен - число.
      2. Operator* oper - если токен - оператор.
      3. Function* func - если токен - функция.
   3. Type type - тип токена.
   4. UValue value - значение этого токена.
   5. Конструкторы определены для каждого возможного типа токена. Также определен конструктор без параметров.
7. struct Operator - представление оператора.
   1. std::string name - имя оператора.
   2. unsigned int priority - приоритет оператора.
   3. enum class Associativity - ассоциативность оператора
      1. Left(0) - левая.
      2. Right - правая
   4. double(*func)(double, double) - функция, выполняемая над операндами оператора.
8. struct Function - представление функции.
   1. std::string name - имя функции.
   2. size_t argc - число аргументов, принимаемых функцией.
   3. double(*func)(std::vector&) - функция, выполняемая над аргументами.
9. std::ostream& operator<<(std::ostream&, Token) - вставка токена в поток вывода. Для удобного вывода токенов в консоль/файл.
10. using OperatorMap = typename std::unordered_map<char, Operator*> - соответствие между символом оператора и его представлением.
11. using FunctionMap = typename std::unordered_map<std::string, Function*>; - соответствие между именем функции и её представлением.
12. OperatorMap operators - все доступные операторы определены в этом отображении.
13. FunctionMap functions - все доступные функции определены в этом отображении.
14. enum class MinusState - состояния токенизатора для разграничения бинарного и унарного операторов -.