qwq这个是栈的w
不是树w
qwq我承认我发题很杂啦
字符串匹配问题x
【问题描述】
字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是<>,(),[],{}，例如。输入: [()] 输出:YES，而输入([])， ([])都应该输出NO。
【输入格式】strs.in
文件的第一行为一个整数n，表示以下有多少个由括好组成的字符串。接下来的n行，每行都是一个由括号组成的长度不超过255的字符串。
【输出格式】strs.out
在输出文件中有N行，每行都是YES或NO。
【输入样例】
5
{}{}<><>()()[][]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
【输出标例】
YES
YES
YES
YES
NO
代码如下
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 5 using namespace std; 6 7 struct stack { 8 char strstack[256]; 9 int top; 10 }; 11 12 void InitStack(stack &s) { 13 s.top=-1;//将栈顶元素赋值为-1，便于检验是否空 14 } 15 16 char push(stack &s,char a) { 17 if(s.top==255) { 18 return 0;//说明栈已满 19 } 20 s.top++;//栈顶++ 21 s.strstack[s.top]=a;//将栈顶元素赋值为a 22 return a; 23 } 24 25 char pop(stack &s) { 26 if(s.top==-1) { //如果栈顶空了，则不出栈 27 return 0; 28 } 29 char a=s.strstack[s.top--]; 30 return a;//返回字符检验是否为‘（[{’ 31 } 32 33 int empty(stack &s,int re) { 34 if(s.top==-1) {//如果栈空了，说明暂时匹配，则返回1，为真 35 return 1; 36 } else {//如果没有空，说明暂时不匹配，则返回0，为假 37 return 0; 38 } 39 } 40 41 int check(char *str) { 42 stack s; 43 InitStack(s); 44 int st=strlen(str); 45 for(int i=0; i<st; i++) { 46 char a=str[i]; 47 switch (a) { 48 case '(': 49 case '[': 50 case '{': 51 push(s,a); 52 break; 53 case ')': 54 if(pop(s)!='(') { 55 return 0; 56 } 57 break; 58 case ']': 59 if(pop(s)!='[') { 60 return 0; 61 } 62 break; 63 case '}': 64 if(pop(s)!='{') { 65 return 0; 66 } 67 break; 68 } 69 } 70 int re=0; 71 re=empty(s,re); 72 if(re==1) { 73 return 1; 74 } else { 75 return 0; 76 } 77 } 78 79 int main() { 80 char str[256]; 81 cin>>str; 82 int re=check(str);//用re来传递真假 83 if(re==1) { 84 cout<<"YES"<<endl; 85 } else if(re==0) { 86 cout<<"NO"<<endl; 87 } 88 }