Проверить скобочное выражение

Дана строка, содержащая три вида скобок : (, ), {, }, [ , ], а также буквы латинского алфавита и цифры. Определите, верно ли скобочное выражение.

Для валидности скобочного выражения необходимо:

Открытые скобки должны быть закрыты однотипными скобками.
Открытые скобки должны быть закрыты в правильном порядке.
Каждой закрывающей скобке соответствует открытая скобка того же типа.

Например,

(sdfkhg234(dfg){}fdgfg){dfg(fg)} -> Верное выражение

)(-> Неверное выражение.
(({}))->Верное.

([})-> Неверное.

Решение. Для решения можно использовать стек. Работу стека можно себе представить, как работу со стобкой книг. Книги можно класть только сверху, нельзя класть их в середину или в самый низ. Брать книги также можно только сверху. Этот принцип называется LIFO (Last In - First Out).

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

Изобразил работу алгоритма и состояние стека для примера ([]):

Реализация на языке Java:

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.peek();
                if ((c == ')' && top != '(') 
                    || (c == '}' && top != '{') 
                    || (c == ']' && top != '[')) {
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();    
    }