Alqoritm Analizi

Açılan mötərizələri yalnız saxlayacağımız bir yığın elan edək. Növbəti simvolu aldıqda, yığınla aşağıdakı əməliyyatı yerinə yetiririk:

• əgər simvol ‘(‘ ilə qarşılaşırsa, onu yığında saxlayırıq;

• əgər simvol ‘)’ ilə qarşılaşırsa, yığından bir elementi çıxarırıq. Əgər bu nöqtədə yığın boşdursa, deməli ardıcıllıq mötərizələrlə düzgün formalaşdırılmayıb (bəzi bir məqamlarda bağlayıcı mötərizələrin sayı açıq olanların sayından çoxdur);

Sətirin emalı bitdikdə, yığın boş olmalıdır.

Yığını tək bir dəyişən istifadə edərək modeləyə bilərik. Dəyişən cnt yığında olan açıq mötərizələrin sayını saxlasın. Sonra, ‘(‘ simvolunu yığına əlavə etdikdə, cnt++ əməliyyatını, yığından bir elementi çıxardıqda isə cnt-- əməliyyatını yerinə yetirəcəyik.

Nümunə

"((())())" sətiri üçün yığın əməliyyatını modeləyək.

Alqoritm Tətbiqi

Giriş sətrini oxuyun.

cin >> s;

cnt dəyişəni cari bağlanmamış mötərizələrin sayını (yəni, hələ öz uyğun bağlayıcılarını tapmamış açıq mötərizələrin sayını) saxlayır.

flag dəyişəni, hər hansı bir iterasiyada bağlayıcı mötərizələrin sayı açıq olanların sayından çox olduqda 1-ə bərabər olacaq. Əvvəlcə flag = 0 olaraq təyin edin.

cnt = flag = 0;

Giriş sətrini simvol-simvol işləyərək, yığın əməliyyatını modeləyin.

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

flag və cnt dəyişənlərinin dəyərlərinə əsasən cavabı çıxarın. Sətirin emalı bitdikdə yığın boş olacaqsa, cnt = 0 olmalıdır.

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

Sətir istifadə edərək Java tətbiqi

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();    
    }
}

Simvol massivi istifadə edərək Java tətbiqi

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 tətbiqi

Giriş sətrini oxuyun.

s = input()

cnt dəyişəni cari bağlanmamış mötərizələrin sayını (yəni, hələ öz uyğun bağlayıcılarını tapmamış açıq mötərizələrin sayını) saxlayır.

flag dəyişəni, hər hansı bir iterasiyada bağlayıcı mötərizələrin sayı açıq olanların sayından çox olduqda 1-ə bərabər olacaq. Əvvəlcə flag = 0 olaraq təyin edin.

cnt = flag = 0

Giriş sətrini simvol-simvol işləyərək, yığın əməliyyatını modeləyin.

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

flag və cnt dəyişənlərinin dəyərlərinə əsasən cavabı çıxarın. Sətirin emalı bitdikdə yığın boş olacaqsa, cnt = 0.

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