首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#7281

扩号匹配问题(2022.12) 在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且…

扩号匹配问题(2022.12)

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

时间限制:3000

内存限制:65536

输入

输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100

输出

对每组输出数据,输出两行,第一行包含原始输入字符,第二行由"$","?"和空格组成,"$"和"?"表示与之对应的左括号和右括号不能匹配。

样例输入

((ABCD(x)
)(rttyy())sss)(

样例输出

((ABCD(x)
$$
)(rttyy())sss)(
?            ?$
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1:递归 #include &lt;bits/stdc++.h&gt; using namespace std; #define N 105 char s[N], sign[N]; int si, len; void find()//找下一个右括号 如果找到,si指向右括号 如果没找到,做标记  {     int lp = si;//当前左括号的下标      si++;     while(si &lt; len)     {         if(s[si] == ')')             return;         else if(s[si] == '(')             find();         si++;     }     sign[lp] = '$';//没有找到右括号,左括号的位置标记为$  } int main() {  while(cin &gt;&gt; s)  {      len = strlen(s);   for(int i = 0; i &lt; len; ++i)//初始化sign字符串为空格              sign[i] = ' ';         sign[len] = '\0';         si = 0;         while(si &lt; len)         {             if(s[si] == ')')//右括号的位置标记为?                  sign[si] = '?';             else if(s[si] == '(')                 find();             si++;         }         cout &lt;&lt; s &lt;&lt; endl &lt;&lt; sign &lt;&lt; endl;  }  return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2 // 就近原则匹配:栈 // 遍历字符串 // 遇到左括号,将其下标入栈 // 右括号则先判断栈内元素情况 // 1.空,则将其下表记录到数组中 // 2.非空,则栈顶元素弹出(匹配到了) // 将字符串便遍历后,将栈内元素记录入另一个数组 // 用两数组内的对应下标分别改成对应字符 #include &lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5 + 10; string s; char ans[N]; // 第二排的输出数组 stack&lt;int&gt; st; int a[N], cnt = 1; // 未匹配的右括号的下标存储 int b[N], cnn = 1; // 未匹配的左括号的下标存储 int main() {   while (getline(cin, s)) { // 输入不结束     memset(ans, 0, sizeof(ans));     memset(a, 0, sizeof(a));     memset(b, 0, sizeof(b));     cnt = 1;     cnn = 1; // 数据初始化     for (int i = 0; i &lt; s.size(); i++) {       if (s[i] == '(') {         st.push(i); // 左括号统一入栈       }       if (s[i] == ')') {         if (!st.empty()) {           st.pop(); // 若栈非空,则可以匹配         } else {           a[cnt++] = i; // 否则无法匹配,记录         }       }     }     if (!st.empty())       while (!st.empty()) {         b[cnn++] = st.top();         st.pop();       } // 栈内数据(下标)的出栈     for (int i = 1; i &lt; cnn; i++) {       ans[b[i]] = '$'; // 在ans内标记     }     for (int i = 1; i &lt; cnt; i++) {       ans[a[i]] = '?'; // 在ans内标记     }     cout &lt;&lt; s &lt;&lt; endl;     for (int i = 0; i &lt; s.size(); i++) {       if (ans[i] == 0)         cout &lt;&lt; " ";       if (ans[i] == '$')         cout &lt;&lt; "$";       if (ans[i] == '?')         cout &lt;&lt; "?"; // 格式转化     }     cout &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。