ac1138.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1138;
const
  maxterms=1000;
type
  term=record factor,index:longint;end;
  formula=array[1..maxterms]of term;
var
  a,b,c:formula;
  p,la,lb,lc,i,j:longint;
  s:ansistring;
  first:boolean;
procedure getnum(var x:longint);
  var
    minus:boolean;
  begin
    minus:=s[p]='-';
    if s[p] in ['+','-'] then repeat inc(p);until s[p]<>' ';
    x:=0;
    while s[p] in ['0'..'9'] do begin
      x:=x*10+ord(s[p])-48;
      repeat inc(p);until s[p]<>' ';
    end;
    if minus then x:=-x;
  end;
procedure getformula(var a:formula;var l:longint);
  begin
    l:=0;
    repeat
      while s[p]=' ' do inc(p);
      if s[p]=')' then exit;
      inc(l);getnum(a[l].factor);
      if s[p]='a' then begin
        repeat inc(p);until s[p]='^';
        repeat inc(p);until s[p]<>' ';
        getnum(a[l].index);
      end
      else
        a[l].index:=0;
    until false;
  end;
procedure qsort(s,t:longint);
  var
    p,i,j:longint;
    tc:term;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tc:=c[p];c[p]:=c[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (c[j].index<=tc.index) do dec(j);
      if i=j then break;c[i]:=c[j];inc(i);
      while (i<j) and (c[i].index>=tc.index) do inc(i);
      if i=j then break;c[j]:=c[i];dec(j);
    until i=j;
    c[i]:=tc;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
procedure out(f,i:longint);
  begin
    if not first and (f>0) then write('+');
    write(f);
    if i>0 then write('a^',i);
  end;
begin
  repeat
    readln(s);p:=1;while s[p]<>'(' do inc(p);inc(p);
    getformula(a,la);
    repeat inc(p);until s[p]='(';inc(p);
    getformula(b,lb);

    lc:=0;
    for i:=1 to la do
      for j:=1 to lb do begin
        inc(lc);
        c[lc].factor:=a[i].factor*b[j].factor;
        c[lc].index:=a[i].index+b[j].index;
      end;
    qsort(1,lc);

    first:=true;p:=c[1].factor;
    for i:=2 to lc do begin
      if (c[i].index<c[i-1].index) and (p<>0) then begin
        out(p,c[i-1].index);
        first:=false;p:=0;
      end;
      inc(p,c[i].factor);
    end;
    if p<>0 then out(p,c[lc].index);
    writeln;
  until seekeof;
end.