350
技術社區[雲棲]
九度題目1153：括號匹配問題
題目1153：括號匹配問題
時間限製：1 秒
內存限製：32 兆
特殊判題：否
提交：2965
解決：1315
題目描述：
在某個字符串（長度不超過100）中有左括號、右括號和大小寫字母；規定（與常見的算數式子一樣）任何一個左括號都從內到外與在它右
邊且距離最近的右括號匹配。寫一個程序，找到無法匹配的左括號和右括號，輸出原來字符串，並在下一行標出不能匹配的括號。不能匹配的
左括號用"$"標注,不能匹配的右括號用"?"標注.
輸入：
輸入包括多組數據，每組數據一行，包含一個字符串，隻包含左右括號和大小寫字母，字符串長度不超過100。
注意：cin.getline(str,100)最多隻能輸入99個字符！
輸出：
對每組輸出數據，輸出兩行，第一行包含原始輸入字符，第二行由"$","?"和空格組成，"$"和"?"表示與之對應的左括號和右括號不能匹配
。
樣例輸入：
)(rttyy())sss)(
樣例輸出：
)(rttyy())sss)(
? ?$
來源：
2010年北京大學計算機研究生機試真題
棧的應用
AC代碼：
1.數組棧
#include<stdio.h>
#include<algorithm>
#include<stack>
#include<string.h>
#include<ctype.h>
using namespace std;
char a[200];
char s1[200];
int s2[200],s3[200];
int top1,top2,top3;
int main()
{
int i,j,n,m;
int num[200];
int sign[200];
while(scanf("%s",a)!=EOF)
{
n=strlen(a);
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
memset(s3,0,sizeof(s3));
top1=0;top2=0;top3=0;
for(i=0;i<n;i++)
{
if(!(isalpha(a[i])))
{
if(s1[top1-1]=='('&&a[i]==')'&&i!=0)
{
top1--;
top2--;
top3--;
}
else
{
s1[top1++]=a[i];
s2[top2++]=i;
if(a[i]=='(')
s3[top3++]=1;
else
s3[top3++]=2;
}
}
}
m=0;
memset(num,0,sizeof(num));
while(top2>0&&top3>0)
{
num[s2[top2-1]]=1;
sign[s2[top2-1]]=s3[top3-1];
top2--;
top3--;
}
puts(a);
for(i=0;i<n;i++)
{
if(num[i]==1)
{
if(sign[i]==1)
printf("$");
else
printf("?");
}
else
printf(" ");
}
puts("");
memset(a,0,sizeof(a));
}
return 0;
}
2.STL中的棧（但是Runtime Error，不知道為什麼）
Runtime Error代碼：
#include<stdio.h>
#include<algorithm>
#include<stack>
#include<string.h>
#include<ctype.h>
using namespace std;
char a[200];
int main()
{
int i,j,n,m;
int num[200];
int sign[200];
stack<char> s1;
stack<int> s2;
stack<int> s3;
while(scanf("%s",a)!=EOF)
{
n=strlen(a);
for(i=0;i<n;i++)
{
if(!(isalpha(a[i])))
{
if(i!=0&&s1.top()=='('&&a[i]==')')
{
s1.pop();
s2.pop();
s3.pop();
}
else
{
s1.push(a[i]);
s2.push(i);
if(a[i]=='(')
s3.push(1);
else
s3.push(2);
}
}
}
m=0;
memset(num,0,sizeof(num));
while(!s2.empty())
{
num[s2.top()]=1;
sign[s2.top()]=s3.top();
s2.pop();
s3.pop();
}
puts(a);
for(i=0;i<n;i++)
{
if(num[i]==1)
{
if(sign[i]==1)
printf("$");
else
printf("?");
}
else
printf(" ");
}
puts("");
memset(a,0,sizeof(a));
}
return 0;
}
最後更新：2017-04-03 05:39:34