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;
uvnitr:=true;
u:='';
for i:=1 to Length(t) do
begin
if uvnitr=true then
begin
if t[i] in ['.','0'..'9'] then u:=u+t[i]
else begin
Val(u,r,k);
if (k<>0) or (u='') then
begin
chyba:=i-Length(u)+k;
Exit;
end;
s:=s+u;
u:=t[i];
uvnitr:=false;
end;
end
else begin
if not (t[i] in ['.','0'..'9']) then u:=u+t[i]
else begin
if Length(u)>1 then
begin
if u='--' then u:='+' else
if u='+-' then u:='-' else
if u='*-' then u:='@' else
if u='/-' then u:='#' else
if u='*--' then u:='*' else
if u='/--' then u:='/' else
begin
chyba:=i;
Exit;
end;
end;
s:=s+u;
u:=t[i];
uvnitr:=true;
end;
end;
end;
if uvnitr=false then
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;
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;
end;
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;
end;
end;
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;
end;
end;
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);
if k<>0 then
if t[1]='(' then
begin
delete(t,Length(t),1);
delete(t,1,1);
r2:=Uroven1(t);
end
else begin
k:=Pos('(',t);
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);
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