На этом шаге мы преведем рекрсивные функции, решающие эту задачу.

    Цель этого этапа заключается в преобразовании входной строки, представляющей собой математическое выражение, в последовательность (список) лексем, которыми могут быть:

• положительные или отрицательные целые числа: последовательность цифр, которой может предшествовать символ '-';
• операции: '+', '-', '*', '/';
• круглые скобки: '(' и ')'.

    Например, для входной строки "-(-6 / 3) - (-(4)) + (18-2)" алгоритм на первом этапе должен создать такой список:

    ['-', '(', '-6', '/', '3', ')', '-', '(', '-', '(', '4', 
          ')', ')', '+', '(', '18', '-', '2', ')']   .

    Прежде всего алгоритм игнорирует символы пробела и табуляции (пропуски). Кроме того, отметим, что знак минус может выполнять разные роли: помимо обозначения отрицательного числа, он может быть также либо одноместной, либо двуместной (бинарной) операцией. Например, алгоритм должен считать -6 единым числом и потому не должен создавать две отдельные лексемы для (унарного) минуса и числа 6. Пример также показывает, что унарный минус может появиться в начале входной последовательности или между двумя левыми скобками. Взаимно-рекурсивные функции, которые мы вскоре рассмотрим, возникают из-за необходимости обработки унарных минусов в математических выражениях. Наконец, отметим, что лексемой может быть число, состоящее из нескольких цифр, возможно, со знаком минус.

    Для решения этой задачи воспользуемся двумя похожими методами tokenize_unary() и tokenize() из примера 9.7, которые получают на входе строку s длины n и возвращают список лексем. Разница между ними лишь в том, что первый предполагает, что первым непустым символом s может быть унарный минус. Оба метода посредством функции is_number() из примера 9.8 проверяют также, является ли строка целым числом.

    Размер задач - длина входной строки (n). Существует несколько начальных условий. Если строка пуста или содержит лишь пропуски, методы должны вернуть пустой список. Кроме того, если строка состоит из единственного непустого символа (предыдущее условие уже "отсекло" все пропуски), то начальное условие должно вернуть список, содержащий этот символ. Оба этих условия гарантируют, что в рекурсивных условиях входная строка будет содержать не менее двух символов. Следовательно, мы можем спокойно обращаться ко второму элементу строки, не опасаясь выхода её индекса за границы строки.

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

    Во-первых, если первый элемент входной строки - пропуск, то им нужно пренебречь. В этом случае оба метода, вызвав самих себя, должны вернуть лишь остаток входной строки (s_1...n-1).

def tokenize_unary(s):
    if not s or s == ' ' or s == '\t':
        return []
    elif len(s) == 1:
        return [s]
    elif s[0] == ' ' or s[0] == '\t':
        return tokenize_unary(s[1:])
    elif s[0].isdigit() or s[0] == '-':
        if s[0].isdigit() and (s[1] == ' ' or s[1] == '\t'):    
            return [s[0]] + tokenize(s[2:])
        else:
            t = tokenize(s[1:])
            if t == []:
                return [s[0]]
            else:
                if is_number(t[0]):
                    t[0] = s[0] + t[0]
                    return t
                else:
                    return [s[0]] + t
    else:
        if s[0] == '(':
            t = tokenize_unary(s[1:])
        else:
            t = tokenize(s[1:])
        return [s[0]] + t


def tokenize(s):
    if not s or s == ' ' or s == '\t':
        return []
    elif len(s) == 1:
        return [s]
    elif s[0] == ' ' or s[0] == '\t':
        return tokenize(s[1:])
    elif s[0].isdigit():
        if s[1] == ' ' or s[1] == '\t':
            return [s[0]] + tokenize(s[2:])
        else:
            t = tokenize(s[1:])
            if t == []:
                return [s[0]]
            else:
                if is_number(t[0]):
                    t[0] = s[0] + t[0]
                    return t
                else:
                    return [s[0]] + t
    else:
        if s[0] == '(':
            t = tokenize_unary(s[1:])
        else:
            t = tokenize(s[1:])
        return [s[0]] + t

def is_number(s):
    try:
        float(s)
        return True
    except ValueError:    
        return False

    На следующем шаге мы рассмотрим функцию tokenize().

Предыдущий шаг Содержание Следующий шаг