紫书 习题7-13 UVa 817（dfs+栈求表达式的值）

题目链接  点击打开链接

这道题分为两个部分， 一用搜索枚举每种可能， 二计算表达式的值， 有挺多细节需要注意

特别注意我的代码中在计算表达式的值中用到了一个！（代码枚举中的！表示不加符号， 我现在说的是表达式中的！）， 这个是

虚拟的， 是为了数字栈里面只有一个数字的时候不会被计算，因为计算至少要两个数个时候。 这个时候f函数返回0是不会执行50

行的while的。比如2100-100，这当执行到‘-’时候不能用cal， 因为只有2100一个数字。

具体看代码。

#include<cstdio>
#include<cstring>
#include<cctype>
#define REP(i, a, b) for(int i = (a); i < (b); i++)   //为了偷懒， 主要是小于b, 不是小于等于 
using namespace std;

const char* word = "*+-!";   //这里！表示不加符号， 这个顺序不能错， 是字典序 
char str[20], symbol[20], sign[20];  //symbol是用来存枚举的符号， 而sign是计算表达式用到的存符号栈 
int ok, len, topn, tops, num[20];  //num是计算表达式用到的存数字栈  

bool get_string(char (&s)[20])   //这里是引用数组， 类型名 （&变量名）[N]；  
{
	int pos = 0;
	REP(i, 0, len - 1)   //等号忽略， 所以是len - 1 
	{
		s[pos++] = str[i];
		if(symbol[i] != '!') 
			s[pos++] = symbol[i];
	}
	
	if(s[0] == '0' && isdigit(s[1])) return false;    //这下面一段是判断前导0， 第一个字符特判一下 
	REP(i, 1, pos)
		if(!isdigit(s[i-1]) && s[i] == '0' && isdigit(s[i+1]))   //前面是符号，中间是数字， 后面也是数字
			return false;                                        // 这样不会是单个0， 这样就有前导0 
	return true;
}

void cal()
{
	char t = sign[tops--];
	if(t == '+') num[--topn] += num[topn+1];
	else if(t == '-') num[--topn] -= num[topn+1];
	else num[--topn] *= num[topn+1];
}

int f(char x) { return x == '!' ? 0 : x == '*' ? 2 : 1; } 
														
int get_val(char* s)                                       
{                                                          
	int x = 0;
	topn = tops = 0;
		
	REP(i, 0, strlen(s))
	{
		if(isdigit(s[i])) x	= x * 10 + s[i] - '0';
		else
		{
			num[++topn] = x;
			x = 0;
			while(f(s[i]) <= f(sign[tops])) cal();
			sign[++tops] = s[i];
		}
		if(i == strlen(s) - 1) num[++topn] = x;   //最后一个数不要漏 
	}
		
	while(tops) cal();  //计算遗留下来的符号 
	return num[1];
}

void check_ans()
{
	char s[20];
	if(!get_string(s)) return;
	if(get_val(s) == 2000)
	{
		printf("  %s=
", s);
		ok = true;
	}
}

void search(int d)
{
	if(d == strlen(str) - 2) { check_ans(); return; } 
	REP(i, 0, 4)
	{
		symbol[d] = word[i];
		search(d + 1);
	}
}

int main()
{
	int kase = 0;
	while(scanf("%s", str) && strcmp(str, "="))
	{
		memset(symbol, 0, sizeof(symbol));
		memset(num, 0, sizeof(num));
		memset(sign, 0, sizeof(sign));
		sign[0] = '!';                        //见36行注释 
		
		ok = false;
		len = strlen(str);
		printf("Problem %d
", ++kase);
		if(!strcmp(str, "2000="))            //这里有个坑， 要特判一下 
		{
			puts("  IMPOSSIBLE");
			continue;
		}
		search(0);	
		if(!ok) puts("  IMPOSSIBLE");
	}
	return 0;	
}