Токенизатор математических выражений на JavaScript

0
3980
Добавить в избранное

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

Токенизатор математических выражений на JavaScript

Что такое токенизатор?

Токенизатор – это программа, которая разбивает исходное выражение на отдельные части – лексические единицы, лексемы, или токены. Для примера возьмем выражение «I’m a big fat developer». Его можно токенизировать несколькими способами:

Например, используя в качестве токенов отдельные слова:

Или непробельные символы:

Или вообще все символы:

Ну, идею вы поняли, правда?

Токенизаторы, или лексеры, лексические анализаторы, используются в разработке компиляторов различных языков программирования. Они помогают машине понять, что вы хотели сказать своим кодом.

Вместо кода мы будем работать с математическими выражениями, это почти то же самое.

Токены

Допустимое математическое выражение состоит из математически допустимых токенов, которые могут быть Литералами, Переменными, Операторами, Функциями или Разделителями Аргументов Функции.

  • Литерал в нашем случае – это просто число. Оно может быть целое или десятичное.
  • К Переменным мы давно привыкли в математике и программировании. В этом проекте они будут иметь самые простые однобуквенные имена, например, a, b, m, n, x, y. Таким образом, мы сможем токенизировать выражение ma как произведение переменных m и a, а не как самостоятельную переменную ma.
  • Операторы работают с Литералами, Переменными и результатами функций. Мы будем использовать только следующие операторы: +, _, *, / и ^ (возведение в степень).
  • Функции – это продвинутые операции, вроде sin(), cos(), tan(), min(), max() и т. д.
  • Разделители Аргументов Функции – это обычные запятые вот в таком контексте: max(4,5). Здесь вызывается функция max с двумя аргументами, разделенными запятой.

Возьмем еще два токена, которые обычно не учитываются, но с ними будет проще: Левая и Правая Круглые Скобки.

Размышления

Неявное умножение

Зачастую оператор умножения в выражениях опускается. Пользователь может писать 5x вместо 5*x. Точно так же можно действовать и с функциями: 5sin(x) = 5*sin(x).

Можно даже позволить писать 5(x) и 5(sin(x)), но стоит ли?

С жесткими правилами синтаксиса токенизация будет проще. Также можно будет использовать многобуквенные имена переменных, например, price.

Если разрешить подобные вольности, платформа станет интуитивно понятнее. Плюс это еще один челлендж для разработчика. Пойдем по сложному пути и разрешим неявное умножение.

Синтаксис

Хотя мы и не пишем новый язык программирования, все равно необходимо установить ряд синтаксических правил. Они определят допустимый формат сочетания токенов. Так пользователи будут знать, что вводить, а программист – что ожидать.

  1. Токены могут быть разделены любым количеством пробельных символов, включая нулевое.

    Другими словами, интервал между токенами не имеет значения. Разумеется, кроме многосимвольных токенов, например, числового Литерала 22.
  2. Аргументы Функций должны находиться в скобках.

    Для чего это нужно? При парсинге из строки будут удалены все пробелы, поэтому важно знать, где начинается и заканчивается функция.
  3. Неявное умножение допускается только между Литералами и Переменными или Литералами и Функциями, при этом Литерал всегда должен быть первым множителем. Круглые скобки опциональны.

А теперь приступим к работе.

Моделирование данных

Как должны быть представлены данные? Разберемся на простом примере 2y + 1.

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

Значит, прежде всего нужно определить класс для токенов, чтобы проще было с ними работать:

Алгоритм

Теперь можно построить скелет функции-лексера.

Наш токенизатор будет перебирать массив str посимвольно и создавать токены на основе найденных значений.

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

Этот код очень прост. Функции-помощники, которые в нем встретились (isComma(), isDigit(), isLetter(), isOperator(), isLeftParenthesis(), isRightParenthesis() могут быть легко определены с помощью регулярных выражений:

Обратите внимание, здесь нет функций isFunction(), isLiteral() или isVariable(). Мы тестируем каждый символ отдельно от других.

Парсер уже работает. Вы можете протестировать его на выражениях:

  • 2 + 3
  • 4a + 1
  • 5x + (2y)
  • 11 + sin(20.4)

Все хорошо? Не совсем.

В последнем выражении число 11 отображается как два Литеральных токена вместо одного. А функция sin вообще выглядит как три отдельных токена.

Действительно, некоторые токены могут состоять из нескольких символов: и Литералы (55, 7.9, .5), и Функции (sin, cos). Переменные односимвольны, но они могут объединяться в выражениях неявного умножения. Как решить эту проблему?

Буфер

На помощь приходит буфер. Два буфера: один – для хранения Литеральных символов (цифр и десятичных точек), второй – для букв (Переменных и Функций).

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

Например, анализ выражения 456.7 xy + 6sin(7.04 x) — min(a, 7) будет выглядеть так:

Готово, осталось совсем немного.

Инструкция

Что произойдет, если текущий символ является оператором, а numberBuffer не пуст? А могут ли оба буфера быть непустыми одновременно?

Соберем все вместе в небольшой инструкции. Слева от стрелки указан тип текущего символа (char), NB = numberBuffer, LB = letterBuffer, LP = левая скобка, RP = правая скобка.

  • Цикл по массиву символов, определение типа текущего символа:
    • цифра => отправить char в NB
    • десятичная точка => отправить char в NB
    • буква => объединить содержимое NB в один Литерал и отправить в результат, затем отправить char в LB
    • оператор => объединить содержимое NB в один Литерал и отправить в результат или взять содержимое LB, разделить его на отдельные Переменные и отправить в результат, затем отправить char в результат
    • LP => объединить содержимое LB в одну Функцию и отправить в результат или (объединить содержимое NB в один Литерал и отправить в результат и отправить Оператор * в результат), затем отправить char в результат
    • RP => объединить содержимое NB в один Литерал и отправить в результат, взять содержимое LB, разделить его на отдельные Переменные и отправить в результат, затем отправить char в результат
    • запятая => объединить содержимое NB в один Литерал и отправить в результат,  взять содержимое LB, разделить его на отдельные Переменные и отправить в результат, затем отправить char в результат
  • закончить цикл
  • объединить содержимое NB в один Литерал и отправить в результат,  взять содержимое LB, разделить его на отдельные Переменные и отправить в результат

Обратите внимание на две вещи:

  1. Неявное умножение преобразуется в явное, в результат добавляется оператор *. Также нужно помнить о том, что между отдельными переменными, извлеченными из LB необходимо вставлять тот же оператор умножения.
  2. После цикла нужно очистить все накопленное в буферах.

Оформление

Соберем все вместе и оформим токенизатор на реальном языке программирования:

 

А вот небольшое демо работы этого лексического анализатора:

Обратите внимание, что в операции неявного умножения добавлены операторы *

Для полноты картины нужно провести ряд тестов и учесть крайние случаи, например, отрицательные числа.

Оригинальная статья: How to build a math expression tokenizer using JavaScript (or any other language)

Интересные материалы

Хотите получать больше интересных материалов с доставкой?

Подпишитесь на нашу рассылку:

И не беспокойтесь, мы тоже не любим спам. Отписаться можно в любое время.




Добавить комментарий