Description

You are given a string that contains dozens of brackets.

A valid string is a string such that every bracket in it is matched with another bracket.

For example, an empty string is a valid string.

Generally, a string is valid if one of the below's conditions is satisfied:

• The string is empty.
• The string starts with a left bracket and ends with a right bracket, and the string enclosed by these two brackets is valid.
• The string is two valid string's concatenation.

Your task is that, determine if the given string is valid, and you have to answer it for \(T\) times.

You may use the template below

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

#define MAXN 505 

int record[MAXN][MAXN];
char s[MAXN];

int solve(int l, int r) {
    // return 1 if s[l, r] is valid, 0 otherwise.
    if (record[l][r] != -1) return record[l][r]; // If the substring is computed, return it immediately.
    int flag = 0; // store your answer for this state in flag.
    // [TODO] Implement your codes here.
    // Noticed that you only need to store the result in "flag".

    // End 
    record[l][r] = flag;
    return flag;
}

int main () {
    int T;
    scanf("%d", &T);
    while (T--) {
        for (int i = 0;i < MAXN; ++i)
            for (int j = 0;j < MAXN; ++j)
                record[i][j] = -1;
        scanf("%s", s);
        int flag = solve(0, strlen(s)-1);
        printf(flag ? "Yes\n" : "No\n");
    }
    return 0;
}

Input

The first line contains a integer \(T\).

The next \(T\) lines, each contains string consists of brackets only.

Constraints

• \(1 \le T \le 10\)
• \(1 \le |s| \le 500\)

Output

Print \(T\) line, "Yes" if the string is valid, "No" otherwise.

Sample Input  Download

Sample Output  Download

Tags

Discuss