Парсим математические выражения на чистом Javascript. Часть 2: вычисление выражения в обратной польской записи

javascript, math expression parsing, reverse polish notation
Парсим математические выражения на чистом Javascript. Часть 2: вычисление выражения в обратной польской записи

Цикл статей о создании собственного парсера выражений: от токенизации до полноценного синтаксического разбора.

Оглавление цикла

В предыдущей части мы научились превращать строку с математическим выражением в последовательность токенов – чисел, операторов, скобок, функций и других элементов. Но токены сами по себе ничего не вычисляют. Чтобы получить результат, их нужно обработать, и сделать это можно по-разному.

В этой части мы познакомимся с обратной польской записью (Reverse Polish Notation, RPN) – универсальным представлением выражения, которое не требует скобок и знания приоритетов операций и реализуем калькулятор, вычисляющий выражения, записанные в этом представлении. Такой формат идеально подходит для вычисления выражений с произвольной структурой и глубиной.

Что такое польская и обратная польская запись?

В привычной записи (её называют инфиксной) операторы располагаются между операндами: 3 + 4, a * (b + c), x ^ y.

Однако такая запись требует скобок и таблицы приоритетов, чтобы интерпретировать выражение корректно. Именно из-за этого реализация собственного калькулятора или парсера становится нетривиальной задачей.

В 1920-х годах польский логик Ян Лукасевич предложил запись, в которой операторы располагаются перед операндами. Она и получила название польская запись (префиксная):

Выражения в префиксной форме
+ 3 4     // вместо 3 + 4
* + 1 2 3 // вместо (1 + 2) * 3

Позже появилась обратная польская запись (ОПЗ, постфиксная), в которой оператор стоит после операндов. Именно она и используется чаще всего на практике:

Выражения в постфиксной форме
3 4 +     // вместо 3 + 4
1 2 + 3 * // вместо (1 + 2) * 3

Главное преимущество RPN заключается в том, что её можно вычислять без скобок и приоритетов, используя всего лишь стек.

Алгоритм вычисления выражения в ОПЗ

Корректное выражение, записанное в постфиксной форме, вычисляется следующим образом:

  1. Создаём пустой стек;
  2. Идём по списку токенов от первого к последнему;
    • Если токен является числом, константой или переменной – кладём его значение в стек;
    • Если токен является операцией или функцией – достаём из стека нужное количество аргументов, вычисляем результат и кладём его обратно в стек (важно: аргументы в стеке идут в обратном порядке);
  3. После обработки всех токенов в стеке должно остаться одно число – оно и является значением выражения.

Разберём на примере

Рассмотрим выражение, записанное в привычной форме:

Выражение в инфиксной форме
3 + 4 * 8 / (5 - 3)^2^3

Чтобы корректно его вычислить, требуется знать:

  • порядок выполнения операций;
  • ассоциативность (правая или левая);
  • скобочную структуру.

Но в обратной польской записи всё упрощается. Это же выражение запишется так:

Выражение в обратной польской записи
3 4 8 * 5 3 - 2 3 ^ ^ / +

Теперь вычислим его пошагово:

шаг токен действие стек
1 "3" кладём 3 в стек [3]
2 "4" кладём 4 в стек [3, 4]
3 "8" кладём 8 в стек [3, 4, 8]
4 "*" достаём из стека 8 [3, 4]
достаём из стека 4 [3]
вычисляем 4 * 8 и кладём 32 в стек [3, 32]
5 "5" кладём 5 в стек [3, 32, 5]
6 "3" кладём 3 в стек [3, 32, 5, 3]
7 "-" достаём из стека 3 [3, 32, 5]
достаём из стека 5 [3, 32]
вычисляем 5 - 3 и кладём 2 в стек [3, 32, 2]
8 "2" кладём 2 в стек [3, 32, 2, 2]
9 "3" кладём 3 в стек [3, 32, 2, 2, 3]
10 "^" достаём из стека 3 [3, 32, 2, 2]
достаём из стека 2 [3, 32, 2]
вычисляем 2 ^ 3 и кладём 8 в стек [3, 32, 2, 8]
11 "^" достаём из стека 8 [3, 32, 2]
достаём из стека 2 [3, 32]
вычисляем 2 ^ 8 и кладём 256 в стек [3, 32, 256]
12 "/" достаём из стека 256 [3, 32]
достаём из стека 32 [3]
вычисляем 32 / 256 и кладём 0.125 в стек [3, 0.125]
13 "+" достаём из стека 0.125 [3]
достаём из стека 3 []
вычисляем 3 + 0.125 и кладём 3.125 в стек [3.125]

Итоговый ответ: 3.125.

Такой подход легко реализуется программно, если всё выражение уже представлено в виде массива токенов в RPN. Далее мы создадим калькулятор, который будет выполнять именно эти шаги и поддерживать:

  • любые унарные и бинарные операторы;
  • функции (sin, max, и др.);
  • константы (pi, e);
  • обработку возможных ошибок.

Реализация калькулятора

