|
Читайте также: |
-Железнодорожный тупик.
-стопка горшков.
-магазин пистолета.
Принцип(девиз) работы Stack
-Первым пришёл-последним ушёл.
очередь. Первым пришёл-первым ушёл.
Стеком называется динамическая структура данных, в которой добавление новых элементов и удаление существующих происходит в специальной точке, называемой вершиной стека.
Стек является основным инструментов для практической программной реализации рекурсии. Он необходим для управления точками возврата рекурсивных алгоритмов (запоминает, куда нужно вернутся после рекурсивного вызова). Он необходим для запоминания параметров рекурсивных процедур. Сама система создаёт СТЕК!
Использование стека рассмотрим на простом модельном примере. Им является задача о проверке правильности расстановки скобок разных типов.
Формулировка задачи:
Пусть дано арифметическое выражение содержание скобки разных типов ((), [], {} и т.д.) Скобка каждого типа может быть либо открывающей, либо закрывающей. Требуется написать алгоритм, проверяющий правильность расстановки скобок.
Алгоритм проверки правильности расстановки скобок разных типов.
На входе алгоритм- символьная скобка с записью исследуемого скобочного выражения.
На выходе из алгоритма- диагностика (сообщение).
Для промежуточного хранения данных алгоритм использует Stack
Шаг 1. Просматривать входную строку слева направо символ за символом.
1если текущий символ- открывающая скобка, то записать её в stack.
1.1.если текущий символ- закрывающая скобка, то:
1.1.1. проверить, пуст стек или нет. Если стек пуст, то ошибка: выдать сообщение об ошибке: «Закрывающих скобок больше, нет открывающих». Работу алгоритма прекратить.
1.1.2. Stack не пуст. Извлечь из него открывающую скобку и проверить типы открывающей и закрывающей скобок. Если типы скобок совпали, то ничего не делаем, а если не совпали, то ошибка: выдать сообщение «несоответствие типов скобок». Работу алгоритма прекратить.
Шаг 2. Проверить Stack. Если он пуст, то скобки расставлены верно. Если не пуст, то ошибка: выдать сообщение: «Открывающих скобок больше, чем закрывающих». Работу алгоритма прекратить.
Private Sub click()
Dim A As String, Otkr As String, Zakr As String, x As String. y As String
Dim Ot As Integer, Za As Integer
Dim I As Integer, L As Integer, TS As Integer ‘Вершина стека
Dim ST() As String ‘Сам стек
Otkr=”([{<”
Zakr=”)]}>”
A=InputBox (“Введите выражение со скобками”+otkr+zakr, “Проверка скобок”)
L=Len(A) ‘В перемещенную L помещаем длину строки А (со скобками)
ReDim ST(L)
TS=0 ‘инициализация стека
For I=1 To L
X=Mid(A,I,1) ‘вырезает i-й символ из строки А, начиная с I, с количеством «1» заданных символов
Ot=Instr(otkr,x) ‘ Записывает порядковый номер в переменную Ot (от 1 до 4)
If Ot <>0 Then Если текущий символ – открывающая скобка, то записываем его в стек
TS=TS+1
ST(TS)=x
GoTo cont ‘(→стек
End If
Za=instr(zakr,x):If Za=0 Then GoTo cont ‘Проверяем,евляется ли текущий символ закрывающей скобкой.
If TS=0 Then MsgBox “Закрывающих скобок больше” “Проверка скобок” ‘ проверка пуст стек или нет.
Exit Sub
y=ST(TS)
TS=TS-1 ‘стек→(
Ot=instr(otkr y)
If Za<> Ot Then MsgBox “Несоответствие типов скобок”, “Проверка скобок”
Exit Sub
Cont:
Next I
If TS=0 Then
MsgBox “Скобки расставлены верно”,”Проверка скобок”
Else
MsgBox “Открывающих скобок больше”, ”Проверка скобок”
End If
End Sub
Дата добавления: 2015-11-13; просмотров: 77 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Простейшие методы сортировки: пузырьковая, поиском максимального элемента. | | | Вопрос 21. Графы. Алгоритм поиска достижимых вершин графа. |