Проверка правильности расстановки скобок разного типа в строке - Разбор алгоритмической задачи

Задача:

Проверить, правильно ли закрываются скобки ()[]{}
Например:
()[]{} - правильно
([{}[]])() -правильно
({]){} - неправильно

Основная идея

Используем структуру стэка:

1. Кладем в стэк открывающие скобки
2. Выщёлкиваем из стэка эти открывающие скобки, если нашли соответствующую закрывающую (того же типа)

Ну и дополнительные моменты:

• Для каждой закрывающей скобки в стэке должно что-то быть (совпадение количеств)
• Если мы встретили закрывающую скобку одного типа, а наверху стэка лежит открывающая другого - то это ошибка (завершаем обработку), значит скобки расставлены неправильно
• Если мы прочитали всю строчку, то стэк должен стать пустым - тогда скобки расставлены правильно

Возможная реализация в коде

На примере Golang-а:

package main

import "fmt"

func isValidBrackets(s string) bool {
	// Карта соответствия закрывающей скобки открывающей
	brackets := map[rune]rune{
		')': '(',
		']': '[',
		'}': '{',
	}

	// тут будем хранить открывающие скобки
	var stack []rune

	for _, char := range s {
		// Если это закрывающая скобка
		if opening, ok := brackets[char]; ok {
			// Проверяем: стек не пуст и на вершине подходящая открывающая
			if len(stack) > 0 && stack[len(stack)-1] == opening {
				stack = stack[:len(stack)-1] // Удаляем из стека (Pop)
			} else {
				return false // Либо лишняя закрывающая, либо не тот тип
			}
			// если допустимы иные символы, чтобы проигнорировать их
			// проверим перед отправкой в стэк, что это именно
			// открывающая скобка
		} else if char == '(' || char == '[' || char == '{' {
			// Если открывающая — кладем в стек (Push)
			stack = append(stack, char)
		}
	}

	// Если стек пуст — все скобки нашли пару
	return len(stack) == 0
}

func main() {
	// Тестовые случаи
	testCases := []string{
		"()",
		"()[]{}",
		"(]",
		"([{}])",
		"((()))",
		"({[}])",
		"",
		"(((",
		")))",
		"()[{} ]",
		"([)]",
	}

	for _, test := range testCases {
		result := isValidBrackets(test)
		fmt.Printf("'%s' -> %t\n", test, result)
	}
}

-- range для строки в golang сразу перебирает руны (подходит для юникода)

Анализ сложности

• O(N) - линейная по количеству чтений символов строки, относительно ее длины
• O(N) и по памяти - тоже линейная (относительно размера стэка) - в худщем случае, для строки, состоящей только из открывающих скобок