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

Оголосимо стек, в якому будемо зберігати лише відкриваючі скобки. При надходженні чергового символу робимо наступну операцію зі стеком:

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

• якщо зустрівся символ ‘)‘, то витягуємо елемент зі стека. Якщо стек при цьому порожній, то послідовність не дужкова (на деякому етапі кількість закриваючихся скобок більше кількості відкриваючихся);

В кінці обробки рядка стек має бути порожнім.

Моделювати стек можна за допомогою однієї змінної. Нехай змінна 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")