Дужкові послідовності (Розбір)

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

• якщо зустрічається символ '$($', то заносимо його в стек;

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

По закінченні обробки рядка стек має залишатися порожнім.

Моделювання стека можна здійснити з використанням єдиної змінної. Нехай змінна $cnt$ зберігає кількість відкритих дужок у стеці. Тоді при поміщенні символу '$($' в стек збільшуємо cnt на $1$, а при вилученні елемента зі стека — зменшуємо $cnt$ на $1$.

Приклад

Промоделюємо роботу стека для рядка "$((())())$" з першого прикладу.

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

Читаємо вхідний рядок.

cin >> s;

Змінна $cnt$ зберігає кількість поточних незакритих дужок (тобто кількість відкриваючих дужок, для яких ще не зустрілися відповідні закриваючі).

Змінна $flag$ встановлюється в $1$, якщо на якійсь ітерації кількість закриваючих дужок стає більше числа відкриваючих. Спочатку встановимо flag = 0.

cnt = flag = 0;

Обробляємо вхідний рядок посимвольно, моделюючи роботу зі стеком.

for (i = 0; i < s.size(); i++)
{

Обробляємо поточний символ $s[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:

Обробляємо поточний символ $s[i]$.

  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")