青岛学网站建设的大学,营销网站设计公司有哪些,安卓做网站,去年做那个网站致富题目描述: 现在#xff0c;有一行括号序列#xff0c;请你检查这行括号是否配对。 输入描述: 第一行输入一个数N#xff08;0N100#xff09;,表示有N组测试数据。后面的N行输入多组输入数据#xff0c;每组输入数据都是一个字符串S(S的长度小于10000#xff0c;…题目描述: 现在有一行括号序列请你检查这行括号是否配对。 输入描述: 第一行输入一个数N0N100,表示有N组测试数据。后面的N行输入多组输入数据每组输入数据都是一个字符串S(S的长度小于10000且S不是空串测试数据组数少于5组。数据保证S中只含有[, “]”, “(”, “)” 四种字符 输出描述: 每组输入数据的输出占一行如果该字符串中所含的括号是配对的则输出Yes,如果不配对则输出No 样例输入: 3 [(]) (]) ([]) 样例输出: No No Yes
思路分析
对于括号匹配问题这里运用C的栈操作比较方便。 定义一个变量y用来判断是否匹配成功若成功y1,否则y0最后根据y的值来输出最后的结果。 定义一个字符数组s存储输入的符号
定义一个变量l为字符数组s的最大长度
定义一个变量n为需要判断的组数
定义一个字符类型的栈sq判断是字符数组s里面的元素符号是否是‘’‘{’‘[’若是左半边符号则入栈 如不是则跟已经入栈的栈顶元素进行匹配 若匹配失败y1,结束本次判断 若匹配成功则将该元素符号出栈
最后组数循环完之后判断栈是否为空是否全都匹配成功出栈了若栈不为空则y1匹配失败。然后将栈中其他元素全部出栈。
代码如下
#include iostream
#includestack
#includecstring
#includecstdio
using namespace std;int main()
{int n,i,l,y0; //l为字符数组s的大小长度y1表示匹配失败y0表示匹配成功char s[65536]; //定义一个字符数组用来存待匹配的符号stackcharsq; //定义一个char类型的栈scanf(%d,n); //输入要测试的几组数据while(n--){y0; //这里的y用来判断是否为空栈cins;lstrlen(s);for(i0;il;i){if(s[i](||s[i]{||s[i][) //如果字符数组s里面的字符为左半边符号sq.push(s[i]); //该字符数组s里面的符号进栈else{if(sq.empty()) //如果栈为空{y1; //y1直接说明匹配不成功因为根本没有进左括号break;}}if(s[i]]) //判断字符数组里面的元素是否是 ] 如果是进入下一个判断{if(sq.top()![) //判断栈顶是否是 [{y1; //若不是 [ y1匹配失败break; //结束}else sq.pop(); //若是 [ 将栈顶元素出栈}if(s[i]}) //以次类推{if(sq.top()!{){y1;break;}else sq.pop();}if(s[i])){if(sq.top()!(){y1;break;}else sq.pop();}}if(!sq.empty()) //最后如果栈不为空则匹配失败{y1;}if(y1) printf(No\n);else printf(Yes\n);while(!sq.empty()) //如果栈不空栈顶元素出栈直到栈为空为止{sq.pop();}
}return 0;}
