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

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

Следующий код демонстрирует возможности движка:

const formula = "if( 1; round(10,2); 2*10)";
const formula1 = "round2(15.542 + 0.5)";
const formula2 = "max(2*15; 10; 20)";
const formula3 = "min(2; 10; 20)";
const formula4 = "round4(random()*10)";
const formula5 = "if ( max(0;10) ; 10*5 ; 15 ) ";
const formula6 = "sum(2*15; 10; 20)";

const calculator = new Calculator(null);
console.log(formula+" = "+calculator.calc(formula));    // if( 1; round(10,2); 2*10) = 10
console.log(formula1+" = "+calculator.calc(formula1));  // round2(15.542 + 0.5) = 16.04
console.log(formula2+" = "+calculator.calc(formula2));  // max(2*15; 10; 20) = 30 
console.log(formula3+" = "+calculator.calc(formula3));  // min(2; 10; 20) = 2
console.log(formula4+" = "+calculator.calc(formula4));  // round4(random()*10) = 5.8235
console.log(formula5+" = "+calculator.calc(formula5));  // if ( max(0;10) ; 10*5 ; 15 )  = 50
console.log(formula6+" = "+calculator.calc(formula6));  // sum(2*15; 10; 20) = 60

До начала описания архитектуры формульного движка необходимо сделать несколько замечаний:

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

Про саму польскую нотацию в интернете можно найти довольно много материалов, поэтому лучше сразу начать с описания кода. Сам исходный текст формульного движка размещен по адресу 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)}]`; 
    // шаблон функций вида "random|round|...|sum|min|max|if"
    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]+[0-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 для аргументов функции, в котором ключом выступает имя функции, а значениями – массив аргументов.

В заключении приведу пример, как можно использовать источник данных в виде хеша ячеек и их значений. Для начала определяется класс, реализующий интерфейс, который используется расчетчиком:

class Data {
    #map;
    // конструктор класса
    constructor() {
        this.#map = new Map();
    }
    // добавление ячейки и ее значения 
    add(cellName, number) {
        this.#map.set(cellName, number);
    }
    // проверка, что значение ячейки является числом, используется в Calculator.calc()
    isNumber(cellName) {
        return true;
    }
    // получение токена числового типа, используется в Calculator.calc()
    getNumberToken (token) {
        return new Token (Types.Number, this.#map.get(token.value) );
    }
}

Ну а затем все просто. Создаем источник данных, содержащий значения ячеек. Затем определяем формулу, в которой операнды представляют собой ссылки на ячейки. И в заключении производим вычисления:

let data = new Data();
data.add("A1", 1);
data.add("A2", 1.5);
data.add("A3", 2);

let formula = "round1((A1+A2)^A3)";
let calculator = new Calculator(data);

console.log(formula+" = "+calculator.calc(formula));  // round1((A1+A2)^A3) = 6.3

Спасибо за внимание.