Русский
Русский
English
Статистика
Реклама

Recovery mode Формульный движок с обратной польской нотацией на JavaScript

Имеющиеся реализации расчетных движков на обратной польской нотации, которые можно найти в интернете, всем хороши, только вот не поддерживают функции, такие как round(), max(arg1; arg2, ) или if(условие; истина; ложь), что делает такие движки бесполезными с практической точки зрения. В статье представлена реализация формульного движка на обратной польской нотации, которые поддерживают различные формулы, написанного на чистом JavaScript в объектно-ориентированном стиле.

Следующий код демонстрирует возможности движка:
const formula = "if( 1; round(10,2); 2*10)";const formula = "round2(15.542 + 0.5)";const formula1 = "max(2*15; 10; 20)";const formula2 = "min(2; 10; 20)";const formula3 = "random()";const formula4 = "if ( max(0;10) ; 10*5 ; 15 ) ";const formula5 = "sum(2*15; 10; 20)";const calculator = new Calculator(null);console.log(formula+" = "+calculator.calc(formula));console.log(formula1+" = "+calculator.calc(formula1));console.log(formula2+" = "+calculator.calc(formula2));console.log(formula3+" = "+calculator.calc(formula3));console.log(formula4+" = "+calculator.calc(formula4));console.log(formula5+" = "+calculator.calc(formula5));

До начала описания архитектуры формульного движка необходимо сделать несколько замечаний:
  1. Объект Calculator в качестве аргумента может принимать источник данных ячеек электронных таблицы в виде Map, в котором ключом выступает имя ячейки в формате А1, а значением единичный токен или массив объектов токенов, на которые разбирается строка формул при ее создании. В данном примере в формулах не используются ячейки, поэтому источник данных указан как null.
  2. Функции пишутся в формате [имя_функции]([аргумент1]; [аргумент2]; ).
  3. Пробелы при написании формул не учитываются при разбиении строки формул на токены все пробельные символы предварительно удаляются.
  4. Десятичную часть числа можно разделять как точкой, так и запятой при разбиении строки формул на токены десятичная запятая преобразуется в точку.

Про саму польскую нотацию в интернете можно найти довольно много материалов, поэтому лучше сразу начать с описания кода. Сам исходный текст формульного движка размещен по адресу https://github.com/leossnet/bizcalc под лицензией MIT в разделе /js/data и включает в себя файлы calculator.js и token.js. Попробовать расчетчик сразу в деле можно по адресу bizcalc.ru.

Итак, начнем с типов токенов, которые сосредоточены в объекте Types:
const Types = {    Cell: "cell" ,    Number: "number" ,    Operator: "operator" ,    Function: "function",    LeftBracket: "left bracket" ,     RightBracket: "right bracket",    Semicolon: "semicolon",    Text: "text"};

По сравнению с типовыми реализациями движков добавлены следующие типы:
  • Cell: cell имя ячейки электронной таблицы, которая может содержать текст, число или формулу;
  • Function: function функция;
  • Semicolon: semicolon разделитель аргументов функции, в данном случае ;;
  • Text: text текст, который игнорируется расчетным движком.

