int21h

Vyhodnocování matematických výrazů (parser)

Jaký program použijete, když potřebujete rychle spočítat nějaký matematický výraz? Při programování se běžně stává, že najednou nutně potřebujete vědět, kolik je třeba (12+60)*4-(1-5*(-77+19))
IDE Turbo pascalu v sobě kalkulačku nemá, windowsí kalkulačka se na tohle nehodí, protože neumí výrazy, takže nejspíše příklad vyřešíte postaru papírem a tužkou.
Případně si napíšete pascalovský jednoúčelový mikroprogámek, který tento výraz spočte.
Počítání výrazů pascal zvládne levou zadní. Co to ale zkusit naprogramovat taky? Když to dokázali tvůrci pascalu (BASICu, Fortranu,..., zkrátka jiní, tak my to dokážeme taky, ne?
Já sám jsem v jednom svém programu používal takovýto parser už před třemi lety, ale ten byl vykradený z cizího zdrojáku, a teď jsem si řekl, že jsem přece velkej kluk a že si napíšu svůj vlastní.
Co tedy takový parser musí umět:

• Ošetřit záludnosti znaménka mínus, tedy, že mínus a mínus je dohromady plus a podobně
• Ohlídat korektní vstup. Tím mám na mysli ověřit korektnost výrazu, jako např. řádné párování závorek, povolené znaky, povolené matematické funkce, zkrátka ochrana proti všemu nekorektnímu, co může BFU zadat.
• Ohlídat průběh výpočtu. Tedy ohlídání dělení nulou, záporných argumentů sudých mocnit a podobně
• Priorita operátorů. násobení a dělení má vyšší prioritu než sčítání a odčítání
• Závorky. není co dodat
• ev. některé matematické funkce

Vidíme tedy, že to není prdel. Doporučuji začít nejprve jakousi minimální verzí, která bude umět jenom sčítat, odčítat, násobit a dělit. Teprve poté, co odladíte tuto "minimální verzi", přidejte závorky a funkce.
Zpracování je nejlépe provést ve dvou krocích:
1) kontrola korektnosti zadaného řetězce a předžvejkání
2) vlastní výpočet

Preprocesor

Předžvejkáním mám na mysli hlavně vyřešení problému se znakem mínus. Je rozumné sekvence --, +-, *-..., nahradit jediným symbolem už během tohoto kroku. Jistě, můžete si říct, že tyto kombinace operandů nepovolíte zadat, ale to by bylo hodně omezující. Hlavní využití vašeho parseru totiž bude patrně v tom, že bude vyhodnocovat rovnice s parametrickými proměnnými, které se budou dosazovat až za běhu programu.
(např. (a+15)*-(b-c)+1)
Za běhu programu se doplní koeficienty a pokud bude C záporné, vznikne (B--C). Věnujte pozornost i sekvenci *-. Naším cílem je nahradit víceznakové symboly za jednoznakové. Jenže symbol "vynásob a změň znaménko" neexistuje.
Nu což, tak ho tedy zavedeme! Nechť se tedy *- změní na @ a sekvence /- na #
První verze mého preprocesoru vypadala takto:

Procedure Preprocesor(s:string;var t:string;var chyba:byte);
var i,j:byte;
    k:integer;
    r:real;
    uvnitr:boolean;
    u:string;
begin
t:=ZrusMezery(s);
s:='';
if t[1] in ['-'] then t:='0'+t;    {cely vyraz zacina znamenkem minus?}
uvnitr:=true;           {zaciname uvnitr cisla}
u:='';
for i:=1 to Length(t) do
    begin
    if uvnitr=true then {uvitr cisla...}
       begin
       if t[i] in ['.','0'..'9'] then u:=u+t[i]
          else begin
          Val(u,r,k);
          if (k<>0) or (u='') then   {ze znaku '.' a '0'..'9' nevzniklo smysluplne cislo?}
             begin       {(nejspise dve desetinne tecky v jednom cisle)}
             chyba:=i-Length(u)+k;
             Exit;
             end;
          s:=s+u;
          u:=t[i];
          uvnitr:=false;
          end;
       end
       else begin       {jsme vne cisla...}
       if not (t[i] in ['.','0'..'9']) then u:=u+t[i]
          else begin
          if Length(u)>1 then {kombinace symbolu?}
             begin
             if u='--' then u:='+' else
             if u='+-' then u:='-' else
             if u='*-' then u:='@' else  {ZAPORNE NASOBENI}
             if u='/-' then u:='#' else  {ZAPORNE DELENI}

             if u='*--' then u:='*' else
             if u='/--' then u:='/' else
                begin          {ostatni kombinace nejsou povolene}
                chyba:=i;
                Exit;
                end;
             end;
          s:=s+u;
          u:=t[i];
          uvnitr:=true;
          end;
       end;
    end;   {for}

