栈及其DFS：B

解题心得及总结：
总结：
1、递推：又1推出n，数列中的基本到通项，最终目标得出通项公式。
递归：又n先压缩栈到1，再从函数的出口找到1，又1到n，再从n计算到1；
2、判断是否可以由递推或递推得出，再判断可以用BFS or DFS得出，BFS使用队列（queue），DFS使用栈（stack）。
3、队列，先进先出。如图：

---

栈先进后出，又称先进后出表。
。

例题心得：
1、关键点：队列是否为空，括号是否单项匹配。注意：单项匹配，只能为队列中的左括号和数组中的右括号相互消去。而数列中不能压入右括号，不然直接跳出（可以看作是剪枝）。
2、数列开大一点，汗~~~！
3、这题有坑，输入空格时会输出“Yes”（审题第一个要求）。
4、由于有输入的坑，所以在输入时会纠结，cin，scanf，不能输出空格，只能使用gets（gets可以输入空格和上一个输入的回车），但是在使用gets时会将上一个回车输入导致输入混乱，所以可以在gets前面加一个getchar（）将无用的回车去掉。
5、全局变量中的int、char、long long以及结构体中的元素会自动初始化为0。

例题：
You are given a string consisting of parentheses () and []. A string of this type is said to be correct:
(a) if it is the empty string
(b) if A and B are correct, AB is correct,
(c) if A is correct, (A) and [A] is correct.
Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.

Input
The file contains a positive integer n and a sequence of n strings of parentheses ‘()’ and ‘[]’, one string a line.

Output
A sequence of ‘Yes’ or ‘No’ on the output file.

Sample Input 3
([])
(([()])))
([()])()

Sample Output
Yes
No
Yes

#include<stdio.h>
#include<stack>
 //是c++中的函数，不可以加.h
#include<iostream>
using namespace std;
int main()
{
    char aim[140],now,emp;
    int i,j,n,c,length;
    bool flag = false;
    scanf("%d",&n);;
    getchar();
    while(n--)
    {
        i = 0;
        flag = false;
//判断是否为空格和是否有右括号压入栈中
        stack <char> st;
//栈的定义
        memset(aim,0,sizeof(aim));
        gets(aim);
//注意gets的坑
        length = strlen(aim);
        for(i=0;i<length;i++)
        {
            if(st.empty())
//当栈为空的时候只能够压入，不能取出。
            {
                st.push(aim[i]);
                if(st.top() == ' ')
                {
                    printf("Yes
");
                    flag = true;
                    break;
                }
            }
            else
            {
                if(!st.empty())
                {
                    now = st.top();
                    if(now == ')' || now == ']')
                    {
                        printf("No
");
                        flag = true;
                        break;
                    }
                }
                if(st.empty())
                    continue;
                if(now == '(')
                {
                    if(aim[i] == ')')
                    {
                        st.pop();
                    }
                    else
                        st.push(aim[i]);
                }
                if(now == '[')
                {
                    if(aim[i] == ']')
                    {
                        st.pop();
                    }
                    else
                        st.push(aim[i]);
                }
            }
        }
        if(flag)
            continue;
        if(st.empty())
            printf("Yes
");
        else
            printf("No
");
    }
}