Язык Си в примерах/Скобочки

Язык Си в примерах

---

1. Компиляция программ
2. Простейшая программа «Hello World»
3. Учимся складывать
4. Максимум
5. Таблица умножения
6. ASCII-коды символов
7. Верхний регистр
8. Скобочки
9. Факториал
10. Степень числа
11. Треугольник Паскаля
12. Корень уравнения
13. Система счисления
14. Сортировка
15. Библиотека complex
16. Сортировка на основе qsort
17. RPN-калькулятор
18. RPN-калькулятор на Bison
19. Простая грамматика
20. Задача «Расчёт сопротивления схемы»
21. Простая реализация конечного автомата
22. Использование аргументов командной строки
23. Чтение и печать без использования stdio
24. Декодирование звукозаписи в формате ADX
25. Другие примеры
26. XCC C

Задача "Скобки"

Программа "Скобки" должна определять правильность введённой скобочной структуры. Правильная скобочная структура, это то, что можно получить из арифметического выражения со скобками, выкинув все знаки операций и цифры. Например:

• Правильные скобочные структуры

• ()
• ()()
• ((()))
• (()())
• ((()())())

• Неправильные скобочные структуры

• )(
• ())(
• (
• ())
• )(())(

Вход: Слово в алфавите из двух круглых скобочек ( и ). Длина слова меньше 100000 символов.

Выход: Либо NO, либо YES.

 #include <stdio.h>

 int main(void)
 {
     int ch, a = 0;
     printf("Введите слово из скобок: ");

     do {
         ch = getchar();
         if (ch == '(') 
             a++;
         else if (ch == ')' && --a < 0) 
             break;
     } while (ch != '\n');

     if (a == 0) 
         printf("Правильно\n");
     else
         printf("Не правильно\n");

     return 0;
 }

Здесь нам встречается оператор ==, который соответствует логическому "тождественно равно". Когда мы пишем i = 0, то мы присваиваем переменной i значение 0.

Выражения a++ и --a меняют значения в памяти напрямую, то есть выражение --a в примере уменьшит значение переменной a вне зависимости от того, истинно ли выражение (--a < 0), или ложно.

Выражение a == 0 является проверкой равенства, её значение равно "истина" или "ложь".

В языке C/C++ "истина" соответствует любому ненулевому числу. Поэтому, вместо a == 0 мы могли бы написать равносильное a, но это не рекомендуется делать.

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

Свойством однопроходности обладает также рассмотренный нами алгоритм поиска максимума из чисел.

Задача сортировка чисел не является однопроходным алгоритмом.

1. Какие из перечисленных задач имеют однопроходные решения:
   • Найдите среднее арифметическое чисел.
   • Найдите дисперсию чисел (средний квадрат отклонения от среднего).
   • Найдите три самых маленьких числа среди введенных.
2. Напишите программу, которая проверяет правильность скобочной структуры, составленной из нескольких типов скобок (круглых, квадратных и фигурных).Например, ({()[]}) — правильная структура, а ({()[)}] — неправильная.
3. Напишите программу, которая выводит все правильные скобочные структуры заданной длины. А именно, опишите рекурсивную функцию "вывести все правильные скобочные структуры длины n".
4. Напишите программу, которая определяет число правильных скобочных структур заданной длины. Сведите задачу к множеству задач: число префиксов правильных скобочных структур длины n, которые имеют k незакрытых скобок.