Создадим файл expression_evaluator.js с классом ExpressionEvaluator. Для удобства в конструкторе будем принимать следующие параметры:

  • functions – словарь с поддерживаемыми функциями, в котором ключами будут имена функций, а значениями – их параметры: количество аргументов args и функция вычисления evaluate);
  • constants – словарь с поддерживаемыми константами;
  • operators – словарь с поддерживаемыми операторами, в котором ключами будут сами операторы, а значениями их параметры: количество аргументов args и функция для вычисления evaluate.
Заготовка калькулятора
class ExpressionEvaluator {
    constructor({functions, constants, operators}) {
        this.functions = functions
        this.constants = constants
        this.operators = operators
    }
}

Все вычисления будем проводить в методе evaluate, принимающим два аргумента:

  • rpn – выражение в постфиксной форме в виде массива токенов (которые выдаёт токенизатор);
  • variables – словарь, в котором ключами будут имена переменных, а значениями – значения этих переменных.

Реализуем в этом методе описанный выше алгоритм:

Вычисление значения выражения
evaluate({rpn, variables = {}}) {
    const stack = []

    for (const token of rpn) {
        if (token.type === "number") {
            stack.push(parseFloat(token.value))
        }
        else if (token.type === "constant") {
            stack.push(this.constants[token.value])
        }
        else if (token.type === "variable") {
            stack.push(variables[token.value])
        }
        else if (token.type === "operator") {
            const operator = this.operators[token.value]
            const args = stack.splice(-operator.args)
            stack.push(operator.evaluate(...args))
        }
        else if (token.type === "function") {
            const func = this.functions[token.value]
            const args = stack.splice(-func.args)
            stack.push(func.evaluate(...args))
        }
    }

    return stack[0]
}

Уже сейчас наш калькулятор способен вычислять корректные выражения. Убедимся в этом сами:

Проверяем калькулятор
// поддерживаемые функции
const functions = {
    "sin": {args: 1, evaluate: Math.sin},
    "max": {args: 2, evaluate: Math.max}
}

// поддерживаемые константы
const constants = {
    "pi": Math.PI,
    "e": Math.E
}

// поддерживаемые операции
const operators = {
    "+": {args: 2, evaluate: (arg1, arg2) => arg1 + arg2},
    "-": {args: 2, evaluate: (arg1, arg2) => arg1 - arg2},
    "*": {args: 2, evaluate: (arg1, arg2) => arg1 * arg2},
    "/": {args: 2, evaluate: (arg1, arg2) => arg1 / arg2},
    "^": {args: 2, evaluate: (arg1, arg2) => arg1 ** arg2},
    "~": {args: 1, evaluate: arg => -arg}, // унарный минус
}

// используем токенизатор из прошлой статьи
const tokenizer = new ExpressionTokenizer({
    functions: Object.keys(functions),
    constants: Object.keys(constants)
})

const tokens = tokenizer.tokenize("3 4 8 * 5 3 - 2 3 ^ ^ / +")

// создаём наш калькулятор
const evaluator = new ExpressionEvaluator({
    constants: constants,
    functions: functions,
    operators: operators
})

const result = evaluator.evaluate({rpn: tokens}) // 3.125

Обработка ошибок

