Динамические структуры данных. Задание практикума. Язык Паскаль. Вылиток А.А - 35 стр.

UptoLike

- 35 -
В алгоритме также нет проверки стека на пустоту перед тем, как взять
элемент из стека. Эта проверка не нужна, так как в сбалансированной
последовательности каждая открывающая скобка предшествует парной ей
закрывающей скобке. Следовательно, номер любой открывающей скобки
окажется в стеке раньше, чем произойдёт операция его извлечения на шаге (3).
По достижении конца файла стек станет пустым, поскольку открывающих и
закрывающих скобок в правильном входном тексте поровну.
Изобразим на рисунке последовательность состояний переменных f,
output, pos, sym, S при обработке текста A+(45-F(X)*(B-C)). Файловые
переменные будем изображать в виде ленты, разделённой на ячейки. В одной
ячейке располагается одна компонента файла. Если файл открыт для чтения, то
стрелка, указывающая снизу на ячейку, отмечает компоненту, которая будет
считана при очередном обращении к процедуре read. Если стрелка указывает
на место за последней ячейкой, то чтение очередной компоненты невозможно,
так как достигнут конец файла (функция eof в этой ситуации возвращает
значение «истина»). Стек представим в виде горизонтальной трубки, открытой с
правого конца (вершина стека справа). Левый конецдно» стека) отметим
ломаной линией, символизирующей «пружину» для выталкивания элементов из
стека.
Перед чтением первого символа из f значение переменной sym не
определено, pos=0, стек S и файл output пусты.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’
output
S
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’
pos
0
sym
sym
A’
pos
1
sym
+’
pos
2
       В алгоритме также нет проверки стека на пустоту перед тем, как взять
элемент из стека. Эта проверка не нужна, так как в сбалансированной
последовательности каждая открывающая скобка предшествует парной ей
закрывающей скобке. Следовательно, номер любой открывающей скобки
окажется в стеке раньше, чем произойдёт операция его извлечения на шаге (3).
По достижении конца файла стек станет пустым, поскольку открывающих и
закрывающих скобок в правильном входном тексте поровну.
       Изобразим на рисунке последовательность состояний переменных f,
output, pos, sym, S при обработке текста A+(45-F(X)*(B-C)). Файловые
переменные будем изображать в виде ленты, разделённой на ячейки. В одной
ячейке располагается одна компонента файла. Если файл открыт для чтения, то
стрелка, указывающая снизу на ячейку, отмечает компоненту, которая будет
считана при очередном обращении к процедуре read. Если стрелка указывает
на место за последней ячейкой, то чтение очередной компоненты невозможно,
так как достигнут конец файла (функция eof в этой ситуации возвращает
значение «истина»). Стек представим в виде горизонтальной трубки, открытой с
правого конца (вершина стека справа). Левый конец («дно» стека) отметим
ломаной линией, символизирующей «пружину» для выталкивания элементов из
стека.
       Перед чтением первого символа из f значение переменной sym не
определено, pos=0, стек S и файл output пусты.
       1   2   3   4   5   6   7   8    9   10   11   12   13   14   15   16   17
  f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’
     ↑

 output                                sym                       pos           0


   S



       1   2   3   4   5   6   7   8    9   10   11   12   13   14   15   16   17
  f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’
         ↑
                                     sym     ’A’          pos       1



       1   2   3   4   5   6   7   8    9   10   11   12   13   14   15   16   17
  f ’A’ ’+’ ’(’ ’4’ ’5’ ’-’ ’F’ ’(’ ’X’ ’)’ ’*’ ’(’ ’B’ ’-’ ’C’ ’)’ ’)’
               ↑
                                       sym       ’+’             pos           2




                                       - 35 -