简答题
偏难
#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 <bits/stdc++.h>
using namespace std;
#define N 105
char s[N], sign[N];
int si, len;
void find()//找下一个右括号 如果找到,si指向右括号 如果没找到,做标记
{
int lp = si;//当前左括号的下标
si++;
while(si < len)
{
if(s[si] == ')')
return;
else if(s[si] == '(')
find();
si++;
}
sign[lp] = '$';//没有找到右括号,左括号的位置标记为$
}
int main()
{
while(cin >> s)
{
len = strlen(s);
for(int i = 0; i < len; ++i)//初始化sign字符串为空格
sign[i] = ' ';
sign[len] = '\0';
si = 0;
while(si < len)
{
if(s[si] == ')')//右括号的位置标记为?
sign[si] = '?';
else if(s[si] == '(')
find();
si++;
}
cout << s << endl << sign << endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//解法2
// 就近原则匹配:栈
// 遍历字符串
// 遇到左括号,将其下标入栈
// 右括号则先判断栈内元素情况
// 1.空,则将其下表记录到数组中
// 2.非空,则栈顶元素弹出(匹配到了)
// 将字符串便遍历后,将栈内元素记录入另一个数组
// 用两数组内的对应下标分别改成对应字符
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
string s;
char ans[N]; // 第二排的输出数组
stack<int> 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 < 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 < cnn; i++) {
ans[b[i]] = '$'; // 在ans内标记
}
for (int i = 1; i < cnt; i++) {
ans[a[i]] = '?'; // 在ans内标记
}
cout << s << endl;
for (int i = 0; i < s.size(); i++) {
if (ans[i] == 0)
cout << " ";
if (ans[i] == '$')
cout << "$";
if (ans[i] == '?')
cout << "?"; // 格式转化
}
cout << endl;
}
return 0;
}</pre>
这道题暂未补解析。