// Ulazni niz s sadrži samo znakove '(', ')', '[', ']' // Odredite da li je ulazni niz validan. // Niz je validan ako: // - Sve otvorene zagrade su zatvorene zagradama istog tipa. // - Zagrade se zatvaraju u pravom redosledu. // - Svaka zatvorena zagrada odgovara otvorenoj zagradi istog tipa // () // 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
}