Cod sursa(job #296733)

Utilizator mlazariLazari Mihai mlazari Data 5 aprilie 2009 04:18:15
Problema Evaluarea unei expresii Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 3.67 kb
Program Evaluare;
const nmax=100000;
type BigString=array[1..nmax] of char;
     TipAtom=(inmultire,impartire,scadere,adunare,pardesc,parinc,valoare);
     Atom=record
       tip : TipAtom;
       value : longint;
       priority : byte;
     end;
     PCell=^Cell;
     Cell=record
       a : Atom;
       next : PCell;
     end;
var form : BigString;
    l : longint;
    P,U,op,polp,polu,pol : PCell;

procedure Citeste;
var Intrare : text;
begin
  assign(Intrare,'evaluare.in');
  reset(Intrare);
  l:=0;
  while not eoln(Intrare) do begin
    l:=l+1;
    read(Intrare,form[l]);
  end;
  close(Intrare);
end;

procedure AddInSt(var st : PCell; a : Atom);
var c : PCell;
begin
  new(c);
  c^.a:=a;
  c^.next:=st;
  st:=c;
end;

function ScoateDinSt(var st : PCell) : Atom;
var c : PCell;
    a : Atom;
begin
  a:=st^.a;
  c:=st;
  st:=st^.next;
  dispose(c);
  ScoateDinSt:=a;
end;

procedure AddInCoada(var qp,qu : PCell; a : Atom);
var c : PCell;
begin
  new(c);
  c^.a:=a;
  c^.next:=nil;
  if qp=nil then begin
    qp:=c;
    qu:=c;
  end
  else begin
    qu^.next:=c;
    qu:=c;
  end;
end;

function ScoateDinCoada(var qp,qu : PCell) : Atom;
var c : PCell;
    a : Atom;
begin
  if qp=qu then qu:=nil;
  ScoateDinCoada:=ScoateDinSt(qp);
end;

function ato(tip : TipAtom; value : longint; priority : byte) : Atom;
var a : Atom;
begin
  a.tip:=tip;
  a.value:=value;
  a.priority:=priority;
  ato:=a;
end;

procedure ExtractAtom(var i : longint);
var v : longint;
begin
  case form[i] of
   '*': AddInCoada(P,U,ato(inmultire,0,2));
   '/': AddInCoada(P,U,ato(impartire,0,2));
   '+': AddInCoada(P,U,ato(adunare,0,1));
   '-': AddInCoada(P,U,ato(scadere,0,1));
   '(': AddInCoada(P,U,ato(pardesc,0,0));
   ')': AddInCoada(P,U,ato(parinc,0,0));
   else begin
     v:=ord(form[i])-48;
     while i<l do begin
       i:=i+1;
       if (form[i] in ['0'..'9']) then v:=v*10-48+ord(form[i])
       else break;
     end;
     if not (form[i] in ['0'..'9']) then i:=i-1;
     AddInCoada(P,U,ato(valoare,v,0));
   end;
  end;
  i:=i+1;
end;

function rez(op : TipAtom; x,y : longint) : longint;
begin
  case op of
   inmultire: rez:=x*y;
   impartire: rez:=x div y;
   adunare: rez:=x+y;
   scadere: rez:=x-y;
   else rez:=0;
  end;
end;

function Eval(var polp,polu : PCell) : longint;
var a : Atom;
    x,y : longint;
begin
  pol:=nil;
  while polp<>nil do begin
    a:=ScoateDinCoada(polp,polu);
    case a.tip of
     valoare: AddInSt(pol,a);
     else begin
       y:=ScoateDinSt(pol).value;
       x:=ScoateDinSt(pol).value;
       AddInSt(pol,ato(valoare,rez(a.tip,x,y),0));
     end;
    end;
  end;
  Eval:=ScoateDinSt(pol).value;
end;

procedure Calculeaza;
var i : longint;
    a : Atom;
begin
  P:=nil;
  U:=nil;
  op:=nil;
  polp:=nil;
  polu:=nil;
  i:=1;
  while i<=l do ExtractAtom(i);
  while P<>nil do begin
    a:=ScoateDinCoada(P,U);
    case a.tip of
      inmultire..adunare: begin
        while op<>nil do begin
          if op^.a.priority>=a.priority then
           AddInCoada(polp,polu,ScoateDinSt(op))
          else break;
        end;
        AddInSt(op,a);
      end;
      pardesc: AddInSt(op,a);
      parinc: begin
        while op^.a.tip<>pardesc do AddInCoada(polp,polu,ScoateDinSt(op));
        a:=ScoateDinSt(op);
      end;
      valoare: AddInCoada(polp,polu,a);
    end;
  end;
  while op<>nil do AddInCoada(polp,polu,ScoateDinSt(op));
end;

procedure Scrie;
var Iesire : text;
begin
  assign(Iesire,'evaluare.out');
  rewrite(Iesire);
  write(Iesire,Eval(polp,polu));
  close(Iesire);
end;

begin
  Citeste;
  Calculeaza;
  Scrie;
end.