Базовая рекурсия, проверка сбалансированных скобок

Question

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

Хорошие примеры: () [] () ([] () [])

Плохие примеры: ((] ([)]

Предположим, моя функция называется: isBalanced.

Должен ли каждый проход оценивать меньшую подстроку (до достижения базового случая 2 слева)? Или я должен всегда оценивать всю строку и перемещать индексы внутрь?

Answer 1

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