Баланс дужок (#2479)

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

Для вирішення задачі будемо використовувати символьний стек. Будемо рухатися послідовно по символах вхідного рядка і:

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

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

Приклад

Розглянемо моделювання стека для рядка “( ( [ ] ) [ ] )”.

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

Вхідний дужковий вираз будемо читати в масив stroka. Оголосимо стек s, який використовується в задачі.

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

Читаємо кількість тестів tests. Для кожного вхідного рядка stroka обчислюємо його довжину len. Змінна flag стане рівною 1, якщо вхідний дужковий вираз не є правильним.

scanf("%d\n",&tests);
while(tests--)
{
    gets(stroka); flag = 0;
    
    // Очищаємо стек s.
    while(!s.empty()) s.pop();

    // Рухаємося по символах вхідного рядка stroka.
    for(i = 0; i < strlen(stroka); i++)
    {
        // Заносимо в стек відкриваючу дужку.
        if ((stroka[i] == '(') || (stroka[i] == '[')) s.push(stroka[i]);
        
        // Якщо поточний символ stroka[i] – закриваюча дужка, то
        // витягуємо символ з вершини стека, який має бути відповідною
        // відкриваючою дужкою. Якщо це не так, або якщо стек порожній, то встановлюємо flag рівним 1.
        else if (!s.empty() && ((stroka[i] == ')' && s.top() == '(') || (stroka[i] == ']' && s.top() == '['))) s.pop();
        else flag = 1;
    }

    // Якщо в кінці обробки рядка стек виявився не порожнім, то вхідний дужковий вираз не є правильним.
    if (!s.empty()) flag = 1;

    // Залежно від значення змінної flag виводимо відповідь.
    if (flag) printf("No\n"); else printf("Yes\n");
}

Java реалізація

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