ВУЗ:
Составители:
Рубрика:
- 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 -
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »