Balanced Brackets

Lab C++ Intermediate 20 points

Read a line and print balanced or unbalanced for ()[]{} using std::stack.

Input

One line.

Output

One word.

Example

Input

{[()()]}

Output

balanced

Sample input available Sample output available

Editor

C++

Hints

push opening brackets; a closing bracket must match top().

Solution explanation

std::stack is an adapter over deque exposing only stack operations.

Show solution

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

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

Output

Answer