Но что произойдёт, если мы подадим калькулятору выражение 1 + или 5 x ^? Строго говоря, калькулятор всё равно получит ответ (который почти наверняка будет или NaN или undefined, но это совсем не то, чего нам хотелось бы от калькулятора. Давайте рассмотрим, какие могут быть некорректные случаи:

  • обрабатываемого оператора, функции или константы может не оказаться в списках допустимых;
  • при обработке операторов и функций в стеке может не оказаться нужного количества аргументов;
  • при обработке переменной может не оказаться установленного значения;
  • в качестве токена может прийти что-то ещё помимо обрабатываемых алгоритмом сейчас;
  • в конце работы стек может оказаться пуст или в стеке может находиться более одного значения.

Обработаем эти ситуации, дополнительно вынеся обработку операторов, функций и переменных в соответствующие функции:

Вычисление значения с проверкой корректности
evaluate({rpn, variables = {}}) {
    const stack = []

    for (const token of rpn) {
        if (token.type === "number") {
            stack.push(parseFloat(token.value))
        }
        else if (token.type === "constant") {
            this.evaluateConstant(token, stack)
        }
        else if (token.type === "variable") {
            this.evaluateVariable(token, stack, variables)
        }
        else if (token.type === "operator") {
            this.evaluateOperator(token, stack)
        }
        else if (token.type === "function") {
            this.evaluateFunction(token, stack)
        }
        else
            throw new Error(`got invalid token "${token.value}" (${token.start}:${token.end})`)
    }

    if (stack.length != 1)
        throw new Error("expression is invalid")

    return stack[0]
}

// обработка константы
evaluateConstant(token, stack) {
    if (!(token.value in this.constants))
        throw new Error(`got unknown constant "${token.value}" (${token.start}:${token.end})`)

    stack.push(this.constants[token.value])
}

// обработка переменной
evaluateVariable(token, stack, variables) {
    if (!(token.value in variables))
        throw new Error(`variable "${token.value}" value is not set`)

    stack.push(variables[token.value])
}

// обработка операции
evaluateOperator(token, stack) {
    const operator = this.operators[token.value]

    if (!operator)
        throw new Error(`got unknown operator "${token.value}" (${token.start}:${token.end})`)

    if (stack.length < operator.args)
        throw new Error(`not enough arguments to evaluate operator "${token.value}" (${token.start}:${token.end})`)

    const args = stack.splice(-operator.args)
    stack.push(operator.evaluate(...args))
}

// обработка функции
evaluateFunction(token, stack) {
    const func = this.functions[token.value]

    if (!func)
        throw new Error(`got unknown function "${token.value}" (${token.start}:${token.end})`)

    if (stack.length < func.args)
        throw new Error(`not enough arguments to evaluate function "${token.value}" (${token.start}:${token.end})`)

    const args = stack.splice(-func.args)
    stack.push(func.evaluate(...args))
}

Теперь при попытке посчитать некорректное выражение калькулятор будет бросать соответствующее исключение.

А что это за операция ~?

Внимательные читатели могли заметить, что среди бинарных операций появилась какая-то унарная с токеном ~. Такой токен, получить от токенизатора просто невозможно, но так и должно быть. В обратной польской нотации нам нужно как-то отличать унарный минус от операции вычитания. Кроме как завести под инверсию специальный токен мы больше ничего и не можем. Однако это нам понадобится в будущем, когда мы будет реализовывать парсер, переводящий выражение из инфиксной формы в постфиксную. Именно он будет определять, чем является операция - и в случае чего подменять выходной токен для RPN.

При этом нам ничего не мешает самостоятельно сформировать токены выражения (в конце концов токенизатор мы сейчас использовали просто для удобства) и вычислить его:

Проверяем унарный минус
// токены, представляющие выражение 5 * -7
const rpn = [
    {"type": "number", "value": "5"},
    {"type": "number", "value": "7"},
    {"type": "operator", "value": "~"},
    {"type": "operator", "value": "*"}
]

const evaluator = new ExpressionEvaluator({
    constants: constants,
    functions: functions,
    operators: operators
})

const result = evaluator.evaluate({rpn: rpn}) // -35

Заключение

В этой статье всего в каких-то 88 строках мы реализовали полноценный калькулятор выражений в обратной польской записи – надёжный и расширяемый инструмент, который станет фундаментом для следующих частей цикла. Благодаря стековой природе RPN мы смогли обойтись без учёта приоритетов операций и скобок, а значит – упростили вычисление до последовательного применения операций и функций.

В следующих статьях мы научимся преобразовывать привычные математические выражения в польскую запись. Начнём с классического алгоритма сортировочной станции, а затем постепенно перейдём к более гибким и мощным парсерам.

Итоговый файл expression_evaluator.js
class ExpressionEvaluator {
    constructor({functions, constants, operators}) {
        this.functions = functions
        this.constants = constants
        this.operators = operators
    }

    evaluate({rpn, variables = {}}) {
        const stack = []

        for (const token of rpn) {
            if (token.type === "number") {
                stack.push(parseFloat(token.value))
            }
            else if (token.type === "constant") {
                this.evaluateConstant(token, stack)
            }
            else if (token.type === "variable") {
                this.evaluateVariable(token, stack, variables)
            }
            else if (token.type === "operator") {
                this.evaluateOperator(token, stack)
            }
            else if (token.type === "function") {
                this.evaluateFunction(token, stack)
            }
            else
                throw new Error(`got invalid token "${token.value}" (${token.start}:${token.end})`)
        }

        if (stack.length != 1)
            throw new Error("expression is invalid")

        return stack[0]
    }

    evaluateConstant(token, stack) {
        if (!(token.value in this.constants))
            throw new Error(`got unknown constant "${token.value}" (${token.start}:${token.end})`)

        stack.push(this.constants[token.value])
    }

    evaluateVariable(token, stack, variables) {
        if (!(token.value in variables))
            throw new Error(`variable "${token.value}" value is not set`)

        stack.push(variables[token.value])
    }

    evaluateOperator(token, stack) {
        const operator = this.operators[token.value]

        if (!operator)
            throw new Error(`got unknown operator "${token.value}" (${token.start}:${token.end})`)

        if (stack.length < operator.args)
            throw new Error(`not enough arguments to evaluate operator "${token.value}" (${token.start}:${token.end})`)

        const args = stack.splice(-operator.args)
        stack.push(operator.evaluate(...args))
    }

    evaluateFunction(token, stack) {
        const func = this.functions[token.value]

        if (!func)
            throw new Error(`got unknown function "${token.value}" (${token.start}:${token.end})`)

        if (stack.length < func.args)
            throw new Error(`not enough arguments to evaluate function "${token.value}" (${token.start}:${token.end})`)

        const args = stack.splice(-func.args)
        stack.push(func.evaluate(...args))
    }
}

Часть 1. Токенизация

Часть 3. Алгоритм сортировочной станции