2479. Баланс скобок

Имеется строка, содержащая скобки () и []. Скобочное выражение считается правильным, если выполняются следующие условия:

· строка является пустой;

· если выражения A и B правильные, то их конкатенация AB также является правильной;

· если выражение A правильное, то (A) и [A] также являются правильными.

Напишите программу, которая по заданной строке определяет, является ли скобочное выражение правильным. Длина каждой строки не превышает 128 символов.

Вход. Первая строка содержит количество тестов n. Каждая из следующих n строк содержит скобочное выражение, состоящее из символов ( ) и [ ].

Выход. Для каждого теста выведите в отдельной строке “Yes”, если выражение является правильным, и “No” в противном случае.

Пример входа	Пример выхода
3 ([]) (([()]))) ([()[]()])()	Yes No Yes

РЕШЕНИЕ

структуры данных - стек

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

Для решения задачи будем использовать символьный стек. Последовательно проходя по символам входной строки, будем выполнять следующие действия:

· Если текущий символ – открывающая скобка (круглая или квадратная), помещаем её в стек.

· Если текущий символ – закрывающая скобка, то на вершине стека должна находиться соответствующая открывающая скобка. Если это не так, либо если стек пуст, скобочное выражение считается неправильным.

После обработки всей строки стек должен быть пуст – это условие правильности скобочной последовательности.

Пример

Рассмотрим работу алгоритма на примере строки “( ( [ ] ) [ ] )”.

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

Объявим стек s.

stack<char> s;

Читаем количество тестов tests. Пропускаем символ ‘\n’.

cin >> tests;

getline(cin, str);

Последовательно обрабатываем tests тестов.

while (tests--)

{

Читаем входную строку str. Она может быть пустой.

getline(cin, str);

Переменная flag станет равной 1, если входное скобочное выражение не является правильным. Изначально установим flag = 0.

flag = 0;

Перед обработкой очередного теста очищаем стек s.

while(!s.empty()) s.pop();

Двигаемся по символам входной строки str.

for(i = 0; i < str.size(); i++)

{

Заносим в стек открывающуюся скобку.

if ((st[i] == '(') || (str[i] == '[')) s.push(str[i]); else

Если текущий символ str[i] – закрывающаяся скобка, то извлекаем символ из вершины стека, который должен быть соответствующей открывающей скобкой. Если это не так, или если стек пуст, устанавливаем значение переменной flag равным 1.

if (!s.empty() && ((str[i] == ')' && s.top() == '(') ||

(str[i] == ']' && s.top() == '['))) s.pop();

else flag = 1;

}

Если flag = 0 и стек пустой, то скобочное выражение является правильным.

if (flag == 0 && s.empty()) cout << "Yes\n"; else cout << "No\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");

}

}

}