Balanced Brackets

Lab C Intermediate 20 points

Read a line and print balanced or unbalanced for the brackets ()[]{} using a char stack.

Input

One line.

Output

One word.

Example

Input

{[()()]}

Output

balanced

Sample input available Sample output available

Editor

Hints

Push opening brackets; a closing bracket must match the top.

Solution explanation

Compilers use exactly this check when parsing code.

Show solution

#include <stdio.h>
#include <string.h>

int main() {
    char s[300], stack[300];
    int top = 0, ok = 1;
    fgets(s, 300, stdin);
    for (int i = 0; s[i] != '\0' && ok; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            stack[top] = c;
            top++;
        } else if (c == ')' || c == ']' || c == '}') {
            char open = '{';
            if (c == ')') open = '(';
            else if (c == ']') open = '[';
            if (top == 0 || stack[top - 1] != open) ok = 0;
            else top--;
        }
    }
    printf(ok && top == 0 ? "balanced\n" : "unbalanced\n");
    return 0;
}

Output

Answer