POJ3704 括号匹配问题

130 阅读 0 评论 86 点赞

我是靠谱客的博主眼睛大烧鹅，最近开发中收集的这篇文章主要介绍POJ3704 括号匹配问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

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

输入样例
((ABCD(x)
)(rttyy())sss)(

输出样例
((ABCD(x)
$$
)(rttyy())sss)(
? ?$

提示
读取多组数据时，可采用如下方法，其他scanf读到文件尾时会返回值EOF。
char s[205];
while(scanf("%s",s)!=EOF){}

本题的思路是采用一个状态数组，用来记录字符串上各个位置的状态，本题很明显，只有三种状态，一种是输出不能被匹配的左括号错误，一种是输出不能被匹配的右括号错误，一种是输出能被匹配的左右括号以及其他字符。
那么该怎么来处理这个字符串呢？设置状态数组，第一步先扫描整个字符串，遇到左括号，标记为1，遇到右括号，标记为-1，遇到其他字符，标记为0。
接着来处理括号能否被匹配的问题，首先我们想到，同样是扫描整个状态数组，将1和-1匹配后消除为0，方案是先找到第一个右括号，然后指针回退一步，接着遍历，如果找到了1就消0.
AC代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXLEN 105
/*
在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；
规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。
写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。
不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.
多case
*/
using namespace std;
int main()
{
char s[MAXLEN]="";
int vis[MAXLEN]={0};/*括号匹配状态数组*/
while(scanf("%s",s)!=EOF)/*多case型输入*/
{
int LEN=strlen(s);
for(int i=0;i<LEN;i++)
{
if(s[i]=='(')//左括号匹配，记录数组状态
{
vis[i]=1;
}
else if(s[i]==')')//右括号匹配
{
vis[i]=-1;
}
else//其他字符，
{
vis[i]=0;
}
}
for(int i=0;i<LEN;i++)
{
if(vis[i]==-1)/*检测到右括号*/
{
for(int j=i-1;j>=0;j--)
{
if(vis[j]==1)/*检测到左括号*/
{
vis[i]=0;
vis[j]=0;
break;//注意不要写反
}
}
}
}
printf("%sn",s);
for(int i=0;i<LEN;i++)
{
if(vis[i]==0)
{
printf(" ");
}
else if(vis[i]==1)
{
printf("$");
}
else if(vis[i]==-1)
{
printf("?");
}
}
printf("n");
}
return 0;
}
/*
输入格式
输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100。
输出格式
对每组输出数据，输出两行。
第一行包含原始输入字符，第二行由"$","?"和空格组成，"$"和"?"表示与之对应的左括号和右括号不能匹配。
*/