Mötərizələr ardıcıllığı (Həll təhlili)

Açılan mötərizələri daxil edəcəyimiz bir yığın (stack) müəyyən edəcəyik. Hər yeni simvol daxil olduqda yığın ilə aşağıdakı əməliyyatları icra edirik:

• simvol '$($' ilə qarşılaşdıqda onu yığına daxil edirik;

• simvol '$)$' ilə qarşılaşdıqda yığından bir elementi çıxarırıq. Bu anda yığın boş olarsa, ardıcıllıq mötərizə ardıcıllığı deyil (müəyyən bir mərhələdə bağlanan mötərizələrin sayı açılan mötərizələrdən çoxdur);

Sətirin işlənməsi bitdikdə yığın boş qalmalıdır.

Yığında model yaratmaq üçün tək bir dəyişəndən istifadə edilə bilər. Elə götürək ki, $cnt$ dəyişəni yığındakı açılan mötərizələrin sayını saxlayır. Beləliklə, simvolu '$($' yığına daxil edərkən cnt-ni $1$ artırırıq və element yığından çıxarıldıqda cnt-ni $1$ azaldırıq.

Nümunə

Birinci nümunədən "$((())())$" sətiri üçün yığın işini modelləşdirək.

Alqoritmin həyata keçirilməsi

Giriş sətirini oxuyuruq.

cin >> s;

$cnt$ dəyişəni açılmayan mötərizələrin cari sayını (daha dəqiq açılan, lakin bağlanmayan mötərizələrin sayı) saxlayır.

$flag$ dəyişəni bir iterasiya zamanı bağlanan mötərizələrin sayının açılanlardan çox olduğu təqdirdə $1$-ə təyin edilir. İlkin olaraq flag = 0 təyin edirik.

cnt = flag = 0;

Giriş sətirini simvol-simvol işləyərək yığınla işi modelləşdiririk.

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

Cari simvolu $s[i]$ işləyirik.

   if (s[i] == '(') cnt++; else cnt--;

Bağlanan mötərizələrin sayı bir anda açılanlardan çox olarsa, giriş ardıcıllığı mötərizə ardıcıllığı deyil.

   if (cnt < 0) flag = 1;
}

$flag$ və $cnt$ dəyişənlərinin dəyərlərinə görə cavab çıxarırıq. Sətirin işlənməsinin sonunda yığın boş olarsa, cnt = 0 olacaqdır.

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

Java string ilə həyata keçirmə

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 simvol massivi ilə həyata keçirmə

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 həyata keçirmə

Giriş sətirini oxuyuruq.

s = input()

$cnt$ dəyişəni açılmayan mötərizələrin cari sayını (açılan, lakin bağlanmayan mötərizələrin sayı) saxlayır.

$flag$ dəyişəni, bir iterasiya zamanı bağlanan mötərizələrin sayının açılanlardan çox olarsa $1$-ə təyin edilir. İlkin olaraq flag = 0 təyin edirik.

cnt = flag = 0

Giriş sətirini simvol-simvol işləyərək yığınla işi modelləşdiririk.

for ch in s:

Cari simvolu $s[i]$ işləyirik.

  if ch == '(': cnt += 1
  else: cnt -= 1

Bağlanan mötərizələrin sayı bir anda açılanlardan çox olursa, giriş ardıcıllığı mötərizə ardıcıllığı deyil.

  if cnt < 0: flag = 1

$flag$ və $cnt$ dəyişənlərinin dəyərlərinə görə cavab çıxarırıq. Sətirin işlənməsinin sonunda yığın boş olarsa, cnt = 0 olacaqdır.

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