NOI题库2.2括号匹配分析与题解(C++)

1、问题描述问题描述 在某个字符串（长度不超过在某个字符串（长度不超过100）中有）中有左括号、右括号和大小写字母；规定（与常左括号、右括号和大小写字母；规定（与常见的算数式子一样）见的算数式子一样）任何一个左括号都从内任何一个左括号都从内到外与在它右边且距离最近的右括号匹配到外与在它右边且距离最近的右括号匹配。写一个程序，找到写一个程序，找到无法无法匹配的左括号和右括匹配的左括号和右括号，输出原来字符串，并在下一行标出不能号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用匹配的括号。不能匹配的左括号用“$”标注标注,不能匹配的右括号用不能匹配的右括号用“?”标注。标注。输出输出

2、 输入包括输入包括多组数据多组数据，每组数据一行，包，每组数据一行，包含一个字符串，只包含左右括号和大小写字含一个字符串，只包含左右括号和大小写字母，字符串长度不超过母，字符串长度不超过100输入输入 对每组输出数据，输出两行，第一行包对每组输出数据，输出两行，第一行包含原始输入字符，第二行由含原始输入字符，第二行由$,?和和空格空格组组成，成，$和和?表示与之对应的左括号和右括表示与之对应的左括号和右括号不能匹配。号不能匹配。Sample inputSample output(ABCD(x)(rttyy()sss)(ABCD(x) $ )(rttyy()sss)( ? ?$问题分析问题分析

3、本题大致意思就是，对给定的多个字符本题大致意思就是，对给定的多个字符串，输出其中无法匹配的括号标记（左括号串，输出其中无法匹配的括号标记（左括号“$”，右括号右括号“?”），其他字符输出空格，且），其他字符输出空格，且位置严格按照原串。位置严格按照原串。 所以最重要的就是所以最重要的就是找出无法匹配的括号找出无法匹配的括号并标记并标记。问题分析问题分析 那么，如何找呢？那么，如何找呢？ 首先要清楚什么是匹配。题目说，任何首先要清楚什么是匹配。题目说，任何一个左括号都从内到外与在它右边且距离最一个左括号都从内到外与在它右边且距离最近的右括号匹配。近的右括号匹配。(aa()a)bb) ?下图中，相

4、同颜色的括号匹配。下图中，相同颜色的括号匹配。问题分析问题分析 很容易想到，可以假设一开始查找到的很容易想到，可以假设一开始查找到的“(”无法匹配，设为无法匹配，设为“$”，并记录下它的下标并记录下它的下标。其他字符直接设为空格。其他字符直接设为空格。 如此，直到查找到如此，直到查找到“)”，访问它和离它最访问它和离它最近的近的“(”的下标，在原串中设为空格。的下标，在原串中设为空格。 当然，如果找到的当然，如果找到的“(”下标是一个不可能下标是一个不可能的值，例如的值，例如-1，则该则该“)”无法匹配，在原串中无法匹配，在原串中设为设为“?”。(aa()a)bb)$? ?这样就写出了代码：这

5、样就写出了代码：string s;while(getline(cin, S) /读入整行cout S endl; /输出原串int left102,j=0; /left记录所有(在S中的下标，j只是指针memset(left, -1, sizeof(left); /初始化-1for(int i = 0; i = 0) /有匹配的左括号，下标不为-1Sleftj = Si = ; /设空j-; /找上一个左括号elseSi = ?; /未匹配elseSi = ; /其他字符设空cout S endl; /输出（已修改后的S）对吗？对吗？ 如果如果“(”下标从下标从left0开始存储，当第开始存储，当第一个一个“(”匹配完后，匹配完后，j = -1，就会出现就会出现下标下标越界！越界！ 只要修改一句：只要修改一句：leftj+ = i;left+j