Как и в любом другом движке реализована поддержка пяти основных операторов:
const Operators = {    ["+"]: { priority: 1, calc: (a, b) => a + b },  // сложение    ["-"]: { priority: 1, calc: (a, b) => a - b },  //вычитание    ["*"]: { priority: 2, calc: (a, b) => a * b },  // умножение    ["/"]: { priority: 2, calc: (a, b) => a / b },  // деление    ["^"]: { priority: 3, calc: (a, b) => Math.pow(a, b) }, // возведение в степень};

Для тестирования движка были реализованы следующие функции (список функций может быть расширен):
const Functions = {    ["random"]: {priority: 4, calc: () => Math.random() }, // случайное число    ["round"]:  {priority: 4, calc: (a) => Math.round(a) },  // округление до целого    ["round1"]: {priority: 4, calc: (a) => Math.round(a * 10) / 10 },    ["round2"]: {priority: 4, calc: (a) => Math.round(a * 100) / 100 },    ["round3"]: {priority: 4, calc: (a) => Math.round(a * 1000) / 1000 },    ["round4"]: {priority: 4, calc: (a) => Math.round(a * 10000) / 10000 },    ["sum"]:    {priority: 4, calc: (...args) => args.reduce( (sum, current) => sum + current, 0) },    ["min"]:    {priority: 4, calc: (...args) => Math.min(...args) },     ["max"]:    {priority: 4, calc: (...args) => Math.max(...args) },    ["if"]:     {priority: 4, calc: (...args) => args[0] ? args[1] : (args[2] ? args[2] : 0) }};

Думаю, что приведенный код говорит сам за себя. Далее рассмотрим код класса токена:

class Token {    static separators = Object.keys(Operators).join("")+"();"; // запоминает строку разделителей вида "+-*/^();""    static sepPattern = `[${Token.escape(Token.separators)}]`; // формирует шаблон разделитетей вида "[\+\-\*\/\^\(\)]"    static funcPattern = new RegExp(`${Object.keys(Functions).join("|").toLowerCase()}`, "g");    #type;    #value;    #calc;    #priority;    /**     * Конструктор токена, которому передаются в качестве аргументов тип и значение токена,      * а прочие параметры устанавливаются в зависимости от типа     */    constructor(type, value){        this.#type = type;        this.#value = value;        if ( type === Types.Operator ) {            this.#calc = Operators[value].calc;            this.#priority = Operators[value].priority;        }        else if ( type === Types.Function ) {            this.#calc = Functions[value].calc;            this.#priority = Functions[value].priority;        }    }    /**     * Реализация геттеров для приватных полей класса     */    /**     * Разбирает формулу на токены      * @param {String} formula - строка с формулой     */    static getTokens(formula){        let tokens = [];        let tokenCodes = formula.replace(/\s+/g, "") // очистка от пробельных символов            .replace(/(?<=\d+),(?=\d+)/g, ".") // заменяет запятую на точку (для чисел)            .replace(/^\-/g, "0-") // подставляет отсутсующий 0 для знака "-" в начале строки            .replace(/\(\-/g, "(0-") // подставляет отсутсующий 0 для знака "-" в середине строки            .replace(new RegExp (Token.sepPattern, "g"), "&$&&") // вставка знака & перед разделителями            .split("&")  // разбиение на токены по символу &            .filter(item => item != ""); // удаление из массива пустых элементов                tokenCodes.forEach(function (tokenCode){            if ( tokenCode in Operators )                 tokens.push( new Token ( Types.Operator, tokenCode ));            else if ( tokenCode === "(" )                  tokens.push ( new Token ( Types.LeftBracket, tokenCode ));            else if ( tokenCode === ")" )                 tokens.push ( new Token ( Types.RightBracket, tokenCode ));            else if ( tokenCode === ";" )                 tokens.push ( new Token ( Types.Semicolon, tokenCode ));            else if ( tokenCode.toLowerCase().match( Token.funcPattern ) !== null  )                tokens.push ( new Token ( Types.Function, tokenCode.toLowerCase() ));            else if ( tokenCode.match(/^\d+[.]?\d*/g) !== null )                 tokens.push ( new Token ( Types.Number, Number(tokenCode) ));             else if ( tokenCode.match(/^[A-Z]+[1-9]+/g) !== null )                tokens.push ( new Token ( Types.Cell, tokenCode ));        });        return tokens;    }    /**     * Экранирование обратным слешем специальных символов     * @param {String} str      */        static escape(str) {        return str.replace(/[-\/\\^$*+?.()|[\]{}]/g, '\\$&');}    }

Класс Token представляет собой контейнер для хранения неделимых текстовых единиц, на которые разбивается строка формул, каждый из которых несет определенную функциональность.

Конструктор класса Token в качестве аргумента принимает тип токена из полей объекта Types, а в качестве значения неделимую текстовую единицу, выделенную из формульную строки.
Внутренние приватные поля класса Token, хранящие значение приоритета и вычисляемого выражения, определяются в конструкторе на основании значений объектов Operators и Functions.

В качестве вспомогательного метода реализована статическая функция escape(str), код который взят из первой найденной страницы в интернете, экранирующая символы, которые объект RegExp воспринимает как специальные.

Самый важный метод в классе Token это статическая функция getTokens, которая разбирает строку формул и возвращает массив объектов Token. В методе реализована небольшая хитрость перед разбиением на токены предварительно к разделителям (операторам и круглым скобкам) добавляется символ &, который не используется в формулах, и только затем происходит разбиение по символу &.

Сама реализация метода getTokens представляет собой сравнение в цикле всех полученных токенов с шаблонами, определение типа токена, создание объекта класса Token и добавление его в результирующий массив.

На этом предварительная работа по подготовке вычислений завершается. Следующим этапом следуют сами вычисления, которые реализованы в классе Calculator:
class Calculator {    #tdata;    /**     * Конструктор калькулятора     * @param {Map} cells хеш ячеек, содержащих формулы или первичные значения     */    constructor(tableData) {        this.#tdata = tableData;    }    /**     * Расчет значения для формулы     * @param {Array|String} formula - массив токенов или формула строки     */    calc(formula){        let tokens = Array.isArray(formula) ? formula : Token.getTokens(formula);        let operators = [];        let operands = [];        let funcs = [];        let params = new Map();        tokens.forEach( token => {            switch(token.type) {                case Types.Number :                     operands.push(token);                    break;                case Types.Cell :                    if ( this.#tdata.isNumber(token.value) ) {                        operands.push(this.#tdata.getNumberToken(token));                    }                    else if ( this.#tdata.isFormula(token.value) ) {                        let formula = this.#tdata.getTokens(token.value);                        operands.push(new Token(Types.Number, this.calc(formula)));                    }                    else {                        operands.push(new Token(Types.Number, 0));                    }                    break;                case Types.Function :                    funcs.push(token);                    params.set(token, []);                    operators.push(token);                                 break;                case Types.Semicolon :                    this.calcExpression(operands, operators, 1);                    // получить имя функции из стека операторов                    let funcToken = operators[operators.length-2];                      // извлечь из стека последний операнд и добавить его в параметы функции                    params.get(funcToken).push(operands.pop());                        break;                case Types.Operator :                    this.calcExpression(operands, operators, token.priority);                    operators.push(token);                    break;                case Types.LeftBracket :                    operators.push(token);                    break;                case Types.RightBracket :                    this.calcExpression(operands, operators, 1);                    operators.pop();                    // если последний оператор в стеке является функцией                    if (operators.length && operators[operators.length-1].type == Types.Function ) {                        // получить имя функции из стека операторов                        let funcToken = operators.pop();                                // получить массив токенов аргументов функции                        let funcArgs = params.get(funcToken);                           let paramValues = [];                        if ( operands.length ) {                            // добавить последний аргумент функции                            funcArgs.push(operands.pop());                                 // получить массив значений всех аргументов функции                            paramValues = funcArgs.map( item => item.value );                         }                        // вычислить значение функции и положить в стек операндов                        operands.push(this.calcFunction(funcToken.calc, ...paramValues));                      }                    break;            }        });        this.calcExpression(operands, operators, 0);        return operands.pop().value;     }    /**     * Вычисление подвыражения внутри (без) скобок     * @param {Array} operands массив операндов     * @param {Array} operators массив операторов      * @param {Number} minPriority минимальный приоритет для вычисления выражения     */    calcExpression (operands, operators, minPriority) {        while ( operators.length && ( operators[operators.length-1].priority ) >= minPriority ) {            let rightOperand = operands.pop().value;            let leftOperand = operands.pop().value;            let operator = operators.pop();            let result = operator.calc(leftOperand, rightOperand);            if ( isNaN(result) || !isFinite(result) ) result = 0;            operands.push(new Token ( Types.Number, result ));        }    }    /**     * Вычисление значений функции     * @param {T} func - функция обработки аргументов     * @param  {...Number} params - массив числовых значений аргументов     */    calcFunction(calc, ...params) {        return new Token(Types.Number, calc(...params));    }}

Как и в обычном формульном движке все вычисления выполняется в основной функции calc(formula), где в качестве аргумента передается либо строка формул, либо уже готовый массив токенов. Если методу calc передается формульная строка, то она предварительно преобразуется в массив токенов.

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

В качестве расширения обычного формульного движка реализована довольно простая функция calcFunction, которая принимает в качестве аргументов имя функции, а также произвольное число аргументов этой функции. Функция calcFunction вычисляет значение функции формулы и возвращает новый объект класса Token с числовым типом.

Для вычисления функций в рамках общего чикла вычислений к стекам операндов и операторов добавлены стек функций и Map для аргументов функции, в котором ключом выступает имя функции, а значениями массив аргументов.

На этом все. Спасибо за внимание.
Источник: habr.com
К списку статей
Опубликовано: 26.07.2020 16:05:43
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Javascript

Excel

Категории

Последние комментарии

© 2006-2021, personeltest.ru