游客 注册 | 登录
中文 | En

1487 - 括号匹配问题

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

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

题目输入

输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100。
注意：cin.getline(str,100)最多只能输入99个字符！

题目输出

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

输入/输出样例

输入格式

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

输出格式

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

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"); 
    }    
}

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;
}

Java解答

import java.util.*;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		while(sc.hasNextLine())
		{
			String t1=sc.nextLine();
			StringBuffer sb=new StringBuffer(t1);
			StringBuffer t2=new StringBuffer(200);
			for(int i=0;i<t1.length();i++)
			{
				if(t1.charAt(i)=='(')
					t2.append('(');
				else if(t1.charAt(i)==')')
				{
					if(t2.length()>0)
						t2.deleteCharAt(t2.length()-1);
					else
						sb.setCharAt(i, '?');
				}
			}
			t2.setLength(0);
			for(int i=t1.length()-1;i>=0;i--)
			{
				if(t1.charAt(i)==')')
					t2.append(')');
				else if(t1.charAt(i)=='(')
				{
					if(t2.length()>0)
						t2.deleteCharAt(t2.length()-1);
					else
						sb.setCharAt(i, '$');
				}
			}
			for(int i=0;i<sb.length();i++)
			{
				if(sb.charAt(i)!='?' && sb.charAt(i)!='$')
					sb.setCharAt(i, ' ');
			}
			System.out.print(t1);
			System.out.print('\n');
			System.out.print(sb);
			System.out.print('\n');
		}
	}
}
请先登陆