2410648_ac_1343ms_40k.cpp

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

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

char exp[110];
char op[] = "+-*/";
int res, p;
int stack[11];

int cal()
{
	char tmp[110], cat[110];
	int i, j, q, s, k, a, b, mark;

	strcpy(tmp,exp);
	mark = 1;
	while(mark)
	{
		mark = 0;
		for(i = 0; tmp[i]!='\0'; i++)
		{
			if(tmp[i]==')')
			{
				mark = 1;
				for(j = i-1; j >= 0; j--)
				{
					if(tmp[j]=='(')
						break;
				}
				for(k = j+1; k < i; k++)
					if(tmp[k]=='*'||tmp[k]=='/')
					{
						b = atoi(&tmp[k+1]);
						if(tmp[k+1]=='0')
							b *= -1;
						q = k-1;
						while(q>=0&&isdigit(tmp[q]))
							q--;
						a = atoi(&tmp[q+1]);
						if(tmp[q+1]=='0')
							a *= -1;
						if(tmp[k]=='*')
							a *= b;
						else
						{
							if(!b)
								return -1000;
							a /= b;
						}
						s = k+1;
						while(tmp[s]!='\0'&&isdigit(tmp[s]))
							s++;
						itoa(a,cat,10);
						if(a<0)
							cat[0] = '0';
						strcat(cat,&tmp[s]);
						strcpy(&tmp[q+1],cat);
						goto bre;
					}
				for(k = j+1; k < i; k++)
					if(tmp[k]=='+'||tmp[k]=='-')
					{
						b = atoi(&tmp[k+1]);
						if(tmp[k+1]=='0')
							b *= -1;
						q = k-1;
						while(q>=0&&isdigit(tmp[q]))
							q--;
						a = atoi(&tmp[q+1]);
						if(tmp[q+1]=='0')
							a *= -1;
						if(tmp[k]=='+')
							a += b;
						else
							a -= b;
						s = k+1;
						while(tmp[s]!='\0'&&isdigit(tmp[s]))
							s++;
						itoa(a,cat,10);
						if(a<0)
							cat[0] = '0';
						strcat(cat,&tmp[s]);
						strcpy(&tmp[q+1],cat);
						goto bre;
					}
					strcpy(&tmp[i],&tmp[i+1]);
					strcpy(&tmp[j],&tmp[j+1]);
bre:
					break;
			}
		}
	}
	return atoi(tmp)*(tmp[0]=='0'?-1:1);
}

int dfs(int v)
{
	int i;

	if(v==p)
		if(cal()==res)
			return 1;
		else
			return 0;
	for(i = 0; i < 4; i++)
	{
		exp[stack[v]] = op[i];
		if(dfs(v+1))
			return 1;
	}
	return 0;
}

void solve()
{
	int i;

	p = 0;
	for(i = 0; exp[i]!='\0'; i++)
	{
		if(exp[i]=='?')
			stack[p++] = i;
	}
	if(dfs(0))
		printf("yes\n");
	else
		printf("no\n");
}

int main()
{
	int n;

	scanf("%d",&n);
	while(n--)
	{
		exp[0] = '(';
		scanf("%s%d",&exp[1],&res);
		strcat(exp,")");
		solve();
	}
	return 1;
}