Седьмое занятие. Контейнерные классы.

Указание. В задачах можно заменить использование файлов на строки, если Вам не рассказывали работу с файлами средствами среды . NET

1. Выберите одну задачу из двух.  Дан файл - программа на каком-нибудь языке, например, PascalABC.net или С++. Используя стек, определить правильность расстановки операторных скобок ( begin end, {}). Или задана строка с арифметическим выражением. Определить правильность расстановки скобок ( может встречаться (), [], {}).

2. Дана корректная запись арифметического выражения в форме обратной польской записи. Вычислить выражение, используя стек.

Указание. Для любителей - пусть выражение записано в классическом варианте, без польской записи. Реализуйте парсер (используйте знания работы со строками!).

3. Дан набор слов (можно использовать любой текст на русском языке). Вывести все слова, длины не более 4, в порядке их следования. Вывод осуществлять по к  слов. Используйте очередь.

4*. Даны два поля шахматной доски. Найти минимальное число ходов, чтобы перейти коню из первого поля на второе (очередь).

Указание.

Идея решения основывается на использовании очереди. Вначале в очередь помещается элемент, определяющий исходное положение шахматного коня, а соответствующая клетка поля помечается как посещенная.

На каждом из следующих шагов алгоритма (пока очередь не пуста или не помечена конечная клетка) выполняются следующие действия.

  1. Из очереди извлекается очередной элемент, который определяет некоторую позицию (x,y).
  2. Находятся клетки в пределах поля, которые достижимы из (x,y) одним ходом шахматного коня, и которые еще не помечены.
  3. Элементы, соответствующие найденным клеткам, помещаются в очередь, а клетки помечаются как посещенные.

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

Для этого метку поля можно определить как позицию поля, из которой она была помечена. Подумайте об обеспечении минимальности ходов.

5. Дан тестовый файл. Определить частоту вхождений всех слов за один проход (Dictionary).

6. Реализуйте очередь целых чисел с приоритетом - из очереди всегда извлекается максимальный элемент. При реализации Вам достаточно изменить только один метод - либо Enqueue,  либо Dequeue.

7. Дана корректная запись логического выражения в форме обратной польской записи. Вычислить выражение.

8*. (+ООП). Задача "Расписание поездов" сформулирована для студентов 1-го курса. Реализуйте её.