DHUOJ 2017052401 - Corn's new language（栈 括号匹配）
来自：2017年上海金马五校程序设计竞赛（网上资格赛）
Corn's new language
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;
}
查看9道真题和解析
