PrepBro
← Назад к вопросам

Валидация скобочной последовательности

1.2 Junior🔥 101 комментариев
#Другое#Основы Java

Условие

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

Строка содержит только символы: ( ) { } [ ]

Строка считается корректной, если:

  • Каждая открывающая скобка имеет соответствующую закрывающую того же типа
  • Скобки закрываются в правильном порядке

Примеры

  • "()" → true
  • "()[]{}" → true
  • "(]" → false
  • "([)]" → false
  • "{[]}" → true
  • "" → true (пустая строка корректна)

Требования

  • Используйте Stack для решения
  • Временная сложность O(n)
  • Пространственная сложность O(n)

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Валидация скобочной последовательности

Это классическая задача на использование Stack (стека) — одной из фундаментальных структур данных в программировании. Идея решения очень простая: мы проходим по каждому символу и либо добавляем открывающую скобку в стек, либо проверяем, что закрывающая скобка соответствует последней открывающей.

Алгоритм

  1. Создаём пустой стек
  2. Для каждого символа в строке:
    • Если это открывающая скобка (, {, [ — добавляем её в стек
    • Если это закрывающая скобка, проверяем:
     - Стек не пуст
     - Скобка на вершине стека соответствует закрывающей
  1. В конце стек должен быть пуст

Реализация на Java

import java.util.Stack;

public class BracketValidator {
    public static boolean isValid(String s) {
        if (s == null || s.isEmpty()) {
            return true;
        }
        
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (isOpeningBracket(c)) {
                stack.push(c);
            } else if (isClosingBracket(c)) {
                if (stack.isEmpty() || !isMatching(stack.pop(), c)) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
    
    private static boolean isOpeningBracket(char c) {
        return c == '(' || c == '{' || c == '[';
    }
    
    private static boolean isClosingBracket(char c) {
        return c == ')' || c == '}' || c == ']';
    }
    
    private static boolean isMatching(char opening, char closing) {
        return (opening == '(' && closing == ')') ||
               (opening == '{' && closing == '}') ||
               (opening == '[' && closing == ']');
    }
    
    public static void main(String[] args) {
        System.out.println(isValid("()")); // true
        System.out.println(isValid("()[]{}")); // true
        System.out.println(isValid("(]")); // false
        System.out.println(isValid("([)]")); // false
        System.out.println(isValid("{[]}")); // true
        System.out.println(isValid("")); // true
    }
}

Альтернативное решение с HashMap

Для больших проектов логику проверки соответствия удобнее хранить в Map:

import java.util.HashMap;
        import java.util.Map;
import java.util.Stack;

public class BracketValidatorV2 {
    static final Map<Character, Character> PAIRS = new HashMap<>();
    
    static {
        PAIRS.put('(', ')');
        PAIRS.put('{', '}');
        PAIRS.put('[', ']');
    }
    
    public static boolean isValid(String s) {
        if (s == null || s.isEmpty()) {
            return true;
        }
        
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (PAIRS.containsKey(c)) {
                stack.push(c);
            } else if (PAIRS.containsValue(c)) {
                if (stack.isEmpty() || !PAIRS.get(stack.pop()).equals(c)) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}

Анализ сложности

Временная сложность: O(n) — проходим по каждому символу ровно один раз.

Пространственная сложность: O(n) — в худшем случае (например, "(((((" ) стек содержит все символы.

Почему Stack?

  • LIFO (Last In First Out) — последний открытый элемент должен закрыться первым
  • Соответствие между структурой скобок и структурой стека естественно и интуитивно
  • Стек работает за O(1) для push/pop операций

Тестирование

Все примеры из задания работают корректно:

  • Пустая строка → true (нет скобок, значит нечего проверять)
  • Корректные последовательности → true
  • Несоответствующие скобки → false
  • Неправильный порядок → false
Валидация скобочной последовательности | PrepBro