3058060_ac_0ms_148k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

int n;
int yes;

void solve(char tree[],int v)
{
	char *p;
	int t;
	int i, left, right;

	if(yes)
		return ;
	tree[strlen(tree)-1] = '\0';
	p = strchr(&tree[1],'(');
	t = atoi(&tree[1]);
	if(strcmp(p,"()()")==0)
	{
		if(v+t==n)
			yes = 1;
		return ;
	}
	left = right = 0;
	for(i = 1; ; i++)
	{
		if(tree[i]=='(')
			left++;
		if(tree[i]==')')
			right++;
		if(left&&left==right)
			break;
	}
	if(strlen(&tree[i+1])!=2)
		solve(&tree[i+1],v+t);
	tree[i+1] = '\0';
	int l = i-(strchr(&tree[1],'(')-tree)+1;
	if(l!=2)
	{
		p = strchr(&tree[1],'(');
		solve(p,v+t);
	}
}

int main()
{
	int left, right;
	char ch;
	char tree[100], l;

	while(scanf("%d",&n)==1)
	{
		l = yes = 0;
		left = right = 0;
		while(1)
		{
			ch = getchar();
			if(ch!='('&&ch!=')'&&ch!='-'&&!isdigit(ch))
				continue;
			tree[l++] = ch;
			if(ch=='(')
				left++;
			if(ch==')')
				right++;
			if(left&&left==right)
				break;
		}
		tree[l] = '\0';
		if(strcmp("()",tree)==0)
		{
			puts("no");
			continue;
		}
		solve(tree,0);
		puts(yes?"yes":"no");
	}
	return 0;
}