2017年上海金马五校程序设计竞赛（网上资格赛） A : Corn's new language（括号匹配+求深度）

Problem A : Corn's new language

From: DHUOJ, 2017052401 (Out of Contest)

Time Limit: 1 s

Description

Corn is going to promote programming in the campus, so he wants to add a lot of interesting ideas to make programming more attractive. One task he is working on is to develop a new programming language because he thinks all existing ones are too simple to him. The syntax rules of the language are:

1. () is a valid program

2. (P) is a valid program, if P is a valid program

3. PQ is a valid program, if both P and Q are valid programs

Corn wants a compiler for the language. For a program, if it is valid, the compiler should print the max depth in the program. For example " (()) " has a depth of 2 , while " ((())()) " has a depth of 3 . Formally, the max depth is the max number of unmatched open brackets in any prefix.

Input

Each case is a non-empty string in a single line, the string will only contain ' ( ' or ' ) ', its length will be no more than 100 .

Output

For each case, output "YES" and the integer required above if the program is valid, separated with a space. Or "NO" if the program is invalid.

Sample Input

(
)
()
(())
((())())
())
((

Sample Output

NO
NO
YES 1
YES 2
YES 3
NO
NO

Author: Tianyi Chen

解题思路：典型的括号匹配（栈加求深度）每次遇到 '('且栈顶为‘）’时，记录下此时栈里的元素个数。

我的代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
int main()
{
    string s;
    while(cin>>s)
    {
        int i,h=0,flag=0,sum=0;
        stack<char>q;
        for(i=0; i<s.size(); i++)
        {
            if(s[i]=='(')//正括号进栈
                q.push(s[i]);
            else//反括号出栈
            {
                if(!q.empty()&&q.top()=='(')
                {

                    if(q.size()>sum)
                        sum=q.size();
                    q.pop();

                }
                else
                    q.push(s[i]);
            }
        }
        //cout<<q.size()<<" sum="<<sum<<endl;
        if(!q.empty())
            printf("NO\n");
        else
            printf("YES %d\n",sum);
    }
    return 0;
}

秒客网