Task 42. Баланс скобок
UniLecsЗадача: имеется строка, содержащая скобки ( ) и { }. Скобочное выражение считается правильным, если:
- для каждой открывающей скобки справа от нее есть соот-щая закрывающая скобка и наоборот.
- Соответствующие пары скобок разным типов правильно вложены друг в друга.
Длина строки не больше 128 символов. Проверить баланс скобок в заданной строке.
Например:
({(){}()})() - баланс скобок
({(}){}) - баланс скобок нарушен
Идея: в общем случае подобного рода задачу удобно решать с помощью стека, где всегда доступен только последний добавленный элемент.
Если текущий символ строки - левая скобка, то добавим ее в стек. Если текущий символ - правая скобка, то сравним его с последним добавленным элементом в стек. Если мы нашли соот-вие: открывающую и закрывающую скобку одного типа, то удалим последний добавленный символ в стек. В противном случае баланс скобок нарушен и мы можем закончить перебор строки. Либо после проверки всей строки, если стек будет не пустой, то мы также можем сказать, что баланс скобок нарушен.
Реализация:
https://gist.github.com/unilecs/cf57b6a849d983bbf6dc79587d66ff44
Тест: