来自：2017年上海金马五校程序设计竞赛（网上资格赛）


Corn's new language


From: DHUOJ, 2017052401

<a type="button" class="btn btn-warning" href="/solution/submit.html?problemId=5261">Submit</a>
<center> Time Limit: 1 s </center>

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) (P) is a valid program, if P P is a valid program

3. PQ PQ is a valid program, if both P P and Q 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 2, while "((())()) ((())())" has a depth of 3 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 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<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<stack>
using namespace std;
 
int main()
{
    char s[1000000];
    while(cin>>s)
    {   
        stack<char>st;
        bool flag=1;
        int maxn=0;
        int len=strlen(s);
        for(int i=0;i<len;i++){
            if(s[i]=='('){
                st.push(s[i]);
                if(maxn<st.size()){
                    maxn=st.size();
                }
            }
            if(s[i]==')'){
                if(st.size()<=0){
                    flag=0;
                    break;
                }
                st.pop();
            }
        }
        if(st.size()>0)cout<<"NO"<<endl;
        else if(flag==0)cout<<"NO"<<endl;
        else{
            cout<<"YES "<<maxn<<endl;
        }
    }
    return 0;   
}