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