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

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

Правильные скобочные выражения
- ()
- ()()
- ((()))
- (()())
- ((()())())

Неправильные скобочные выражения
- )(
- ())(
- (
- ())
- )(())(

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

Выход: Либо "Не правильное", либо "Правильное".

#include <stdio.h>
int main ()
{
    int ch, a;
    printf ("Введите слово из скобок: ");
    do {
        ch = getchar();
        if ( ch == '(' ) 
           a++;
        else 
           if ( ch == ')' ) 
               if( --a < 0 ) 
                   break;
    } while ( ch != '\n' );
    if ( a == 0 ) 
        printf ("Правильное\n");
    else 
        printf ("Не правильное\n");
    return 0;
}

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

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

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

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

Утверждение, что "для данного алгоритма достаточно конечной памяти и одного пробега по сколь угодно большим входным данным, чтобы получить верный ответ" неверно. Например, приведённый алгоритм будет работать неправильно, если ввести очень много однотипных скобок, так чтобы их количество не помещалось в тип int и при изменении переменной a произошло переполнение.

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

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

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