if uvnitr=false then  {na konci vyrazu musi byt cislo, ne symbol}
   begin
   chyba:=i;
   Exit;
   end;
chyba:=0;
s:=s+u;
t:=s;
end;

Procedura kromě předžvýkaného řetězce T vrací i pozicu chyby chyba. Její výsledky je třeba brát s rezervou, nicméně platí, že pokud je 0, tak je řetězec korektní; v opačném případě je chybně.

Vlastní výpočet

Tady už máme pořešené víceznaké matematické symboly, ale problém jejich priority přetrvává. Povedlo se mi to vyřešit až na třetí pokus.
Je totiž třeba rezignovat na zpracování celého výrazu v jedné proceduře. Vyřešil jsem to zavedením dvou procedur. Jedna zpracovává sčítání a odčítání (jmenuje se Uroven1), druhá násobení a dělení (Uroven2).
Takhle vypadá zdroják funkce Uroven1:

Function Uroven1(const s:string):real;
var o:byte;      {typ operace: (ZADNA, SOUCET, ODECET)}
    i:byte;
    r,r2:real;
    t:string;

begin
t:='';
o:=NIC;
r:=0;
for i:=1 to Length(s) do
    if not (s[i] in ['+','-']) then t:=t+s[i]
       else begin
       r2:=Uroven2(t);
       r:=Operace1(r,r2,o);
       t:='';
       case s[i] of
          '+':o:=SOUCET;
          '-':o:=ODECET;
       end;  {case}
       end;  {else begin}

{dodelame posledni cislo, za kterym uz neni zadny matematicky symbol}
if druh_chyby<>CHYBA_ZADNA then
   begin
   Uroven1:=0;
   Exit;
   end;
r2:=Uroven2(t);
Uroven1:=Operace1(r,r2,o);
end;

Funkce tedy rozkládá výraz na úseky rozdělené znaky plus a mínus a tyto úseky posílá na "vyšší instanci" do funkce Uroven2. Smysl vynikne, podíváme-li se na příklad nějakého matematického výrazu:
3+4*6/2.4+6
Jednotlivé úseky jsou vyznačeny tučně. Úseky 3 a 6 už dále počítat netřeba, úsek 4*6/2.4 si po cifrách rozebere a spočítá Uroven2.

Kompletní zdroják první verze parsery bez podpory závorek je zde. Věnujte pozornost funkci Operace2, abyste viděli, jak využívám své nově definované matematické symboly "záporného násobení a dělení"

Závorky a funkce

Je jasné, že parser, který neumí zpracovat závorky je na prd. Takže se toho vrhněme. Dvě dobré zprávy:
1) jakmile zvládnete závorky, zvládnete i matematické funkce, protože mat. funkce je vlastně jenom jakýsi přílipek k levé závorce. Uvidíte dále.
2) naprogramovat podporu přimo ve vlastním výpočtu je mnohem jednodušší než podpora v preprocesoru. A v preprocesoru jejich zpracovávání může být také jednoduché, rezignujeme-li na kontrolu syntaxe.
Podívejme se tedy, jak se změnila procedura Uroven1

Function Uroven1(s:string):real;
var z,i,o:byte;
    r,r2:real;
    t:string;
begin
if s='' then begin Uroven1:=0;Exit;end;
t:='';
o:=NIC;
r:=0;
z:=0;
for i:=1 to Length(s) do
    begin
    if s[i]='(' then inc(z);
    if s[i]=')' then dec(z);
    if (z<>0) or (not (s[i] in ['+','-']))
       then t:=t+s[i]
       else
       begin
       r2:=Uroven2(t);
       r:=Operace1(r,r2,o);
       t:='';
       case s[i] of
          '+':o:=SOUCET;
          '-':o:=ODECET;
       end;  {case}
       end;  {else begin}
    end;
{dodelame posledni cislo, za kterym uz neni znak zadne operace}
if druh_chyby<>CHYBA_ZADNA then
   begin
   Uroven1:=0;
   Exit;
   end;
r2:=Uroven2(t);
Uroven1:=Operace1(r,r2,o);
end;

Změnou je tedy zavedení čítače Z, který počítá, jak moc jsme zanořeni v závorkách. Jednotlivé členy výrazu tedy odděluje jen, pokud je zanoření 0, tedy nejsme uvnitř závorky. Výraz s závorkou je tedy rozsekán správně, a to takto:
3+(2+2)*6/2.4+6
Kdybychom závorkování nehlídali, rozsekání by proběhlo chybně:
3+(2+2)*6/2.4+6

