Balanced String Parentheses Solution

Problem

You are given a string $S$ which contains only the characters '{', '}', '[', ']', '(' and ')'. Now you wants to know if the given string $S$ is beautiful or not. If $S$ is beautiful then print $1$, otherwise print $0$.

A beautiful parenthesis string is defined as follows:

• The empty string is beautiful
• If P is beautiful then (P), {P}, [P] is also beautiful
• If P and Q are beautiful PQ is also beautiful

For example "([])", "({})[()]" are beautiful parenthesis strings while "([{]})", "())" are not beautiful .

Input:

• The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• The first and only line of each test case contains a single string $S$.

Output

For each test case, print a single line containing the answer.

Constraints

• $1 \leq T \leq 10$
• $1 \leq |S| \leq 10^5$

Example Input

4
()
([)]
([{}()])[{}]
[{{}]

Example Output

1
0
1
0

Explanation

Example case 1: "()" is a beautiful string.

Example case 2: "([)]" is not a beautiful string as the subset of brackets enclosed within '(' and ')' is not beautiful .

Program :

 #include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

#define MAX_SIZE 100001

struct stack {

    char stk[MAX_SIZE];

    int top;

} s;

void push(char c) {

    if (s.top < MAX_SIZE) {

        s.stk[++s.top] = c;

    }

}

char pop() {

    if (s.top > -1) {

        return  s.stk[s.top--];

    } else {

        return -1;

    }

}

int balancedParentheses(char *s, int length) {

    char target, c;

    if (length % 2 != 0) {

        return 0;

    }

    for(int i = 0; i < length; i++) {

        if ((s[i]=='(') || (s[i]=='{') || (s[i]=='[')) {

            push(s[i]);

        } else {

            switch(s[i]) {

                case ')': target = '('; break;

                case '}': target = '{'; break;

                case ']': target = '['; break;

            }

            c = pop();

            if (c == -1 || c != target) {

                return 0;

            }

        }

    }

    return pop() == -1;

}

int main() {

    int t, length;

    char str[MAX_SIZE], c;

    scanf("%d\n", &t);

    for (int i = 0; i < t; i++) {

        s.top = -1;

        length = 0;

        for (;;) {

            c = getchar();

            if (c == EOF || c == '\n') {

                break;

            }

            str[length] = c;

            length++;

        }

        printf("%s\n", balancedParentheses(str, length) == 0 ? "0" : "1");

    }

    return 0;

}