Challenge: Balanced Brackets

Lab C++ Beginner 10 points

Read a line. Print balanced if every ( [ { is closed by the matching bracket in the right order (ignore other characters), otherwise not balanced.

Input

One line of text.

Output

balanced or not balanced.

Example

Input

{[()()]}

Output

balanced

Sample input available Sample output available

Editor

C++

Hints

Push opening brackets.

A closing bracket must match the top; then pop.

The stack must be empty at the end.

Solution explanation

The most recent unclosed bracket is always on top.

Show solution

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    string t;
    getline(cin, t);
    stack<char> s;
    bool ok = true;
    for (char ch : t) {
        if (ch == '(' || ch == '[' || ch == '{') s.push(ch);
        else if (ch == ')' || ch == ']' || ch == '}') {
            char want = ch == ')' ? '(' : ch == ']' ? '[' : '{';
            if (s.empty() || s.top() != want) { ok = false; break; }
            s.pop();
        }
    }
    cout << (ok && s.empty() ? "balanced" : "not balanced") << endl;
    return 0;
}

Output

Answer