1203：扩号匹配问题时间限制: 1000 ms 内存限制: 65536 KB 提交数: 4373 通过数: 2314 【题目描述】在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注。 【输入】输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100。 【输出】对每组输出数据，输出两行，第一行包含原始输入字符，第二行由"$","?"和空格组成，"$"和"?"表示与之对应的左括号和右括号不能匹配。 【输入样例】【输出样例】【来源】N |
用栈进行解题的思路如下：
1、定义一个数字栈
2、站内存放未配对成功的括号在原字符串中的下标
3、用一个数组对这些下标进行记录（不能直接对栈进行操作，因为栈是后入先出型数据结构）
代码如下：
#include <bits/stdc++.h>
using namespace std;
stack<int> st;
char str[120];
int a[120];
int main()
{int len,i;while(gets(str)){memset(a,0,sizeof(a));len=strlen(str);for(i=0; i<len; i++){if(str[i]=='(')st.push(i);if(str[i]==')'){if(st.empty()){st.push(i);}else{if(str[st.top()]=='('){st.pop();}else{st.push(i);}}}}puts(str);while(!st.empty()){a[st.top()]=1;st.pop();}for(i=0; i<len; i++){if(a[i]){if(str[i]=='(')cout<<"$";elsecout<<"?";}elsecout<<" ";}cout<<endl;}return 0;
}
另一种思路
因为递归说到底毕竟是栈，所以这个思路是不用栈而是用递归。
思路如下：
1、对字符串进行递归
2、递归方式有两种：将字符串从下标0向下标len-1递归；将字符串从下标len-1向下标0递归
（本代码用字符串下标从0向len-1递归）
算法大致流程：
首先定义全局变量len，用来记录字符串当前下标；定义一个整型数组，如果当前字符是括号且未能匹配上，则记录当前下标
1、如果当前下标对应的字符既不是'('也不是')'，那么就不用管
2、如果当前下标对应字符串是'('，那么用整型数组记录
3、如果当前下标对应字符串是')'，从当前下标前一位开始，向0查找第一个'('，如果有，则取消'('的下标记录，如果没有则将')'进行记录
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define MAXN 160char str2[MAXN];
int a[MAXN];
int len;void f()
{if(len==strlen(str2))return ;if(str2[len]=='('){a[len]=1; //记录下标}else if(str2[len]==')'){bool flag=false;for(int i=len-1; i>=0; i--){if(a[i]&&str2[i]=='('){flag=true;a[i]=0;break;}}if(!flag) // 说明没有 '(' 与 ')' 配对{a[len]=1;}}len++;f();return ;}int main()
{while(gets(str2)){memset(a,0,sizeof(a)); len=0;f();puts(str2);for(int i=0; i<strlen(str2); i++){if(a[i]==1){if(str2[i]==')')cout<<"?";elsecout<<"$";}else{cout<<" ";}}cout<<endl;}return 0;
}