Помощь - Поиск - Пользователи - Календарь
Полная версия: Стек. Проверка правильности формулы.
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
hzch
Задание вот такое, не пойму как реализовать через стек. Помогите пожалуйста, достаточно будет алгоритма, дальше разберусь.

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

Заранее спасибо!
Lapp
Цитата(hzch @ 11.10.2007 16:20) *
(что-то вроде x(x+z(y-x)), такого типа как я понимаю записи)

Нет.. Смотри внимательнее. Термы не могут стоять просто рядом. Между ними должен быть знак операции.
Скорее, типа так: 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
Большое спасибо!
Все заработало, правда немного видоизменил алгоритм. Надеюсь что понял как подобные задания делать) Спасибо.
siusiura
Можешь показать как организовал программу?
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.