Если текущий обрабатываемый символ:
- Оператор или скобка: просто токенизируем (S1)
- Цифра или буква: записываем в буфер, т.к. все число или называние функции может состоять из нескольких символов (S2, S3, S4). Обратите внимание: название функций может также содержать в себе цифры, например log2(x)
Но это все слова. Давайте воплотим это в код.
Класс токена
Мы хотим, чтобы класс токена хранил информацию о типе токена и его ассоциативности, а также сам токен в виде строки:
class Token < public: // Тип enum Type < OPERATOR, // унарный/бинарный оператор L_PARANTHESIS, // открывающая скобка R_PARANTHESIS, // закрывающая скобка INT_LITERAL, // целое число FLOAT_LITERAL, // число с плавающей точкой FUNCTION, // функция SEPARATOR // разделитель аргументов функции >; // Ассоциативность enum OperatorAssociativity < NONE, // токен - не оператор RIGHT, // правоассоциативный LEFT // левоассоциативный >; Token(std::string token, Type type, OperatorAssociativity asc = NONE); // Приоритет int getPrecendance() const; // Геттеры ( ну у нас же ООП :D ) const Type& getType() const < return type; >const OperatorAssociativity& getAsc() const < return opAsc; >const std::string& getStr() const < return str; >private: Type type; OperatorAssociativity opAsc; std::string str; >;
Token::Token(std::string token, Type type, OperatorAssociativity asc) : type , str < // если токен - оператор, но ассоциативность не задана - ошибка (алгоритма) if(type == OPERATOR && asc == NONE) throw std::logic_error("Associativity required!"); // если токен - НЕ оператор, но ассоциативность задана - ошибка else if(type != OPERATOR && asc != NONE) throw std::logic_error("Non-operator token can't have an associativity!"); opAsc = asc; >
Функция getPrecedance() вовращает приоритет оператора в виде целого числа. Приоритет тем меньше, чем меньше число. Если токен - не оператор, генерирует исключение.
int Token::getPrecendance() const < static std::mapop_leftassociative = < , , , , >; static std::map op_rightassociative = < // унарное отрицание >; // В зависимости от ассоциативности один и тот же символ означает разные операторы switch(opAsc) < case LEFT: // Если str явлеяется ключом map-а, значит мы знаем такой оператор if(op_leftassociative.contains(str)) return op_leftassociative[str]; else throw Error("Unknown Operator!", Error::Syntax); break; case RIGHT: if(op_rightassociative.contains(str)) return op_rightassociative[str]; else throw Error("Unknown Operator!", Error::Syntax); break; case NONE: throw std::logic_error( std::format("Token \"<>\" is not an operatator, impossible.", str) ); break; > >
Отмечу, что для сигнализации об ошибках я использую собственный класс Error для обозначения синтаксических и (в дальнейшем) математических ошибок в исходном инфиксном выражении, и std::logic_error для обозначения программных багов.
Токенизатор-автомат
Во первых, состояния:
enum State < S0, // Стартовое S1, // Токенизация скобки/оператора S2, // Запись целого числа в буфер S3, // Запись floating-point числа в буфер S4, // Запись функции в буфер S5 // Токенизация записанного числа/функции из буфера >;
Теперь конечный автомат. Реализуем его функцией, принимающей на вход сроку-выражение, а на выходе дающую вектор токенов.
void tokenize(const std::string &expr, std::vector &tokens) < // .
Объявим необходимые переменные:
// . State state = S0; // Устанавливаем состояние в начальное std::string validOperators = "+-*^/"; // Допустимые операторы // каким типом является текущий символ? bool isDigit, isLetter, isOp, isParanth, isPoint, isSep, isLParanth, isRParanth; std::string buffer; // Буфер Token::Type bufferTokenType = Token::INT_LITERAL; // Тип токена, записаного в буфере // .
// . for(auto& s : expr) < // Определяем тип символа isDigit = std::isdigit(s); isLetter = std::isalpha(s); isLParanth = s == '('; isRParanth = s == ')'; isParanth = isLParanth || isRParanth; isPoint = s == '.'; isSep = s == ','; isOp = validOperators.find(s) != validOperators.npos; // Если тип символа неопределен, значит ошибка в синтаксисе if(!(isDigit || isLetter || isParanth || isPoint || isSep || isOp)) throw SyntaxError(std::format("Unknown symbol: <>", s)); // Смена состояния switch(state) < case S0: if (isOp || isParanth) state = S1; else if (isDigit) state = S2; else if (isLetter) state = S4; else if (isPoint || isSep) throw SyntaxError(std::format("Unexpected symbol: <>", s)); break; case S1: if (isDigit) state = S2; else if (isLetter) state = S4; else if (isPoint || isSep) throw SyntaxError(std::format("Unexpected symbol: <>", s)); break; case S2: bufferTokenType = Token::INT_LITERAL; if (isPoint) state = S3; else if (isParanth || isOp || isSep) state = S5; else if (isLetter) throw SyntaxError(std::format("Unexpected symbol: <>", s)); break; // и так далее для состояний S3, S4, S5. Остальной код можно посмотреть в конце статьи default: break; > // .
Далее - соответствующее действия на каждое из состояний:
// . // Токенизирует оператор/скобку/разделитель auto tokenize_Op_Paranth_Sep = [&]() < /* . */ >; // Действия switch(state) < case S1: tokenize_Op_Paranth_Sep(); break; case S2: case S3: case S4: // Записываем цифру/букву в буфер buffer.push_back(s); break; case S5: // Токенизируем содержимое буфера tokens.push_back(); // Освобождаем буфер buffer.clear(); // Токенизируем текущий символ tokenize_Op_Paranth_Sep(); break; > > // конец цикла // .
Если после обработки всех символов в буфере все еще что-то осталось, токенизируем:
// . if(!buffer.empty()) tokens.push_back(); > // конец функции tokenize
С токенизатором на этом, собственно, все. Пример работы:
Код целиком приведен ниже.
#pragma once #include class Error < public: enum Type < Syntax, Math >type; Error(std::string message, Type errorType) : type < switch(errorType) < case Syntax: msg = "Syntax Error: " + message; break; case Math: msg = "Math Error: " + message; break; >> std::string what() < return msg; >private: std::string msg; >;
#pragma once #include class Token < public: // Тип enum Type < OPERATOR, // унарный/бинарный оператор L_PARANTHESIS, // открывающая скобка R_PARANTHESIS, // закрывающая скобка INT_LITERAL, // целое число FLOAT_LITERAL, // число с плавающей точкой FUNCTION, // функция SEPARATOR // разделитель аргументов функции >; // Ассоциативность enum OperatorAssociativity < NONE, // токен - не оператор RIGHT, // правоассоциативный LEFT // левоассоциативный >; Token(std::string token, Type type, OperatorAssociativity asc = NONE); // Приоритет int getPrecendance() const; const Type& getType() const < return type; >const OperatorAssociativity& getAsc() const < return opAsc; >const std::string& getStr() const < return str; >private: Type type; OperatorAssociativity opAsc; std::string str; >;
#include #include #include #include "Token.hpp" #include "Error.hpp" Token::Token(std::string token, Type type, OperatorAssociativity asc) : type , str < // если токен - оператор, но ассоциативность не задана - ошибка if(type == OPERATOR && asc == NONE) throw std::logic_error("Associativity required!"); // если токен - НЕ оператор, но ассоциативность задана - ошибка else if(type != OPERATOR && asc != NONE) throw std::logic_error("Non-operator token can't have an associativity!"); opAsc = asc; >int Token::getPrecendance() const < static std::mapop_leftassociative = < , , , , >; static std::map op_rightassociative = < // унарное отрицание >; switch(opAsc) < case LEFT: if(op_leftassociative.contains(str)) return op_leftassociative[str]; else throw Error("Unknown Operator!", Error::Syntax); break; case RIGHT: if(op_rightassociative.contains(str)) return op_rightassociative[str]; else throw Error("Unknown Operator!", Error::Syntax); break; case NONE: throw std::logic_error( std::format("Token \"<>\" is not an operatator, impossible.", str) ); break; > >
Tokenizer.hpp
#pragma once #include #include "Token.hpp" enum State < S0, // Стартовое S1, // Токенизация скобки/оператора S2, // Запись целого числа в буфер S3, // Запись floating-point числа в буфер S4, // Запись функции в буфер S5 // Токенизация записанного числа/функции из буфера >; void tokenize(const std::string &expr, std::vector &tokens);
Tokenizer.cpp
#include "Tokenizer.hpp" #include #include #include #include #include "Error.hpp" void tokenize(const std::string &expr, std::vector &tokens) < State state = S0; std::string validOperators = "+-*^/"; bool isDigit, isLetter, isOp, isParanth, isPoint, isSep, isLParanth, isRParanth; std::string buffer; Token::Type bufferTokenType = Token::INT_LITERAL; for(auto& s : expr) < // Определяем тип символа isDigit = std::isdigit(s); isLetter = std::isalpha(s); isLParanth = s == '('; isRParanth = s == ')'; isParanth = isLParanth || isRParanth; isPoint = s == '.'; isSep = s == ','; isOp = validOperators.find(s) != validOperators.npos; // Если тип символа неопределен, значит ошибка в синтаксисе if(!(isDigit || isLetter || isParanth || isPoint || isSep || isOp)) throw Error(std::format("Unknown symbol: <>", s), Error::Syntax); // Смена состояния switch(state) < case S0: if (isOp || isParanth) state = S1; else if (isDigit) state = S2; else if (isLetter) state = S4; else if (isPoint || isSep) throw Error(std::format("Unexpected symbol: \"<>\"", s), Error::Syntax); break; case S1: if (isDigit) state = S2; else if (isLetter) state = S4; else if (isPoint || isSep) throw Error(std::format("Unexpected symbol: \"<>\"", s), Error::Syntax); break; case S2: bufferTokenType = Token::INT_LITERAL; if (isPoint) state = S3; else if (isParanth || isOp || isSep) state = S5; else if (isLetter) throw Error(std::format("Unexpected symbol: \"<>\"", s), Error::Syntax); break; case S3: bufferTokenType = Token::FLOAT_LITERAL; if (isParanth || isOp || isSep) state = S5; else if (isPoint) throw Error(std::format("Unexpected symbol: \"<>\"", s), Error::Syntax); break; case S4: bufferTokenType = Token::FUNCTION; if(isLParanth) state = S5; else if(isOp || isRParanth || isSep) throw Error(std::format("Unexpected symbol \"<>\"", s), Error::Syntax); break; case S5: if (isParanth || isOp) state = S1; else if (isDigit) state = S2; else if (isLetter) state = S4; else if (isPoint || isSep) throw Error(std::format("Unexpected symbol: \"<>\"", s), Error::Syntax); break; default: break; > auto tokenize_Op_Paranth_Sep = [&]() < if(isOp) < // обработка unary negation if(tokens.size() == 0 || tokens[tokens.size()-1].getType() == Token::L_PARANTHESIS) tokens.push_back(, Token::OPERATOR, Token::RIGHT>); else tokens.push_back(, Token::OPERATOR, Token::LEFT>); > else if(isParanth) < tokens.push_back(, isRParanth ? Token::R_PARANTHESIS : Token::L_PARANTHESIS>); > else if(isSep) < tokens.push_back(, Token::SEPARATOR>); > >; // Действия switch(state) < case S1: tokenize_Op_Paranth_Sep(); break; case S2: case S3: case S4: buffer.push_back(s); break; case S5: tokens.push_back(); buffer.clear(); tokenize_Op_Paranth_Sep(); break; > > if(!buffer.empty()) tokens.push_back(); >
#include #include "Tokenizer.hpp" int main() < std::vectortokensInfix; std::string expr = "log2(23)+(2/(3.14))*(sqrt(0.1*10^(-3)/0.02))"; std::cout switch(i.getAsc()) < case Token::NONE: asc = "NONE"; break; case Token::RIGHT: asc = "RIGHT"; break; case Token::LEFT: asc = "LEFT"; break; >std::cout > catch(Error &e) < std::cerr catch(const std::exception& e) < std::cerr return 0; >
Заключение
Надеюсь, было интересно. В следующей статье, как было обещанно, будет реализация Алгоритма сортировочной станции, и калькулятор (мы же все здесь за этим собрались?) будет доведен до конца.
Пишем «калькулятор» на C#. Часть I. Вычисление значения, производная, упрощение, и другие гуси
Калькулятор у нас почему-то ассоциируется с чем-то, что должен написать каждый новичок. Возможно потому, что исторически компьютеры с той целью и создавались, чтобы считать. Но мы будем писать непростой калькулятор, не sympy конечно, но чтобы умел базовые алгебраические операции, типа дифференциирования, симплификации, а также фичи типа компиляции для ускорения вычислений.
Меньше воды! О чем статья?
Здесь будет поверхностно о построении выражения, парсинге из строки, подстановки переменной, аналитической производной, численным решении уравнения и определенного интеграла, рендеринг в формат LaTeX, комплексных числах, компиляцией функций, упрощении, раскрытии скобок, и бла бла бла. Вероятно, не в одной статье.
Для тех, кому нужно срочно что-нибудь склонировать, ссылка на репозиторий.
Берем оставшиеся с нового года печеньки, и погнали!
Для кого эта статья?
Я думаю, что статья может быть полезна новичку, но может быть те, кто чуть поопытнее, тоже найдут что-то интересное. Впрочем, я надеюсь написать статью так, чтобы ее можно было читать и не будучи C# программистом вообще.
Сборка выражения
Что такое «выражение»?
Когда я был маленький.
То я конечно хотел написать калькулятор. Что он должен уметь делать? Четыре основные операции, и в принципе куда еще больше. Так, моей задачей было посчитать значение строкового выражения, например «1 + (3 / 4 — (5 + 3 * 1))». Я взял мою любимую дельфи, и написал парсер, который сначала рекурсивно уходил в скобочки, а потом выражение в скобках заменял на значение, а скобки убирал. В принципе, вполне рабочий способ для меня в то время.
Конечно, это не строка. Довольно очевидно, что математическая формула — это либо дерево, либо стек, и здесь мы остановимся на первом. То есть каждая нода, каждый узел этого дерева, это какая-то операция, переменная, либо константа.
Операция — это либо функция, либо оператор, в принципе, примерно одно и то же. Ее дети — аргументы функции (оператора).
Иерархия классов в вашем коде
Разумеется, реализация может быть любой. Однако идея в том, что если ваше дерево состоит только из узлов и листьев, то они бывают разными. Поэтому я называю эти «штуки» — сущностями. Поэтому верхним классом у нас будет абстрактный класс Entity.
Абстрактный?
Как все знают из базового изучения языка, абстрактный класс хорош тем, что с одной стороны обобщает какие-то классы, с другой стороны позволяет разделить логику и поведение некоторых объектов. Объект абстрактного класса нельзя создать, а вот его наследника — можно.
А также будет четыре класса-наследника: NumberEntity, VariableEntity, OperatorEntity, FunctionEntity.
Как построить выражение?
Для начала мы будем строить выражение в коде, то есть
var x = new VariableEntity("x"); var expr = x * x + 3 * x + 12;
Если объявить пустой класс VariableEntity, то такой код выкинет вам ошибку, мол не знает как умножать и суммировать.
Переопределение операторов
Очень важная и полезная фича большинства языков, позволяя кастомизировать выполнение арифметических операций. Синтаксически реализуется по-разному в зависимости от языка. Например, реализация в C#
public static YourClass operator +(YourClass a, YourClass b)
(Не)явное приведение типов
В компилируемых языках типа C# такая штука обычно присутствует и позволяет без дополнительного вызова myvar.ToAnotherType() привести тип, если необходимо. Так, например, было бы удобно писать
NumberEntity myvar = 3;
NumberEntity myvar = new NumberEntity(3);
Подвешивание
Класс Entity имеет поле Children — это просто список Entity, которые являются аргументами для данной сущности.
Вообще-то детей могут иметь объекты лишь двух классов: OperatorEntity и FunctionEntity. То есть в принципе можно было бы создать какой-нибудь NodeEntity и у него унаследовать эти два класса, и создать LeafEntity и от него унаследовать VariableEntity и NumberEntity.
Когда у нас вызывается функция или оператор, нам стоит создать новую сущность, и в ее дети положить то, от чего вызывается функция или оператор. К примеру, сумма по идее должна выглядить примерно так:
public static Entity operator +(Entity a, Entity b)
То есть теперь если у нас есть сущность x и сущность 3, то x+3 вернет сущность оператора суммы с двумя детьми: 3 и x. Так, мы можем строить деревья выражений.
Вызов функции более простой и не такой красивый, как с оператором:
public Entity Sin(Entity a)
Подвешивание в репе реализовано тут.
Отлично, мы составили дерево выражений.
Подстановка переменной
Здесь все предельно просто. У нас есть Entity — мы проверяем является ли он сам переменной, если да, возвращаем значение, иначе — бежим по детям.
В этом огромном 48-строчном файле реализована столь сложная функция.
Вычисление значения
Собственно то, ради чего все это. Здесь мы по идее должны добавить в Entity какой-то такой метод
public Entity Eval() < if (IsLeaf) < return this; >else return MathFunctions.InvokeEval(Name, Children); >
Листик без изменений, а для всего остального у нас кастомное вычисление. Опять же, приведу лишь пример:
public static Entity Eval(List args)
Если аргумент — число, то произведем численную функцию, иначе — вернем как было.
Number?
Это самая простая единица, число. Над ним можно проводить арифметические операции. По умолчанию оно комплексное. Также у него определены такие операции как Sin, Cos, и некоторые другие.
Если интересно, Number описан тут.
Производная
Численно производную посчитать может кто угодно, и такая функция пишется поистине в одну строку:
public double Derivative(Func f, double x) => (f(x + 1.0e-5) - f(x)) * 1.0e+5;
Но разумеется нам хочется аналитическую производную. Так как у нас уже есть дерево выражений, мы можем рекурсивно заменить каждый узел в соответствии с правилом дифференциирования. Работать оно должно примерно так:
Вот, к примеру, как реализованна сумма в моем коде:
public static Entity Derive(List args, VariableEntity variable)
А вот произведение
public static Entity Derive(List args, VariableEntity variable)
А вот сам по себе обход:
public Entity Derive(VariableEntity x) < if (IsLeaf) < if (this is VariableEntity && this.Name == x.Name) return new NumberEntity(1); else return new NumberEntity(0); >else return MathFunctions.InvokeDerive(Name, Children, x); >
Это метод Entity. И как видим, что у листа всего два состояния — либо это переменная, по которой мы дифференциируем, тогда ее производная равна 1, либо это константа (число либо VariableEntity), тогда ее производная 0, либо узел, тогда идет отсылка по имени (InvokeDerive обращается к словарю функций, где и находится нужная (например сумма или синус)).
Заметьте, я здесь не оставляю что-то типа dy/dx и сразу говорю, что производная от переменной не по которой мы дифференциируем равна 0. А вот здесь сделано по-другому.
Все дифференциирование описано в одном файле, а больше и не надо.
Упрощение выражения. Паттерны
Упрощение выражения в общем случае в принципе нетривиально. Ну например, какое выражение проще: или ? Но мы придерживаемся каких-то представлений, и на основе них хотим сделать те правила, которые точно упрощают выражение.
Можно при каждом Eval писать, что если у нас сумма, а дети — произведения, то переберем четыре варианта, и если где-то что-то равно, вынесем множитель… Но так делать конечно же не хочется. Поэтому можно догадаться до системы правил и паттернов. Итак, что мы хотим? Примерно такой синтаксис:
< any1 / (any2 / any3) ->any1 * any3 / any2 >, < const1 * var1 + const2 * var1 ->(const1 + const2) * var1 >, < any1 + any1 * any2 ->any1 * (Num(1) + any2) >,
Вот пример дерева, в котором нашлось поддерево (обведено в зеленый), отвечающее паттерну any1 + const1 * any1 (найденное any1 обведено в оранжевый).
Как видим, иногда нам важно, что одна и та же сущность должна повторяться, например чтобы сократить выражение x + a * x нам необходимо, чтобы и там и там был x, ведь x + a * y уже не сокращается. Поэтому нам нужно сделать алгоритм, который не только проверяет, что дерево соответсвует паттерну, но и
- Проверять, что одинаковые паттерновые Entity соответствуют одинаковым Entity.
- Записывать, что чему соответствует, чтобы потом подставить.
internal Dictionary EqFits(Entity tree) < var res = new Dictionary(); if (!tree.PatternMakeMatch(this, res)) return null; else return res; >
А в tree.PaternMakeMatch мы рекурсивно наполняем словарь ключами и их значениями. Вот пример списка самих паттерных Entity:
static readonly Pattern any1 = new Pattern(100, PatType.COMMON); static readonly Pattern any2 = new Pattern(101, PatType.COMMON); static readonly Pattern const1 = new Pattern(200, PatType.NUMBER); static readonly Pattern const2 = new Pattern(201, PatType.NUMBER); static readonly Pattern func1 = new Pattern(400, PatType.FUNCTION);
Когда мы будем писать any1 * const1 — func1 и так далее, у каждой ноды будет номер — это и есть ключ. Иначе говоря, при заполнении словаря, ключами выступят как раз эти номера: 100, 101, 200, 201, 400… А при постройке дерева мы будем смотреть на значение, соответствующее ключу, и подставлять его.
Упрощение. Сортировка дерева
В статье, к которой я уже обращался, автор решил сделать просто, и отсортировал практически по хешу дерева. Ему удалось сократить a и -a, b + c + b превратить 2b + c. Но мы, конечно, хотим и чтобы (x + y) + x * y — 3 * x сокращалось, и в целом более сложные штуки.
Паттерны не работают?
Вообще, то, что мы сделали до этого, паттерны — чудовищно замечательная штука. Она позволит вам сокращать и разность квадратов, и сумму квадрата синуса и косинуса, и другие сложные штуки. Но элементарную пальму, ((((x + 1) + 1) + 1) + 1), она не сократит, ведь здесь главное правило — коммутативность слагаемых. Поэтому первый шаг — вычленить «линейных детей».
«Линейные дети»
Собственно для каждой ноды суммы или разности (и, кстати, произведения/деления) мы хотим получить список слагаемых (множителей).
Это в принципе несложно. Пусть функция LinearChildren(Entity node) возвращает список, тогда мы смотрим на child in node.Children: если child — это не сумма, то result.Add(child), иначе — result.AddRange(LinearChildren(child)).
Не самым красивым образом реализовано тут.
Группировка детей
Итак, у нас есть список детей, но что дальше? Допустим, у нас есть sin(x) + x + y + sin(x) + 2 * x. Очевидно, что наш алгоритм получит пять слагаемых. Далее мы хотим сгруппировать по похожести, например, x похож на 2 * x больше, чем на sin(x).
Вот хорошая группировка:
Так как в ней паттерны дальше справятся с преобразованием 2*x + x в 3*x.
То есть мы сначала группируем по некоторому хешу, а затем делаем MultiHang — преобразование n-арного суммирования в бираное.
Хеш узла
С одной стороны, и следует поместить в одну группу. С другой стороны, при наличии помещать в одну группу с бессмысленно.
Если подумать, то . Хотя мне кажется, это практически не проще, и уж точно не нужно. Да и вообще, упрощение — вещь ни разу неочевидная, и уж это точно не первое, что стоит писать при написании «калькулятора».
Поэтому мы реализовываем многоуровневую сортировку. Сначала мы делаем вид, что — одно и то же. Посортировали, успокоились. Потом делаем вид, что можно помещать только с другими . И вот уже наши и наконец объединились. Реализовано достаточно просто:
internal string Hash(SortLevel level)
Как видим, функция по-любому влияет на сортировку (разумеется, ведь с вообще никак в общем случае не связана). Как и переменная, с ну никак не получится смешать. А вот константы и операторы учитываются не на всех уровнях. В таком порядке идет сам процесс упрощения
public Entity Simplify(int level) < // Сначала мы делаем самую простую симплификацю: вычисление значений там, где это возможно, умножение на ноль и т. д. var stage1 = this.InnerSimplify(); Entity res = stage1; for (int i = 0; i < level; i++) < // Этот блок ответственнен за сортировку. Сначала мы группируем что-то типа x и x+1 (переменные и функции), затем что-то типа x-1 и x+1 (переменные, функции и константы), затем что-то типа x+1 и x+1 (учитывается все). switch (i) < case 0: res = res.Sort(SortLevel.HIGH_LEVEL); break; case 2: res = res.Sort(SortLevel.MIDDLE_LEVEL); break; case 4: res = res.Sort(SortLevel.LOW_LEVEL); break; >// Здесь мы заменяем паттерны. res = TreeAnalyzer.Replace(Patterns.CommonRules, res).InnerSimplify(); > return res; >
Самая ли это лучшая реализация? Пихните в личные сообщения, может быть будут идеи получше. Я долго думал, как сделать это макимально красиво, хотя по моему мнению, до «красиво» здесь далеко.
«Компиляция» функций
В кавычках — так как не в сам IL код, а лишь в очень быстрый набор инструкций. Но зато очень просто.
Проблема Substitute
Чтобы посчитать значение функции, нам достаточно вызвать подстановку переменной и eval, например
var x = MathS.Var("x"); var expr = x * x + 3; var result = expr.Substitute(x, 5).Eval();
Но это работает медленно, около 1.5 микросекунды на синус.
Инструкции
Чтобы ускорить вычисление, мы делаем вычисление функции на стеке, а именно:
1) Придумываем класс FastExpression, у которого будет список инструкций
2) При компиляции инструкции складываются в стек в обратном порядке, то есть если есть функция x * x + sin(x) + 3, то инструкции будут примерно такими:
PUSHVAR 0 // Подстановка переменной номер 0 - x CALL 6 // Вызов функции номер 6 - синуса PUSHCONST 3 CALL 0 // Вызов функции номер 0 - суммы PUSHVAR 0 PUSHVAR 0 CALL 2 CALL 0
Далее при вызове мы прогоняем эти инструкции и возвращаем Number.
Пример выполнения инструкции суммы:
internal static void Sumf(Stack stack)
Вызов синуса сократился с 1500нс до 60нс (системный Complex.Sin работает за 30нс).
В репе реализовано тут.
Фух, вроде бы пока все. Хотя рассказать еще есть о чем, но мне кажется объем для одной статьи достаточный. Интересно ли кому-нибудь продолжение? А именно: парсинг из строки, форматирование в латех, определенный интеграл, и прочие плюшки.
Ссылка на репозиторий со всем кодом, а также тестами и самплами.
Вообще-то я продолжаю работать над этим проектом. Распространяется он под MIT (то есть делайте с ним что хотите), и он никогда не станет ни закрытым, ни коммерческим. Более того, если есть идеи для улучшения и вклада — pull-реквесты очень приветствуются.
Как сделать калькулятор в C++
Пример создания простого калькулятора на C++ для сложения, вычитания, умножения и деления с использованием операторов switch и break.
Эта программа принимает арифметический оператор (+, -, *, /) и два операнда от пользователя и выполняет операцию с этими двумя операндами в зависимости от оператора, введенного пользователем.
# include using namespace std; int main() < char op; float num1, num2; cout > op; cout > num1 >> num2; switch(op) < case '+': cout return 0; >
Enter operator either + or - or * or divide : - Enter two operands: 3.4 8.4 3.4 - 8.4 = -5.0
Эта программа принимает от пользователя оператор и два операнда.
Оператор хранится в переменной оп и два операнда хранятся в num1 и num2 соответственно. Затем оператор switch … case используется для проверки оператора, введенного пользователем. Если пользователь вводит +, то в калькуляторе выполняются операторы case: ‘+’ и программа завершается.
Если пользователь вводит -, то выполняются операторы для case: ‘-‘ и программа завершается.
