【Luogu1054】等价表达式

Source and Judge

NOIP2005 提高组 T4
Luogu1054
Caioj1524

Problem

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

这个选择题中的每个表达式都满足下面的性质:
1. 表达式只可能包含一个变量‘a’。
2. 表达式中出现的数都是正整数,而且都小于10000。
3. 表达式中可以包括四种运算‘+’,‘-’,‘*’,‘^’,以及小括号‘(’,‘)’。
(注意:运算符‘+’,‘-’,‘*’,‘^’以及小括号‘(’,‘)’都是英文字符)

小括号的优先级最高,
其次是‘^’,
然后是‘*’,
最后是‘+’和‘-’。
‘+’和‘-’的优先级是相同的。
相同优先级的运算从左到右进行。

4. 幂指数只可能是1到10之间的正整数(包括1和10)。
5. 表达式内部,头部或者尾部都可能有一些多余的空格。

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

1
2
3
4
5
6
((a ^1)^2)^3
a* a+a-a
((a+a) )
9999+(a-a)*a
1+(a -1)^3
1^ 10^9


【Input】
第一行给出的是题干中的表达式。
第二行是一个整数n,表示选项的个数。
后面n行,每行包括一个选项中的表达式。
这n个选项的标号分别是A,B,C,D……
输入中的表达式的长度都不超过50个字符,
而且保证选项中总有表达式和题干中的表达式是等价的。
【Output】
一系列选项的标号,表示哪些选项是和题干中的表达式等价的。
选项的标号按照字母顺序排列,而且之间没有空格。
【Limited conditions】
2<=n<=26
【Sample input】
1
2
3
4
5
( a + 1) ^2
3
(a-1)^2+4*a
a + 1+ a
a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a


【Sample output】
AC
【Sample explanation】

Record

30min

Analysis

请先思考

看到题面,突然就想到了NOIP2017D1T2的“时间复杂度”
都是很有意思的题目呢
虽然理论上“侦探推理”也很有意思,但纯属码农题

其实这道题感觉小学的时候想过,当时想设计四则运算的计算器,
但半途而废了……

好了讲正事
用函数递归求解
每次找优先级最低的地方,递归左右后计算即可

然后本来想自然溢出的,结果差一个点,改long long就行了

Code

请先思考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//Zory-2018
//****************头文件****************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<iostream>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
//****************全局常量****************
const int INF=0x3f3f3f3f;
//****************全局定义****************
char s[2][60];int ln[2];
ll ans[2][30];
//****************实现****************
bool isok(char c)
{
return c>='0' and c<='9';
}
ll power(ll x,int e) {ll t=1;for(int i=1;i<=e;i++) t=t*x;return t;}
ll make(int t,int l,int r,int a)
{
int mi=INF,mp,now=0;
bool op=0;
for(int i=r;i>=l;i--)//从后往前,保证自左向右结合性
{
int me=INF;
if(s[t][i]==')') now+=100;
if(s[t][i]=='(') now-=100;
if(s[t][i]=='^') me=now+3,op=1;
if(s[t][i]=='*') me=now+2,op=1;
if(s[t][i]=='+') me=now+1,op=1;
if(s[t][i]=='-') me=now+1,op=1;
if(me<mi) mi=me,mp=i;
}
if(op==0)
{
ll sum=0;
for(int i=l;i<=r;i++)
{
if(s[t][i]=='a') return a;
if(isok(s[t][i]))//去空格、换行、括号
sum=sum*10+s[t][i]-'0';
}
return sum;
}
if(s[t][mp]=='^') return power( make(t,l,mp-1,a),make(t,mp+1,r,a) );
if(s[t][mp]=='*') return make(t,l,mp-1,a)*make(t,mp+1,r,a);
if(s[t][mp]=='+') return make(t,l,mp-1,a)+make(t,mp+1,r,a);
if(s[t][mp]=='-') return make(t,l,mp-1,a)-make(t,mp+1,r,a);
}
//****************主函数****************
int main()
{
//gets(s[0]+1);
scanf("%[^\r]",s[0]+1);getchar();
ln[0]=strlen(s[0]+1);
for(int j=0;j<=30;j++) ans[0][j]=make(0,1,ln[0],j-15);
int n;scanf("%d",&n);getchar();
for(int i=1;i<=n;i++)
{
//gets(s[1]+1);
scanf("%[^\r]",s[1]+1);getchar();
ln[1]=strlen(s[1]+1);
for(int j=0;j<=30;j++) ans[1][j]=make(1,1,ln[1],j-15);
if(memcmp(ans[0],ans[1],sizeof(ans[0]))==0) printf("%c",'A'+i-1);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/等价表达式.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%