Сбалансированные символы (общий случай)¶

Показанная выше задача о сбалансированных скобках является частным случаем более общей ситуации, возникающей во многих языках программирования. Обобщённая проблема балансировки и вложенности различных типов открывающих и закрывающих символов возникает очень часто. Например, в Python квадратные скобки, [ и ], используются для списков, фигурные скобки, { и }, - для словарей, а круглые (( и )) - для кортежей и арифметических выражений. Можно сколько угодно перемешивать символы до тех пор, пока каждый из них поддерживает свои открывающие и закрывающие отношения. Для строк вроде

{ { ( [ ] [ ] ) } ( ) }

[ [ { { ( ( ) ) } } ] ]

[ ] [ ] [ ] ( ) { }

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

Сравните верхний пример со следующими несбалансированными строками:

( [ ) ]

( ( ( ) ] ) )

[ { ( ) ]

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

Реализующая эту идею программа на Python показана в ActiveCode 5. Единственное изменение коснулось строки 16, где вызывается вспомогательная функция matches, помогающая с соотнесением символов. Каждый символ, удаляемый из стека, должен быть проверен на то, что он верно сопоставляется с текущим закрывающим символом. Если возникает ошибка, то булева переменная balanced устанавливается в False

from pythonds.basic.stack import Stack

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "([{":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                top = s.pop()
                if not matches(top,symbol):
                       balanced = False
        index = index + 1
    if balanced and s.isEmpty():
        return True
    else:
        return False

def matches(open,close):
    opens = "([{"
    closers = ")]}"
    return opens.index(open) == closers.index(close)


print(parChecker('{{([][])}()}'))
print(parChecker('[{()]'))

Решение общего случая балансирования символов (parcheck2)

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

Next Section - Конвертирование десятичных чисел в двоичные