Платформа: CodeWars
Название задачи: Valid Parentheses (Допустимые круглые скобки)
Ссылка на задачу: https://www.codewars.com/kata/6411b91a5e71b915d237332d
Сложность: 7 kyu
Уже решили (На момент написания статьи): 11 360 из 30 669
Тэги: Строки, синтаксический анализ, алгоритмы
Оригинальное описание задачи:
Write a function that takes a string of parentheses, and determines if the order of the parentheses is valid. The function should return `true` if the string is valid, and `false` if it's invalid.
Examples
"()" => true
")(()))" => false
"(" => false
"(())((()())())" => true
Constraints
`0 <= length of input <= 100`
- All inputs will be strings, consisting only of characters `(` and `)`.
- Empty strings are considered balanced (and therefore valid), and will be tested.
- For languages with mutable strings, the inputs should not be mutated.
Protip: If you are trying to figure out why a string of parentheses is invalid, paste the parentheses into the code editor, and let the code highlighting show you!
Пояснение задачи:
Необходимо написать функцию, проверяющую корректность последовательности скобок в строке.
Пояснение:
1. Входные данные: строка, состоящая исключительно из символов открывающихся (`(`) и закрывающихся (`)`) скобок.
2. Цель функции — определить, является ли последовательность скобок корректной (балансированной):
- Каждый открывающийся символ должен иметь соответствующий закрывающий.
- Последовательность должна начинаться с открывающих скобок и завершаться закрывающими.
- Нельзя встретить закрывающую скобку раньше соответствующей открывающей.
3. Решение через стек:
- Используем структуру данных «стек», который позволяет эффективно отслеживать соответствие открывающих и закрывающих скобок.
- При встрече открывающейся скобки добавляем её в стек.
- При встрече закрывающейся скобки извлекаем элемент из стека и проверяем, соответствует ли она открывающему символу.
- Если стек становится пустым до завершения проверки или не удается найти соответствующую открывающую скобку, возвращаем `false`.
4. Граничные случаи:
- Пустая строка считается корректной.
- Строка, содержащая только открывающиеся или только закрывающиеся скобки, некорректна.
- Для строки вида `(())`, `(())()` и аналогичных корректны.
Пример:
python def is_valid_parentheses(s: str) -> bool:
Создаем пустой стек для хранения открывающихся скобок
stack = []
Проходим по каждому символу строки
for char in s: if char == '(': Открывающаяся скобка stack.append(char) elif char == ')':
Закрывающаяся скобка if not stack or stack[-1]
'(': Проверяем наличие подходящей открывающей скобки return False stack.pop()
После прохода по всей строке проверяем, остались ли незакрытые скобки return len(stack) == 0
Объяснение примера:
- Строка "()" — корректная, потому что каждый открывающийся символ имеет пару закрывающего.
- Строка ")(()))" — некорректная, потому что сначала встречаем закрывающую скобку, не имеющую пары.
- Строка "(" — некорректная, поскольку не хватает закрывающей скобки.
- Строка "()()()" — корректная, каждая открыв
