栈及其DFS：B - Parentheses Balance

解题心得及总结：

总结：

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\n");

                    flag = true;

                    break;

                }

            }

            else

            {

                if(!st.empty())

                {

                    now = st.top();

                    if(now == ')' || now == ']')

                    {

                        printf("No\n");

                        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\n");

        else

            printf("No\n");

    }

}

巴特西

栈及其DFS：B - Parentheses Balance

最新文章

热门文章