Баланс скобок (#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");
        }
    }
}