Teď je nezbytně nutné podívat se i na Uroven2 a její satelitní funkce:

Function Uroven2(const s:string):real;
var i,o,z:byte;
    r,r2:real;
    k:integer;
    t:string;
begin
if s='' then begin Uroven2:=0;Exit;end;
t:='';
o:=NIC;
r:=0;
z:=0;
for i:=1 to Length(s) do
    begin
    if s[i]='(' then inc(z);
    if s[i]=')' then dec(z);

    if (z<>0) or (not (s[i] in ['*','/','@','#'])) then t:=t+s[i]
       else begin
       r:=ZpracujClen(t,r,r2,o);
       if druh_chyby<>CHYBA_ZADNA then
          begin
          Uroven2:=0;
          Exit;
          end;
       t:='';
       case s[i] of
          '*':o:=NASOBENI;
          '/':o:=DELENI;
          '@':o:=ZAPORNE_NASOBENI;
          '#':o:=ZAPORNE_DELENI;
       end;  {case}
       end;  {else begin}
    end;
{dodelame posledni cislo, za kterym uz neni znak zadne operace}
Uroven2:=ZpracujClen(t,r,r2,o);
end;

Jak vidíme, Uroven2 se velmi podobá funkci Uroven1. I ona si musí hlídat zanoření do závorek, protože závorky mají ještě vyšší prioritu než násobení či dělení.
To skutečně zajímavé probíhá uvnitř funkce ZpracujClen. Podívejme se na ni:

Function ZpracujClen(t:string;r,r2:real;o:byte):real;
var k:integer;
    i:byte;
    n:real;
    s:string[10];
begin
Val(t,r2,k);      {napred to zkus proste prevest na cislo}
if k<>0 then      {konverze cisla se nepovedla, tudiz je to neco slozitejsiho}
   if t[1]='(' then
      begin                  {zacina to zavorkou, je to tedy zavorka}
      delete(t,Length(t),1);
      delete(t,1,1);
      r2:=Uroven1(t);
      end
      else begin
      k:=Pos('(',t);     {zavorka je uvnitr kazdopadne, ale co je pred ni?}
      s:=Copy(t,1,k-1);
      delete(t,Length(t),1);
      delete(t,1,k);
      r2:=Uroven1(t);
      if s='SIN' then r2:=sin(r2) else
      if s='COS' then r2:=cos(r2);
  {Dalsi matematicke funkce jsem pro zkraceni zdrojaku vypustil}
      end;
ZpracujClen:=Operace2(r,r2,o);
end;

Funkci si budeme demostrovat na tomto výrazu:
5*cos(0)*(1+2*(2-5))
1) Napřed do funkce ZpracujClen dorazí 5. Žádný problém, to pořeší jednoduché Val.
2) Dále příjde cos(0). Val ohlásí chybu, tudíž víme, že je to něco složitějšího, než pouhé číslo. První znak tohoto členu není závorka, tudíž jí předchází matematická funkce (nic jiného to být nemůže). Nicméně závorka tam někde musí být tak jako tak, protože mat. funkce mají svoje argumenty v závorkách. Tudíž ji najdeme, vytáhnu vnitřek závorky (v našem případě 0)
a provedu rekurzivní volání funkce Uroven1
Ta takovouto trivialitu vyřeší raz dva, vrátí hodnotu 0, ke které poté vypočítám cosinus.
3) A nakonec (1+2*(2-5)), což je složitější varianta předchozího případu, akorát, že bez přídavné mat. funkce. I tohle pořeší rekurze. Rekurze je mocná!

Aby tohle všechno dobře šlapalo, tak je ale nutné, aby závorky byly správně spárované. V preprocesoru tedy vždy pečlivě ošetřete, zda je závorkování validní.
Konečný program je zde.

Závěrem bych chtěl poznamenat, že tenhle program jsem psal tak, aby šel přeložit i v Turbo pascalu a musím říct, že to byla pěkná pruda. Neskutečně mi chybí, že Exit nemá v TP parametr, tudíž nemůže vracet návratovou hodnotu, jako to umí FP. Nepohodlné.

Aktualizace! - svůj parser jsem ještě vylepšil a udělal z něho jednotku a program, který ji využívá. Je optimalizovaný pro FreeDOS a jelikož má všchny hlášky uloženy v externích textových souborech, je mnohojazyčný. Stahovat můžete zde: Compute