游客 注册 | 登录
中文 | En

2365 - 等价表达式

通过次数

0

提交次数

0

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

明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。

这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？

这个选择题中的每个表达式都满足下面的性质：

1．表达式只可能包含一个变量‘a’。

2．表达式中出现的数都是正整数，而且都小于10000。

3．表达式中可以包括四种运算‘+’（加），‘-’（减），‘*’（乘），‘^’（乘幂），以及小括号‘(’，‘)’。小括号的优先级最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符‘+’，‘-’，‘*’，‘^’以及小括号‘(’，‘)’都是英文字符）

4．幂指数只可能是1到10之间的正整数（包括1和10）。

5．表达式内部，头部或者尾部都可能有一些多余的空格。

下面是一些合理的表达式的例子：

((a^1) ^ 2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1 + (a -1)^3，1^10^9...


题目输入

每组输入数据的第一行给出的是题干中的表达式。第二行是一个整数n（2<=n<=26），表示选项的个数。后面n行，每行包括一个选项中的表达式，表达式中没有空格。这n个选项的标号分别是A，B，C，D...

输入中的表达式的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的。 


<span style="line-height:1.5;">数据规模：</span> 


<span style="line-height:1.5;">对于30%的数据，表达式中只可能出现两种运算符‘+’和‘-’；</span> 


<span style="line-height:1.5;">对于其它的数据，四种运算符‘+’，‘-’，‘*’，‘^’在表达式中都可能出现。</span> 


<span style="line-height:1.5;">对于全部的数据，表达式中都可能出现小括号‘(’和‘)’。</span> 


<span style="line-height:1.5;"><br />


<span style="line-height:1.5;"></span>

题目输出

每组输出包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。


输入/输出样例

输入格式

(a+1)^2
3
(a-1)^2+4*a
a+1+a
a^2+2*a*1+1^2+10-10+a-a

输出格式

AC

C++解答

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <stack>
using namespace std;

const int N = 27, MOD = 0x7fffffff;
long long Std_Value[N], v[N];
string s;
istringstream ss;

struct State
{
	long long v, c1, c2;
	char c3;
	
	State() {}
	State(long long V, long long C1, long long C2, char C3) {v = V; c1 = C1; c2 = C2; c3 = C3;}
} C;
stack<State> st[N];
long long Pow(long long a, int b)
{
	long long c = 1;
	while (b)
	{
		if (b & 1) c = c * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return c;
}
void Calc()
{
	int i, c4;
	long long c1[N], c2[N] = {0};
	char c, c3[N];
	
	fill(c1, c1 + N, 1);
	fill(v, v + N, 0);
	fill(c3, c3 + N, '+');
	ss.str(s);
	while (ss >> c)
	{
		if (c == '^') ss >> c4;
		for (i = 0; i < N; i++)
			switch (c)
			{
				case '(': 
					st[i].push(State(v[i], c1[i], c2[i], c3[i]));
					v[i] = c2[i] = 0; c1[i] = 1; c3[i] = '+';
					break;
				case ')':
					C = st[i].top(); st[i].pop();
					if (c3[i] == '+') c2[i] = (v[i] + c1[i] * c2[i] % MOD) % MOD;
					else c2[i] = (v[i] - c1[i] * c2[i] % MOD) % MOD;
					c1[i] = C.c1; c3[i] = C.c3; v[i] = C.v;
					break;
				case '+':
				case '-':
					if (c3[i] == '+') v[i] = (v[i] + c1[i] * c2[i] % MOD) % MOD;
					else v[i] = (v[i] - c1[i] * c2[i] % MOD) % MOD;
					c1[i] = 1; c2[i] = 0; c3[i] = c; break;
				case '*': c1[i] = c1[i] * c2[i] % MOD; c2[i] = 0; break;
				case '^': c2[i] = Pow(c2[i], c4); break;
				case 'a': c2[i] = i; break;
				default: c2[i] = c2[i] * 10 + c - '0';
			}
	}
	for (i = 0; i < N; ++i)
		if (c3[i] == '+') v[i] = (v[i] + c1[i] * c2[i] % MOD) % MOD;
		else v[i] = (v[i] - c1[i] * c2[i] % MOD) % MOD;
	ss.clear();
}

int main()
{
	int n, i, j;
	bool OK;
	
	getline(cin, s);
	Calc();
	copy(v, v + N, Std_Value);
	getline(cin, s);
	ss.str(s);
	ss >> n;
	ss.clear();
	for (i = 0; i < n; ++i)
	{
		getline(cin, s);
		Calc();
		OK = true;
		for (j = 0; j < N; ++j)
			if ((Std_Value[j] - v[j]) % MOD) {OK = false; break;}
		if (OK) cout << (char)(i + 'A');
	}
	cout << endl;
	
	return 0;
}
请先登陆