Анализ алгоритма

Объявим стек, в котором будем хранить только открывающиеся скобки. При поступлении очередного символа делаем следующую операцию со стеком:

• если встретился символ ‘(‘, то заносим его в стек;

• если встретился символ ‘)‘, то извлекаем элемент из стека. Если стек при этом пуст, то последовательность не скобочная (на некотором этапе количество закрывающихся скобок больше количества открывающихся);

В конце обработки строки стек должен быть пустой.

Моделировать стек можно при помощи одной переменной. Пусть переменная cnt хранит количество открытых скобок в стеке. Тогда при занесении в стек символа ‘(‘ будем производить операцию cnt++, а при удалении элемента из стека операцию cnt--.

Пример

Промоделируем работу стека для строки “((())())” из первого примера.

Реализация алгоритма

Читаем входную строку.

cin >> s;

Переменная cnt хранит количество текущих незакрытых скобок (то есть количество открывающихся скобок, которым еще не встретились соответствующие закрывающиеся).

Переменная flag станет равной 1, если на какой-то итерации количество закрывающихся скобок станет больше числа открывающихся. Изначально положим flag = 0.

cnt = flag = 0;

Обрабатываем посимвольно входную строку, моделируем работу со стеком.

for (i = 0; i < s.size(); i++)
{
    if (s[i] == '(') cnt++; else cnt--;
    if (cnt < 0) flag = 1;
}

В зависимости от значений переменных flag и cnt выводим ответ. Стек будет пустым в конце обработки строки, если cnt = 0.

if (flag == 0 && cnt == 0) cout << "YES\n"; else cout << "NO\n";

Java реализация через строку

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        String s = con.nextLine();
        boolean flag = false; 
        int open = 0;
        for(int i = 0; i < s.length(); i++)
        {
            if (s.charAt(i) == '(') open++; else open--;
            if (open < 0) flag = true;
        }
        if (flag || (open > 0)) System.out.println("NO"); else System.out.println("YES");
        con.close();    
    }
}

Java реализация через массив символов

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        char s[] = con.nextLine().toCharArray();
        boolean flag = false; 
        int open = 0;
        for(int i = 0; i < s.length; i++)
        {
            if (s[i] == '(') open++; else open--;
            if (open < 0) flag = true;
        }
        if (flag || (open > 0)) System.out.println("NO"); else System.out.println("YES");
        con.close();    
    }
}

Python реализация

Читаем входную строку.

s = input()

Переменная cnt хранит количество текущих незакрытых скобок (то есть количество открывающихся скобок, которым еще не встретились соответствующие закрывающиеся).

Переменная flag станет равной 1, если на какой-то итерации количество закрывающихся скобок станет больше числа открывающихся. Изначально положим flag = 0.

cnt = flag = 0

Обрабатываем посимвольно входную строку, моделируем работу со стеком.

for ch in s:
    if ch == '(': cnt += 1
    else: cnt -= 1
    if cnt < 0: flag = 1

В зависимости от значений переменных flag и cnt выводим ответ. Стек будет пустым в конце обработки строки, если cnt = 0.

if flag == 0 and cnt == 0:
    print("YES")
else:
    print("NO")