Цикл статей о создании собственного парсера выражений: от токенизации до полноценного синтаксического разбора.
Оглавление цикла
- Часть 1. Токенизация
- Часть 2. Вычисление выражения в обратной польской записи
- Часть 3. Алгоритм сортировочной станции
- Часть 4. Парсер рекурсивного спуска
- Часть 5. Парсер Пратта
- Часть 6. Перевод из постфиксной формы в инфиксную (вы находитесь здесь)
В предыдущих частях мы построили полноценную систему разбора и вычисления математических выражений: реализовали токенизацию, синтаксический разбор с помощью трёх различных парсеров, поддержку унарных операторов, функций с переменным числом аргументов и проверку синтаксических ошибок. Всё это позволило получать корректные выражения в виде постфиксной записи (RPN) и эффективно их вычислять.
Однако постфиксная форма плохо подходит для отображения: её структура непрозрачна, а порядок выполнения операций неочевиден без подготовки. В этой части мы научимся преобразовывать выражение из RPN обратно в человекочитаемую инфиксную форму – с корректными скобками, приоритетами и унарными знаками.
Такой функционал необходим, если вы хотите визуализировать введённые выражения. Более того, это отличный способ убедиться, что ваша система разбора работает правильно: если инфиксное выражение, преобразованное в RPN и обратно, совпадает с исходным (с точностью до допустимой расстановки скобок), значит, всё идёт как надо.
Требования к преобразованию
Для восстановления инфиксной формы из RPN нам потребуется пройти по списку токенов и, как и при вычислении, использовать стек. Однако вместо чисел мы будем складывать текстовые подвыражения. Для каждого оператора (в том числе унарного) и функции нам нужно будет правильно:
- Выбрать нужное число аргументов из стека (так что без описаний функций не обойтись).
- Обернуть аргументы скобками, если это необходимо для сохранения приоритетов и ассоциативности.
- Вернуть результат обратно в стек.
Как и во всех прошлых частях, реализовывать будем в единственном файле expression_infix_builder.js с классом ExpressionInfixBuilder.
Интерфейс класса
Будем придерживаться привычной структуры. Создадим класс ExpressionInfixBuilder, у которого будет метод build(rpn), принимающий массив токенов (как и ранее во всех частях цикла). Каждый токен должен содержать хотя бы два свойства: тип (type) и значение (value). Тип определяет, что это за элемент (number, variable, constant, operator или function), а значение – конкретный символ.
Для корректного восстановления мы должны учитывать приоритеты операторов и их ассоциативность, чтобы обернуть подвыражения в скобки, если это необходимо. Также договоримся, что все операции за исключением возведения в степень (^) и унарного минуса (~) мы будем обрамлять пробелами для более красивого вида.
class ExpressionInfixBuilder {
constructor(functions) {
this.functions = functions
this.operators = {
"+": {args: 2, precedence: 1, associate: "left", value: " + "},
"-": {args: 2, precedence: 1, associate: "left", value: " - "},
"*": {args: 2, precedence: 2, associate: "left", value: " * "},
"/": {args: 2, precedence: 2, associate: "left", value: " / "},
"^": {args: 2, precedence: 3, associate: "right", value: "^"},
"~": {args: 1, precedence: 3, associate: "right", value: "-"}
}
this.constants = {
"pi": "π"
}
}
build(rpn) {
}
}
Переводим выражения
Как уже обсуждалось ранее, алгоритм преобразования выражения из постфиксной записи в инфиксную во многом повторяет алгоритм вычисления выражения. Однако вместо того чтобы выполнять операции и получать численные результаты, мы будем поэтапно строить строковое представление выражения. При этом возникает важная особенность: так как в постфиксной записи нет скобок, простая последовательная сборка выражения может привести к неверному порядку вычислений. Например, при прямом преобразовании выражения 1 2 3 + * получится 1 * 2 + 3 вместо ожидаемого 1 * (2 + 3). Чтобы восстановить правильную структуру, необходимо правильно расставлять скобки.
Самым простым решением было бы заключать каждый результат операции в скобки, но в этом случае выражение быстро становится сильно перегруженным и неудобным для восприятия. Вместо этого мы будем учитывать приоритеты операторов: если у текущего оператора приоритет выше, чем у аргумента, – аргумент берётся в скобки. Если приоритеты совпадают, тогда нужно учитывать ассоциативность оператора. Если ассоциативность не совпадает с позицией аргумента (левый или правый), то и в этом случае добавляются скобки. Такой подход позволяет восстанавливать выражения, близкие к оригинальным по форме, но с гарантией правильного порядка вычислений.
Заниматься определением, нужны ли скобки для оператора, будет метод addParenthesis, принимающий операнд, выполняемый оператор и сторону, с которой обрабатывается операнд. Для функций всё гораздо проще. Поскольку вызов функции всегда обрамляется скобками и разделителем, все аргументы можно просто добавлять как есть:
build(rpn) {
const stack = []
for (const token of rpn) {
if (token.type === "number" || token.type === "variable") {
stack.push({value: token.value, precedence: Infinity})
}
else if (token.type === "constant") {
stack.push({value: this.constants[token.value] ?? token.value, precedence: Infinity})
}
else if (token.type === "operator") {
const operator = this.operators[token.value]
const args = stack.splice(-operator.args)
if (args.length === 1) {
const arg = this.addParenthesis(args[0], operator, "right")
stack.push({value: `${operator.value}${arg}`, precedence: operator.precedence})
}
else {
const arg1 = this.addParenthesis(args[0], operator, "left")
const arg2 = this.addParenthesis(args[1], operator, "right")
stack.push({value: `${arg1}${operator.value}${arg2}`, precedence: operator.precedence})
}
}
else if (token.type === "function") {
const args = stack.splice(-this.functions[token.value].args).map(arg => arg.value)
stack.push({value: `${token.value}(${args.join(", ")})`, precedence: Infinity})
}
}
return stack.pop().value
}
addParenthesis(operand, operator, side) {
if (operand.precedence < operator.precedence || operand.precedence === operator.precedence && operator.associate !== side)
return `(${operand.value})`
return operand.value
}
Внимание, внутри метода build нет никаких проверок входного выражения на некорректность, так как мы ожидаем на входе исключительно правильное выражение (что в нашем случае гарантируется устройством парсера, осуществляющего перевод из инфиксной записи в обратную польскую).
Обновляем наш парсер
Давайте добавим созданный класс в наш парсер математических выражений и дополним его методом toInfix:
class ExpressionParser {
constructor(expression) {
...
this.infixBuilder = new ExpressionInfixBuilder(functions)
}
toInfix() {
return this.infixBuilder.build(this.rpn)
}
}
И теперь проверим наш класс в деле:
const expressions = [
"1 + 2 * 3",
"(1 + 2) * 3",
"(1 + 2) * (3 + 4)",
"2^2^3",
"-2^(2^3)",
"-(2^2)^3",
"-2^-2^-3",
"sin(2*pi*x)^2 + cos(-y)^2",
"-max(-cos(pi/2), (1+2)^2^3)"
]
for (const expression of expressions) {
const parser = new ExpressionParser(expression)
console.log(`${expression} -> ${parser.toInfix()}`)
}
/*
* 1 + 2 * 3 -> 1 + 2 * 3
* (1 + 2) * 3 -> (1 + 2) * 3
* (1 + 2) * (3 + 4) -> (1 + 2) * (3 + 4)
* 2^2^3 -> 2^2^3
* -2^(2^3) -> -2^2^3
* -(2^2)^3 -> -(2^2)^3
* -2^-2^-3 -> -2^-2^-3
* sin(2*pi*x)^2 + cos(-y)^2 -> sin(2 * π * x)^2 + cos(-y)^2
* -max(-cos(pi/2), (1+2)^2^3) -> -max(-cos(π / 2), (1 + 2)^2^3)
*/
Заключеине
В этой части мы всего за 57 строк ванильного Javascript кода научились восстанавливать инфиксную форму выражения по его постфиксной записи и ещё немного расширили наш парсер. Хотя на первый взгляд задача кажется простой – нужно просто заменить вычисления на сборку строк – на практике требуется аккуратно расставлять скобки, чтобы сохранить порядок операций. Для этого мы учли приоритеты операторов и их ассоциативность. Результатом стал класс, способный превращать любое корректное RPN-выражение в человекочитаемую форму, максимально близкую к оригиналу.
На этом цикл статей по разбору математических выражений завершается. Спасибо, что прочитали и, надеюсь, вам удалось узнать что-то новое!
Куда же без исходников?
class ExpressionInfixBuilder {
constructor(functions) {
this.functions = functions
this.operators = {
"+": {args: 2, precedence: 1, associate: "left", value: " + "},
"-": {args: 2, precedence: 1, associate: "left", value: " - "},
"*": {args: 2, precedence: 2, associate: "left", value: " * "},
"/": {args: 2, precedence: 2, associate: "left", value: " / "},
"^": {args: 2, precedence: 3, associate: "right", value: "^"},
"~": {args: 1, precedence: 3, associate: "right", value: "-"}
}
this.constants = {
"pi": "π"
}
}
build(rpn) {
const stack = []
for (const token of rpn) {
if (token.type === "number" || token.type === "variable") {
stack.push({value: token.value, precedence: Infinity})
}
else if (token.type === "constant") {
stack.push({value: this.constants[token.value] ?? token.value, precedence: Infinity})
}
else if (token.type === "operator") {
const operator = this.operators[token.value]
const args = stack.splice(-operator.args)
if (args.length === 1) {
const arg = this.addParenthesis(args[0], operator, "right")
stack.push({value: `${operator.value}${arg}`, precedence: operator.precedence})
}
else {
const arg1 = this.addParenthesis(args[0], operator, "left")
const arg2 = this.addParenthesis(args[1], operator, "right")
stack.push({value: `${arg1}${operator.value}${arg2}`, precedence: operator.precedence})
}
}
else if (token.type === "function") {
const args = stack.splice(-this.functions[token.value].args).map(arg => arg.value)
stack.push({value: `${token.value}(${args.join(", ")})`, precedence: Infinity})
}
}
return stack.pop().value
}
addParenthesis(operand, operator, side) {
if (operand.precedence < operator.precedence || operand.precedence === operator.precedence && operator.associate !== side)
return `(${operand.value})`
return operand.value
}
}
А так же expression_parser.js – парсер математических выражений, использующий созданный класс из этой части.