Challenge: Balanced Brackets

Lab C++ Advanced 30 points

Read one line made of the brackets ( ) [ ] { }. Print balanced if every opening bracket is closed by the right kind in the right order, otherwise not balanced. Use a stack.

Input

One line of brackets.

Output

balanced or not balanced.

Example

Input

([]{})

Output

balanced

Sample input available Sample output available

Editor

C++

Hints

Push every opening bracket.

For a closing bracket, the top of the stack must be its matching opener: then pop.

At the end the stack must be empty.

Solution explanation

The most recent unclosed bracket is always on top of the stack, which is exactly the one the next closing bracket must match.

Show solution

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

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

Output

Answer