Алгоритмизации

• Название: Алгоритмизации
• Дата: 27.09.2022
• Размер: 1.15 Mb.
• Имя файла: 12_100229_1_124427 (1).docx
• Тип: Документы; #700459
• страница: 30 из 67

Алгоритмпроверкиправильностирасстановкискобок

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

При реализации алгоритма анализа исходное выражение просматривается слева направо.

1. 
   Если в выражении обнаружена открывающаяся скобка, то анализируем содержимое стека:
   

а) если стек пуст или не пуст, но в вершине находится тоже открывающая скобка, то записываем ее в стек;

б) если стек не пуст и в вершине находится закрывающая скобка, то обе скобки выбрасываем из рассмотрения (находящуюся в стеке удаляем).

2. 
   Если обнаружена закрывающая скобка и стек пуст, то выражение составлено неверно, выводим сообщение об этом и завершаем работу.
   
3. 
   Просмотрев все выражение, проверяем стек и, если он не пуст, то баланс скобок нарушен и выражение составлено неверно, выводим сообщение об этом и завершаем работу.
   

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

3. СтруктураданныхОЧЕРЕДЬ

Очередь– упорядоченный набор данных (структура данных), в котором в отличие от стека извлечение данных происходит из начала цепочки, а добавление данных – в конец этой цепочки.

Очередь также называют структурой данных, организованной по

принципу FIFO(FirstIn,FirstOut) – первый вошел (первый созданный элемент очереди), первый вышел.

В языке Си работа с очередью, как и со стеком, реализуется при помощи структур, указателей на структуры и операций динамического выделения и освобождения памяти.

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

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

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

Шаблон элемента структуры, информационной частью которого является целое число, может иметь следующий вид:

struct Spis {

int info;

Spis *Next;

};

При организации очереди обычно используют два указателя

Spis *begin, *end;

где beginи end– указатели на начало и конец очереди соответственно, т.е. при создании очереди мы организуем структуру данных следующего вида:

info1	A1

begin

info2	A2

. . .

end

каждый элемент которой имеет информационную infои адресную Next(A1, A2, ...) части.

Основные операции с очередью следующие:

• 
  формирование очереди;
  
• 
  добавление нового элемента в конец очереди;
  
• 
  удаление элемента из начала очереди.