【问题描述】
明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。
这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？
这个选择题中的每个表达式都满足下面的性质：
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……
【样例输入】
(a+1)^2
3
(a-1)^2+4*a
a+1+a
a^2+2*a*1+1^2+10-10+a-a
【样例输出】
AC
【解题思路】
本题为NOIP2005提高组第四题，求两个表达式是否等价，其实就是看两个表达式的值是否相等，因此，我们将a换为随机化的数，多次随机化的数产生的结果都相等的话，就说明两个表达式等价，便输出表达式的选项，求表达式的值，自然就是用栈来解决，详见NOIP2013普及组第二题。我在这道题上用了两个总过程，一个建栈，一个计算
【代码实现】
type arr=array[..] of char;
arr2=array[..] of extended;
var ii,jj,n,c1,c2:longint;
tag:boolean;
x1,x2,x3:extended;
c:char;
st,a,e:string;
function pop(var stack:arr; var t:longint):char;
begin
pop:=stack[t];
dec(t);
end;
function top(var stack:arr; var t:longint):char;
begin
top:=stack[t];
end;
procedure push(var stack:arr; ch:char; var t:longint);
begin
inc(t);
stack[t]:=ch;
end;
procedure create(var x,y:string);//建栈
var s:arr;
tp,i,j,k:longint;
begin
x:=x+'@';i:=;tp:=;y:='';
while x[i]<>'@' do
begin
case x[i] of
''..'':
begin
while (x[i]>='')and(x[i]<='') do
begin
y:=y+x[i];
inc(i);
end;
dec(i);
y:=y+'.';
end;
'a':y:=y+'a';
'(':push(s,'(',tp);
')':
begin
if tp> then
begin
c:=top(s,tp);
while c<>'(' do
begin
y:=y+c;
c:=pop(s,tp);
if tp> then
c:=top(s,tp)
else
break;
end;
end;
if (tp>)and(c='(')then
c:=pop(s,tp);
end;
'+','-':
begin
if tp> then
begin
c:=top(s,tp);
while c<>'(' do
begin
y:=y+c;
c:=pop(s,tp);
if tp> then
c:=top(s,tp)
else
break;
end;
end;
push(s,x[i],tp);
end;
'*','/':
begin
if tp> then
begin
c:=top(s,tp);
while (c<>'(')and(c<>'+')and(c<>'-') do
begin
y:=y+c;
c:=pop(s,tp);
if tp> then
c:=top(s,tp)
else
break;
end;
end;
push(s,x[i],tp);
end;
'^':
begin
if tp> then
begin
c:=top(s,tp);
while c='^' do
begin
y:=y+c;
c:=pop(s,tp);
if tp> then
c:=top(s,tp)
else
break;
end;
end;
push(s,x[i],tp);
end;
end;
inc(i);
end;
while tp> do
y:=y+pop(s,tp);
y:=y+'@';
end;
function pop2(var stack:arr2;var tp:longint):extended;
begin
pop2:=stack[tp];
dec(tp);
end;
function top2(var stack:arr2; var tp:longint):extended;
begin
top2:=stack[tp];
end;
procedure push2(var stack:arr2; num:extended; var tp:longint);
begin
inc(tp);
stack[tp]:=num;
end;
function chu(x,y:extended):extended;
begin
if y= then
chu:=-maxlongint
else
chu:=x/y;
end;
function cf(x,y:extended):extended;
var i:longint;
begin
cf:=;
for i:= to round(y) do
cf:=cf*x;
end;
function work(x:string;v:extended):extended;//求表达式的值
var s:arr2;
i,j,tp:longint;
k,w1,w2:extended;
begin
i:=;tp:=;
while x[i]<>'@' do
begin
case x[i] of
''..'':
begin
k:=;
while x[i]<>'.' do
begin
k:=k*+ord(x[i])-;
inc(i);
end;
push2(s,k,tp);
end;
'a':
begin
k:=v;
push2(s,k,tp);
end;
'+':push2(s,pop2(s,tp)+pop2(s,tp),tp);
'-':
begin
w2:=pop2(s,tp);
w1:=pop2(s,tp);
push2(s,w1-w2,tp);
end;
'*':push2(s,pop2(s,tp)*pop2(s,tp),tp);
'/'://可能除以0，需要判断
begin
w2:=pop2(s,tp);
w1:=pop2(s,tp);
k:=chu(w1,w2);
if k=-maxlongint then
exit(-maxlongint)
else
push2(s,k,tp);
end;
'^':
begin
w2:=pop2(s,tp);
w1:=pop2(s,tp);
push2(s,cf(w1,w2),tp);
end;
end;
inc(i);
end;
work:=pop2(s,tp);
end;
procedure k;
var st1,st2,s1,s2:string;
ch:char;
r,u:longint;
t1,t2:extended;
begin
readln(e);
while pos(chr(),e)<> do
delete(e,pos(chr(),e),);
create(e,a);
tag:=true;//判断两个表达式是否相等
c1:=;
c2:=;
for jj:= to do
begin
x3:=random;
x1:=work(st,x3);
x2:=work(a,x3);
if (x1=)or(x2=) then
begin
if abs(x1-x2)<1e-10 then
continue
else
begin
tag:=false;
break;
end;
end;
if (x1=-maxlongint)or(x2=-maxlongint) then
begin
if x1=-maxlongint then
inc(c1);
if x2=-maxlongint then
inc(c2);
continue;
end
else
begin
str(x1,st1);
str(x2,st2);
s1:=copy(st1,,);
s2:=copy(st2,,);
t1:=ln(abs(x1));
t2:=ln(abs(x2));
if not((x1=x2)or(((x1>0)and(x2>0)or(x1<0)and(x2<0))and(round(t1)=round(t2))and(s1=s2))) then 这里是一个很重要的判断是否相等的句子，可以自行思考一下
begin
tag:=false;
break;
end;
end;
end;
if (c1=)and(c2>)or(c1>)and(c2=) then
tag:=false;
if tag then
write(chr(ii+));
end;
begin
randomize;//随机化
readln(e);
while pos(chr(),e)<> do
delete(e,pos(chr(),e),);//数据有坑，无缘无故会有许多多余的空格
create(e,st);
readln(n);
for ii:= to n do
begin
if ii= then
n:=n;
k;
end;
writeln;
end.