题解 P1054 【等价表达式】

Limit · 2019-02-04 12:56:56 · 题解

先用栈把中缀转成后缀QAQ，带入一个特殊值比较 but 这题的数据比较可怕，在取值时要小心

{->}
//这里就是玄学的取值，自己选一个,基本都有70分~90分
//100分还是比较少的QAQ
const md=100000007;//取mod的值也是很重要的
      add=13758;
{<-}
var i,j,k:longint;
    s:ansistring;
    num:array[-1..1000000]of longint;
    fh:array[-1..1000000]of char;
    ch:char;
    f:array[char]of longint;
    m,n,t,h:longint;
    x,y:longint;
    ans:longint;
function js(m,n:longint;ch:char):longint;//计算
var i:longint;
begin
  if ch='+' then exit((m+n) mod md);
  if ch='*' then exit((m*n) mod md);
  if ch='-' then exit((m-n) mod md);
  if ch='^' then 
  begin
    js:=m;
    for i:=2 to n do js:=js*m mod md;
    exit(js);
  end;
end;
function jspd(s:ansistring):longint;//中缀转后缀
var i,j,k,m,n,h,t:longint;
begin
  //运算等级，方便判断
  f['(']:=1;
  f[')']:=1;
  f['*']:=3;
  f['+']:=2;
  f['-']:=2;
  f['^']:=4;
  t:=0;
  h:=0;
  i:=0;
  s:='('+s+')';
  while i<length(s) do
  begin
    inc(i);
    while s[i]=' ' do inc(i);//把空格去掉
    if s[i]='a' then
    begin
      inc(t);
      num[t]:=add;//把值带入
    end;
    if s[i]in ['0'..'9'] then
    begin
      inc(t);
      num[t]:=ord(s[i])-48;
      inc(i);
      while s[i] in ['0'..'9'] do
      begin
      num[t]:=(num[t]*10+ord(s[i])-48) mod md;
      inc(i);
      end;
    end;
    begin
      if s[i] in ['+','*','-','^','('] then
      begin
        if (s[i] in ['+','*','-','^']) and (f[fh[h]]>=f[s[i]]) then
        while (f[fh[h]]>=f[s[i]]) do//其他和表达式的值差不多，只是因为运算等级多了，所以要改成while
        begin
          num[t-1]:=js(num[t-1],num[t],fh[h]);
          dec(t);
          dec(h);
        end;
        inc(h);
        fh[h]:=s[i];
      end else
      if s[i]=')' then
      begin
        while (fh[h]<>'(') and (h>=0) and (t>=0) do
        begin
          num[t-1]:=js(num[t-1],num[t],fh[h]);
          dec(t);
          dec(h);
        end;
        dec(h);
      end;
    end;
  end;
  exit(num[1]);//返回值
end;
begin
  readln(s);//读入
  ans:=jspd(s);//把原表达式的值先算出来
  readln(n);
  for i:=1 to n do
  begin
    readln(s);
    if jspd(s)=ans then write(chr(ord('A')+i-1));//判断，如果正确就输出...
  end;
end.

如果在NOIP现场码一个难度还是挺大的,估计AC的dalao不多吧，面向数据调试其实还是挺快的