《noi题库2.2括号匹配分析与题解(c)》由会员分享，可在线阅读，更多相关《noi题库2.2括号匹配分析与题解(c)（11页珍藏版）》请在金锄头文库上搜索。
1、NOI题库 2.2-括号匹配,问题描述,在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用“$”标注,不能匹配的右括号用“?”标注。,输出,输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100,输入,对每组输出数据，输出两行，第一行包含原始输入字符，第二行由“$“,“?“和空格组成，“$“和“?“表示与之对应的左括号和右括号不能匹配。,问题分析,
2、本题大致意思就是，对给定的多个字符串，输出其中无法匹配的括号标记（左括号“$”，右括号“?”），其他字符输出空格，且位置严格按照原串。 所以最重要的就是找出无法匹配的括号并标记。,问题分析,那么，如何找呢？ 首先要清楚什么是匹配。题目说，任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。,(aa()a)bb) ?,下图中，相同颜色的括号匹配。,问题分析,很容易想到，可以假设一开始查找到的“(”无法匹配，设为“$”，并记录下它的下标。其他字符直接设为空格。 如此，直到查找到“)”，访问它和离它最近的“(”的下标，在原串中设为空格。 当然，如果找到的“(”下标是一个不可能的值，例如-1，则
3、该“)”无法匹配，在原串中设为“?”。,(aa()a)bb),$,$,$,?,?,这样就写出了代码：,string s; while(getline(cin, S) /读入整行 cout S endl; /输出原串 int left102,j=0; /left记录所有“(“在S中的下标，j只是指针 memset(left, -1, sizeof(left); /初始化-1 for(int i = 0; i S.size(); i+) /查找 if(Si = () /找到“(“ leftj+ = i; /记录下标 Si = $; /假设该括号未匹配 ,else if(Si = ) /找到“)“ if(leftj = 0) /有匹配的左括号，下标不为-1 Sleftj = Si = ; /设空 j-; /找上一个左括号 else Si = ?; /未匹配 else Si = ; /其他字符设空 cout S endl; /输出（已修改后的S） ,对吗？,如果“(”下标从left0开始存储，当第一个“(”匹配完后，j = -1，就会出现下标越界！,只要修改一句：,leftj+ = i;,left+j = i;,完成。,本算法时间复杂度O(n),本题相当于普及组12题难度,Thanks for watching.,By yjp,
