Версия для печати темы

Автор: hzch 11.10.2007 19:20

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

Дан текстовый файл. Используя стек, проверить, является ли содержимое
текстового файла правильной записью формулы вида:
<Формула> ::= <Терм> | <Терм> + <Формула> | <Терм> - <Формула>
<Терм> ::= < Имя > | (<Формула>)
< Имя > ::= x | y | z
(что-то вроде x(x+z(y-x)), такого типа как я понимаю записи)

Заранее спасибо!

Автор: Lapp 12.10.2007 14:25

Нет.. Смотри внимательнее. Термы не могут стоять просто рядом. Между ними должен быть знак операции.
Скорее, типа так: x-(x+z-(y-x+z)+x+(x))

Проверку с помощью стека можно сделать примерно так..
Организуешь стек из символов. Делаешь проход по выражению слева направо.
Дальше я обозначаю последний символ стека как s (он же s0), а предпоследний - s1.

1. Если запись пустая, то [если глубина стека=1 или s=имя - успех, в остальных случаях - ошибка].

2. Первый символ проверяемой записи кладем в t (в записи его стираем).

3. Если t=имя, то [если стек пустой или s=( - кладем t в стек, в остальных случаях - ошибка].

4. Если t=операция, то [если если s - имя, то вынимаем s, в остальных случаях - ошибка]

5. Если t=(, то [если стек пустой или s=опер или s=(, то кладем t в стек; в остальных случаях - ошибка]

6. Если t=), то [если s=имя и s1=(, вынимаем 2 символа из стека, причем s закладываем в t и переходим на 3].

7. Переходим на 1.

Не очень красиво, но, думаю, верно... Наверное, можно лучше сделать.
Прога по этому алгоритму у меня, вроде, работает.

Автор: hzch 14.10.2007 18:11

Большое спасибо!
Все заработало, правда немного видоизменил алгоритм. Надеюсь что понял как подобные задания делать) Спасибо.

Автор: siusiura 11.12.2007 2:01

Можешь показать как организовал программу?