九度题目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;
}