Möhrəklərin balansı (#2479)

Alqoritm Analizi

Problem həll etmək üçün simvolik yığın istifadə edəcəyik. Giriş sətirinin simvolları arasında ardıcıl olaraq hərəkət edəcək və:

cari simvol açıq mötərizədirsə (ya dairəvi ya da kvadrat), onda onu yığına qoyuruq.
cari simvol bağlayıcı mötərizədirsə, yığının üstündə uyğun açıq mötərizə olmalıdır. Əgər bu belə deyilsə, və ya yığın boşdursa, onda mötərizə ifadəsi düzgün deyil.

Düzgün sətirin emalı sonunda yığın boş olmalıdır.

Nümunə

“( ( [ ] ) [ ] )” sətiri üçün yığın simulyasiyasını nəzərdən keçirin.

Alqoritm Tətbiqi

Giriş mötərizə ifadəsini stroka massivinə oxuyacağıq. Problemdə istifadə olunan yığın s-i elan edirik.

char stroka[150];
stack<char> s;

Testlərin sayını tests oxuyun. Hər giriş sətiri stroka üçün onun uzunluğunu len hesablayın. flag dəyişəni giriş mötərizə ifadəsi düzgün deyilsə 1-ə bərabər olacaq.

scanf("%d\n",&tests);
while(tests--)
{
    gets(stroka); flag = 0;
    
    // yığın s-i təmizlə.
    while(!s.empty()) s.pop();

    // Giriş sətiri stroka-nın simvolları arasında hərəkət edin.
    for(i = 0; i < strlen(stroka); i++)
    {
        // Açıq mötərizəni yığına qoyun.
        if ((stroka[i] == '(') || (stroka[i] == '[')) s.push(stroka[i]);
        
        // Əgər cari simvol stroka[i] bağlayıcı mötərizədirsə, onda
        // yığının üstündən simvolu çıxarın, bu uyğun açıq mötərizə olmalıdır. Əgər bu belə deyilsə, və ya yığın boşdursa, onda flag-i 1-ə bərabər edin.
        else if (!s.empty() && ((stroka[i] == ')' && s.top() == '(') || (stroka[i] == ']' && s.top() == '['))) s.pop();
        else flag = 1;
    }

    // Əgər sətirin emalı sonunda yığın boş deyilsə, onda giriş mötərizə ifadəsi düzgün deyil.
    if (!s.empty()) flag = 1;

    // flag dəyişənin dəyərinə görə cavabı çıxarın.
    if (flag) printf("No\n"); else printf("Yes\n");
}

Java Tətbiqi

import java.util.*;

public class Main
{
    static char rev(char c)
    {
        return (c == ')') ? '(' : '[';
    }

    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        int tests = con.nextInt();
        String Line = con.nextLine();
        while(tests-- > 0)
        {
            Line = con.nextLine();
            Stack<Character> s = new Stack<Character>();
            int Flag = 0;
            for(int i = 0; i < Line.length(); i++)
            {
                if (Flag > 0) break;
                if ((Line.charAt(i) == '(') || (Line.charAt(i) == '[')) s.push(Line.charAt(i));
                if ((Line.charAt(i) == ')') || (Line.charAt(i) == ']'))
                {
                    if (s.empty() or (s.peek() != rev(Line.charAt(i)))) Flag = 1;
                    else s.pop();
                }
            }
            if (!s.empty()) Flag = 1;
            if (Flag > 0) System.out.println("No");
            else System.out.println("Yes");
        }
    }
}