// Er wordt een string s ingevoerd die alleen de tekens '(', ')', '[', ']' bevat // Bepaal of de invoerstring geldig is. // De string is geldig als: // - Alle open haakjes worden gesloten door haakjes van hetzelfde type. // - Haakjes moeten in de juiste volgorde worden gesloten. // - Elk sluitend haakje komt overeen met een open haakje van hetzelfde type // () // func isValid(s string) bool { // }

Для проверки валидности строки со скобками можно использовать стек. Идея в том, что при встрече открывающей скобки мы кладём её в стек, а при встрече закрывающей — проверяем, соответствует ли она последней открытой (верхнему элементу стека). Если нет — строка невалидна. В конце стек должен быть пуст.

Пример на Go:

type stack []rune

func (s *stack) push(r rune) {
    *s = append(*s, r)
}

func (s *stack) pop() (rune, bool) {
    if len(*s) == 0 {
        return ' ', false
    }
    index := len(*s) - 1
    elem := (*s)[index]
    *s = (*s)[:index]
    return elem, true
}

func isValid(s string) bool {
    var st stack
    pairs := map[rune]rune{')': '(', ']': '['}

    for _, ch := range s {
        switch ch {
        case '(', '[':
            st.push(ch)
        case ')', ']':
            top, ok := st.pop()
            if !ok || pairs[ch] != top {
                return false
            }
        }
    }
    return len(st) == 0
}