10. Основы Kotlin. Дополнительные главы

Зміст

Разбор и представление арифметических выражений
1. Лексический анализ
2. Представление выражений

Разбор и представление арифметических выражений

Эта глава развивает содержимое шестого урока, отвечая на вопрос “А что делать, если простого разбиения строки на части недостаточно?”. Одной из подобных ситуаций является разбор арифметических выражений. Для этого и других похожих случаев программисты придумали парсеры — специальные функции или объекты, выполняющие разбор сложных строк. Для написания парсеров используется теория формальных языков, которой мы (вкратце) коснёмся в этой главе.

Рассмотрим пример. Пусть во входном файле содержится строчка, содержащая описание функции от x, например:

3*x*x - (2 / x)  + 7 -x

Необходимо по имеющемуся списку значений x (например, 1, 2 и -1) рассчитать значения данной функции и вернуть их в виде ассоциативного массива (например, 1 → 7, 2 → 16, -1 → 13).

Предполагается, что функция является целочисленной, и в ней могут присутствовать четыре арифметических действия и круглые скобки.

Как решать подобную задачу? Поэтапно.

1. Лексический анализ

Лексический анализ — первый этап решения. Его цель — разбиение исходного выражения на атомарные элементы, которыми в приведённом примере являются:

3, *, x, *, x, -, (, 2, /, x, ), +, 7, -, x

Обратите внимание, что в процессе лексического анализа из выражения выбрасываются пробелы.

Один из способов лексического анализа — применение регулярных выражений.

fun String.parseExpr(): Expression {
    val matchResults = Regex("""x|\+|-|\*|/|\(|\)|\d+?| +?|.+?""").findAll(this)
    val groups = matchResults.map { it.value }.filter { it.isNotBlank() }.toList()
    return Parser(groups).parse()
}

Заданное в этой функции регулярное выражение задаёт описание атомарного элемента. Это может быть x, знаки четырёх арифметических действий, знаки скобок, пробелы, и все прочие символы. Лямбда { it.isNotBlank() }убирает из имеющейся последовательности пробелы, оставляя всё остальное. После этого происходит переход к следующему этапу — собственно разбору. Но перед этим поговорим о том, а что, собственно, мы хотим получить в результате разбора.

2. Представление выражений

Зададимся вопросом: как представить арифметическое выражение с помощью структур данных, имеющихся в Котлине? Перед ответом на этот вопрос стоит ответить на другой: а что такое (формально) арифметическое выражение в нашей задаче? В теории формальных языков ответ может выглядеть так:

это x,
или же, это целая константа,
или же, это операция (сложение / вычитание / умножение / деление) над двумя другими выражениями
или, наконец, это операция “минус выражение” над другим выражением

Обратите внимание, что определение рекурсивно — понятие выражения использует в процессе определения себя же. Это довольно частый случай для подобных формальных описаний. Подобная рекурсивная структура с вариантами в Котлине может быть описана так называемым алгебраическим или запечатанным (sealed) классом.

sealed class Expression {
    object Variable : Expression()

    class Constant(val value: Int) : Expression()

    enum class Operation {
        PLUS,
        MINUS,
        TIMES,
        DIV;
    }

    class Binary(
            val left: Expression,
            val op: Operation,
            val right: Expression
    ) : Expression()

    class Negate(val arg: Expression) : Expression()
}

Алгебраический класс используется не сам по себе, а в виде его разновидностей, причём по правилам Котлина, для алгебраического класса эти разновидности должны быть описаны внутри определения самого класса (для версии 1.1 и выше — внутри того же файла).

Для описания разновидностей Expression используется уже знакомый синтаксис class Something(…) : Expression(). Разновидности алгебраического класса содержат дополнительную информацию по сравнению с ним самим:

целая константа Constant содержит своё значение value
инвертированное выражение Negate содержит свой аргумент (например, для -x аргумент будет равен x)
выражение с двумя аргументами (бинарное) Binary содержит два своих аргумента и выполняемую операцию

Обратите внимание на enum class Operation. Это не разновидность выражения (нет : Expression()), а просто дополнительный класс для описания операций с двумя аргументами. Слово enum означает перечисление в том смысле, что существует ограниченное (в данном случае — 4) количество операций — сложение, умножение, вычитание, деление. Все операции перечисляются через запятую, в конце (необязательно) ставится точка с запятой.

Последняя разновидность выражения object Variable : Expression(). В отличие от прочих разновидностей, эта является не классом, а объектом. В Котлине объект отличается от класса тем, что для данного типа существует ровно один объект данного типа — в данном случае это переменная x. У объекта нельзя вызывать конструкторы, а обращаются к нему просто по имени: в данном случае Variable. Если бы нас интересовали выражения с несколькими переменными, Variable тоже превратился бы в класс со свойством name: имя конкретной переменной.

Подобное описание выражения позволяет с лёгкостью рассчитать его значение при заданном x:

fun Expression.calculate(x: Int): Int = when (this) {
    Variable -> x
    is Constant -> value
    is Binary -> when (op) {
        PLUS  -> left.calculate(x) + right.calculate(x)
        MINUS -> left.calculate(x) - right.calculate(x)
        TIMES -> left.calculate(x) * right.calculate(x)
        DIV   -> left.calculate(x) / right.calculate(x)
    }
    is Negate -> -arg.calculate(x)
}

В данном when мы перебираем все возможные варианты выражения-получателя:

значение переменной равно заданному x: Int
значение константы равно её свойству value
значение Negate равно минус значению её выражения-аргумента
значение Binary рассчитывается аналогично с учётом конкретной операции

Сторінки: 1 2