Проверить правильность расстановки скобок

Question

Совсем не могу понять как это реализовать.Для введённой пользователем с клавиатуры строки (максимальная длина строки — 80 символов) программа должна определить, корректно ли расставлены скобки (круглые, фигурные, квадратные) или нет. Перемешивание скобок (пример: «{[}]») считается некорректным вариантом.

Answer 1

Решение довольно просто, достаточно внимательнее посмотреть на исходные данные. Эти данные можно представить в качестве операций над стэком: открывающая скобка - push, закрывающая скобка - pop. Единственное что перед pop-ом нужно проверить, что удаляемая скобка имеет такой же тип.

Answer 2

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

// g++ -std=c++11 -pedantic -Wall -Wextra parens.cpp

#include <iostream>
#include <stack>

bool balanced(const std::string &s) {
    std::stack<char> stack;
    for (char c : s) {
        switch (c) {

        case '(': stack.push(')'); break;
        case '[': stack.push(']'); break;
        case '{': stack.push('}'); break;
        case '<': stack.push('>'); break;

        case ')':
        case ']':
        case '}':
        case '>':
            if (stack.empty() || stack.top() != c) {
                return false;
            }
            stack.pop();
            break;
        default:
            break;
        }
    }
    return stack.empty();
}

void test(const std::string& s) {
    std::cout << '"' << s << "\" " << (balanced(s) ? "yes" : "no") << '\n';
}

int main() {
    test("");
    test("a(b[c]d)e");
    test("a(b[c)d]e");
    test("a(b[c]d");
    test("b[c]d)e");
}

"" yes
"a(b[c]d)e" yes
"a(b[c)d]e" no
"a(b[c]d" no
"b[c]d)e" no

БЛОГ НА HUSL

Проверить правильность расстановки скобок

Ответы (2 шт):