Iv. Динамические структуры данных

printf ("Стек пуст"); 
return char(255); 
} 
S.size --; 
return S.data[S.size];
 
} 
Функция Pop возвращает символ, «снятый» с вершины стека, при этом размер стека уменьша-
ется на единицу. Если стек пуст, функция возвращает символ с кодом 255 (который никогда не 
может находиться в стеке по условию задачи и сигнализирует об ошибке). 
Задача. Ввести символьную строку, которая может содержать три вида скобок: (), [] и {}. Оп-
ределить, верно ли расставлены скобки (символы между скобками не учитывать). Например, в 
строках ()[{}] и [{}([])] скобки расставлены верно, а в строках ([)] и ]]]((( - невер-
но. 
Для одного вида скобок решение очень просто – ввести счетчик «вложенности» скобок, про-
смотреть всю строку, увеличивая счетчик для каждой открывающей скобки и уменьшая его для 
каждой закрывающей. Выражение записано верно, если счетчик ни разу не стал отрицательным 
и после обработки всей строки оказался равен нулю. 
Если используются несколько видов скобок, счетчики не помогают. Однако эта задача 
имеет красивое решение с помощью стека. Вначале стек пуст. Проходим всю строку от начала 
до символа с кодом 0, который обозначает конец строки. Если встретили открывающую скобку, 
заносим ее в стек. Если встретили закрывающую скобку, то на вершине стека должна быть со-
ответствующая ей открывающая скобка. Если это так, снимаем ее со стека. Если стек пуст или 
на вершине стека находится скобка другого вида, выражение неверное. В конце прохода стек 
должен быть пуст. 
В приведенной ниже программе используются написанные ранее объявление структуры 
Stack и операции Push и Pop. 

---

Программирование на языке Си
©
 К. Поляков, 1995-2009 
http://kpolyakov.narod.ru
13