1487 - 括号匹配问题

bge)))))))))
((IIII))))))
()()()()(uuu
))))UUUU((()

bge)))))))))
   ?????????
((IIII))))))
        ????
()()()()(uuu
        $   
))))UUUU((()
????    $$  

Hint

 算法思想：
括号匹配是典型的栈的应用，因此可以采用链栈，思路如下：
（1）第一次遍历输入字符串，
        1.是左括号，则入栈，同时标记数组的相应位置置空格
        2.是右括号，则检测栈是否为空，不为空，则判断有对应的左括号，同时出栈；为空，则没有对应的左括号，标记数组置‘？’
（2）第二次遍历输入字符串，
        1.是右括号，则入栈。
        2.是左括号，则检测栈是否为空，不为空，则判断有对应的右括号，同时出栈；为空，则没有对应的左括号，标记数组置‘$’。

Solution C

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
  
struct bracket  
{  
    char data[101];  
    int top;  
};  
  
void main()  
{  
    char str[101],flag[101];  
    int i,len;  
    struct bracket *p, *q;  
  
    while(scanf("%s",str) != EOF)  
    {   
        p=(struct bracket *)malloc(sizeof(struct bracket));  
        q=(struct bracket *)malloc(sizeof(struct bracket));  
        p->top = q->top = 0;  
        len = strlen(str);  
        for(i=0;i<len;i++)  
        {  
            switch(str[i])  
            {  
                case '(' :  
                    p->data[p->top++] = str[i];  
                    flag[i]=' ';  
                    break;  
                case ')' :  
                    if(p->top>0)  
                    {  
                        flag[i]=' ';  
                        p->top-=1;  
                    }else  
                    {  
                        flag[i]='?';  
                    }  
                    break;  
                default :  
                    flag[i]=' ';  
                    break;  
            }  
        }  
        for(i=len-1;i>=0;i--)  
        {  
            switch(str[i])  
            {  
                case ')' :  
                    q->data[q->top++] =str[i];  
                    break;  
                case '(' :  
                    if(q->top>0)  
                    {  
                        q->top-=1;  
                    }else  
                    {  
                        flag[i]='$';  
                    }  
                    break;  
                default :  
                    break;  
            }  
        }    
		for(i=0;i<len;i++)
			printf("%c",str[i]);
		printf("\n");
		for(i=0;i<len;i++)
			printf("%c",flag[i]);
		printf("\n"); 
    }    
}  

Solution C++

#include <stdio.h>
#include <string.h>
char s[111];
void run()
{
	int k=0,i,n;
	char o[111];
	printf("%s\n",s);
	n=strlen(s)-1;
	strcpy(o,"");
	for(i=0;i<=n;i++)
		strcat(o," ");
	k=0;
	for(i=0;i<=n;i++)
	{
		if(s[i]=='(')
			k++;
		if(s[i]==')')
		{
			if(k>0)
				k--;
			else
				o[i]='?';
		}
	}
	k=0;
	for(i=n;i>=0;i--)
	{
		if(s[i]==')')
			k++;
		if(s[i]=='(')
		{
			if(k>0)
				k--;
			else
				o[i]='$';
		}
	}
	printf("%s\n",o);
}
int main()
{
	gets(s);
	while(strlen(s)!=0)
	{
		run();
		strcpy(s,"");
		gets(s);
	}
	return 0;
}