ACM:UESTC - 649 括号配对问题 - stack

Time Limit: 1000MS   Memory Limit: 65535KB   64bit IO Format: %lld & %llu

Description

大家都知道算术表达式中,括号必须配对,现在任意给出一个算术表达式,判断其括号是否配对。如果配对,输出Yes,否则输出No

Input

含多组测试数据,输入首先是一个整数ACM:UESTC - 649  括号配对问题 - stackT表示测试数据组数(ACM:UESTC - 649  括号配对问题 - stackACM:UESTC - 649  括号配对问题 - stackACM:UESTC - 649  括号配对问题 - stackACM:UESTC - 649  括号配对问题 - stackACM:UESTC - 649  括号配对问题 - stackACM:UESTC - 649  括号配对问题 - stackACM:UESTC - 649  括号配对问题 - stack0<T≤300)。随后有ACM:UESTC - 649  括号配对问题 - stackT行测试数据,长度不超过ACM:UESTC - 649  括号配对问题 - stackACM:UESTC - 649  括号配对问题 - stackACM:UESTC - 649  括号配对问题 - stackACM:UESTC - 649  括号配对问题 - stack1000个字符,字符串间不含空格。

Output

对应每组测试数据,输出一行结果。

Sample Input


32(78-23)+78 
32
78)-(23+78)

Sample Output

Yes 
No

Hint

 

Source

wxiaoping - 2012
 
 
/*/
简单的括号配对问题 先把给出的数字串全部变成括号串,在用栈去压入括号,每次保存栈顶括号,如果栈顶括号能和下一个括号配对,就把栈顶弹出,指括号的指针后移。 最后判断栈内是否还有元素,如果有,就说明配对不成功。 AC代码:
/*/
#include"algorithm"
#include"iostream"
#include"cstring"
#include"cstdlib"
#include"cstdio"
#include"string"
#include"vector"
#include"stack"
#include"queue"
#include"cmath"
#include"map"
using namespace std;
typedef long long LL ;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define FK(x) cout<<"["<<x<<"]\n"
#define memset(x,y) memset(x,y,sizeof(x))
#define memcpy(x,y) memcpy(x,y,sizeof(x))
#define bigfor(T) for(int qq=1;qq<= T ;qq++) const int MX=1e5+1e3; char s[MX],cc[MX],t[MX]; stack<char> st; bool check() {
int len = strlen(cc);
while(!st.empty())st.pop();
int i=0;
char stc;
while(i<len) {
st.push(cc[i++]);
stc=st.top();
while(stc=='('&&cc[i]==')'){
st.pop();
i++;
if(st.empty())break;
stc=st.top();
}
}
if(st.empty())return 0;
return 1;
} int main() {
int T;
t[0]='(',t[1]=')',t[2]='\0';
scanf("%d",&T);
bigfor(T) {
scanf("%s",s);
int len=strlen(s);
int erear=0;
for(int i=0; i<len; i++) {
if(s[i]=='('||s[i]==')') {
cc[erear++]=s[i];
}
}
cc[erear]='\0';
if(check()) {
puts("No");
} else puts("Yes");
}
return 0;
}

  

 
上一篇:NYOJ之括号配对问题


下一篇:nyoj 2 括号配对问题