4+5*3-2=?

Ennek a matematikai kifejezésnek az értelmezése legtöbbünknek fejben is sikerülne, ám, ha belegondolunk, nem is olyan egyszerű a feladat, ha hatékony megoldást keresünk. Miről is beszélek? Amikor bármilyen magas szintű programnyelvben beírunk egy kifejezést pl.: k:=sin(x/10)*3, a fordítónak értelmeznie kell azt, hiszen a gépi kódú utasításokkal csak alapműveletek érhetők el. Legtöbb esetben tehát nem kell foglalkoznunk ezekkel a nehézségekkel.
Mi van akkor, ha mi olyan programot szeretnénk írni, ahol a felhasználó adhatja meg a képletet (függvényábrázoló program). Ilyenkor nekünk, programíróknak kell megbirkózni a problémával.
A problémának három, általam is ismert megoldása létezik. Mind a három megoldás a szöveges változóként kapott kifejezéssel dolgozik és egy számot ad vissza, amely az eredményt tartalmazza.

Az egyszerű megoldás
Az első megoldási mód, hogy prioritási sorrendben végigmegyünk a szövegen és kiszedegetjük belőle a műveleteket, míg végül csak egy szám marad. Kiszedegetés alatt azt értem, hogy az aktuális prioritású műveletet a program kiszámolja, majd az eredményt a kifejezés megfelelő részére írja vissza valahogy így:
 
 
4+5*3-2*3+1  Ez az alap kifejezés.
4+15-2*3+1 Kiszedtük az első szorzást
4+15-6+1 Kiszedtük a második szorzást
19-6+1 Ez volt az első összeadás
13+1 Ez volt a második összeadás
14 Íme az eredmény.

Ha egy kifejezés zárójelet vagy függvényt tartalmaz, akkor a zárójel illetve a függvény belső részét teljesen külön értelmezzük (rekurzív módon). Ez a megoldás tűnik a legkézenfekvőbbnek, de egyben ez a legkevésbé hatékony is. Gondoljunk bele, hány szám-szöveg, szöveg-szám konverziót és hány szöveges műveletet kell elvégezni.

Lengyelforma
Ezt a megoldási módot egy lengyel matematikus dolgozta ki a század elején, innen a neve. Itt a kifejezést először egy ún. lengyelformára hozzuk. A lengyelforma jellegzetessége, hogy nincsenek benne zárójelek és prioritási sorrendek, megfelelő értelmezéssel mégis helyes eredményt ad.
A lengyelformában a kifejezés összetevőit szóköz választja el egymástól, a műveleti jelek a kifejezésben szereplő számcsoportok után kerülnek.

Pl:
5+6 lengyelformája 5 6 +
5+6*2 lengyelformája 5 6 2 * +
5+6*2-3 lengyelformája 5 6 2 * + 3 -

A kifejezés lengyelformáját a következő módon képezzük:

A kifejezésben található műveleti jelekből felállítunk egy prioritási sorrendet, amelyben a nem műveleti jelek 0, a nyitó zárójel 1, az összeadás, kivonás 2, a szorzás, osztás 3, a bezáró zárójel 4-es prioritással rendelkezik. Szükségünk lesz egy veremre, amelyben a műveleti jeleket tároljuk. Balról jobbra olvassuk a kifejezést, a számokat szóközökkel elválasztva egyszerűen átírjuk. Ha műveleti jelet találunk, kicsit bonyolultabb a dolog. Először leellenőrizzük, hogy van-e olyan műveleti jel a veremben, amit ki kell onnan venni, majd az aktuális műveleti jelet lerakjuk a verembe.
Nyitó zárójel esetén nem veszünk ki egyetlen műveleti jelet sem, ha záró zárójelet találunk, akkor az összes műveleti jelet egészen az első nyitó zárójelig kivesszük a veremből és - a nyitó zárójel kivételével - hozzáírjuk a lengyelformához.
Nem zárójelek esetén a prioritások döntenek, kivesszük a veremből és hozzáírjuk a lengyelformához az összes, a jelenlegi műveleti jelnél nem kisebb prioritású műveleti jelet.
Ha végigmentünk így a kifejezésen, nincs más dolgunk, mint a veremben maradt néhány műveleti jelet is kivenni és azt is a lengyelforma végére írni.

Az eredményként kapott látszólagos kuszaság mögött furfangos logika rejtőzik...

A lengyelforma értelmezése
A fenti algoritmus által szolgáltatott eredmény az emberi szem számára kicsit kuszának tűnik, mégis van benne értelem. Az értelmezés úgy zajlik, balról jobbra elkezdjük olvasni a kifejezést. Ha számot találunk, azt lerakjuk egy verembe. Ha műveleti jelet találunk, akkor kivesszük a verem két felső elemét, az első és második operandust, elvégezzük a kijelölt műveletet, majd az eredményt letesszük a verembe. Ha mázlink van (mindent jól csináltunk) a kifejezés végére érve nincs más dolgunk, mint kivenni a verem egyetlen elemét, az eredményt.
Hatékonyság
A módszer előnye az előbbihez képest relatív gyorsasága. Ugyanakkor problémaként jelentkezik a rugalmatlanság, hisz igen nehézkes volna ezt a módszert, a fenti logikát követően, függvények és változók kezelésével kiegészíteni. Problémaként jelentkezik, hogy nagymennyiségű, egymástól csak bizonyos paraméterekben különböző kifejezés kiszámításához már lassú. Erre a problémára nyújt megoldást a következő eljárás...
Objektumorientált gráfos megoldás
Első hallásra talán furcsának tűnhet, hogy egy matematikai kifejezést objektumorientált módszerekkel kell értelmezni, de ha meggondoljuk, lehet benne logika. Minden kifejezés tovább nem osztható részegységekből áll, ilyenek a függvények, alapműveletek, számok. Ha ezeknek megfeleltetünk egy-egy objektumot, az objektumok közötti kapcsolatok felírásával tetszőleges matematikai kifejezést leírhatunk. Milyenek is ezek a kapcsolatok? Az objektumokat gráfba fűzzük, ahol minden objektum mutat az operandusaira, amelyek szintén objektumok. Ilyen módon a prioritásokat (pontosabban a kiértékelési sorrendet) a gráf szintjei határozzák meg. Lássunk néhány példát az objektumszerkezetre:
 

Ha végigkövetjük az ábrákat, nyilvánvalóvá válnak a gráf készítésének és értelmezésének szabályai. Az értelmezés mindig balról jobbra, lentről felfelé történik, bár - mivel ez az adatszerkezet objektumokból van - erre nem kell majd sok figyelmet fordítani, mivel minden objektumtípushoz készítünk egy metódust, ami az eredményeket kérdezi le, így egyetlen általunk indított kérdéssel rekurzív módon végigkövethetjük a teljes gráfot. A feladat nehezebb része a megfelelő adatszerkezet elkészítése egy kifejezésből. Erre a problémára is egy rekurzív megoldás tűnik egyszerűnek, itt műveleteket keresünk, méghozzá fordított prioritási sorrendben, vagyis először az összeadást, kivonást. Ha műveleteket találunk, megkeressük azok operandusait. Az operandus addig tart, amíg 0 (nulla) zárójelezettségi szinten nem találunk egy azonos vagy kisebb prioritású műveletet. A gráfkészítő rutinnak két paraméterre van szüksége, az egyik a gráf aktuális pontja (többnyire valamilyen művelet valamelyik operandusmutatója) és a kiértékelni kívánt operandus szöveges formában. Ha az operandus zárójelben van (pl. Azért, mert egy zárójelezett kifejezés) akkor a zárójeleket le kell szedni az operandusról. Egy bonyolultabb kifejezés kiértékelése a következő módon zajlik:

A rutin megkapja a gráf csúcsát és a teljes kifejezést.
Először öszeadást illetve kivonást keresünk:


A szürke részek a talált összeadási művelet operandusai. Ezek után a gráfkészítő rutin meghívja önnmagát, de most a kapott paraméterek az első operandus és a most talált összeadás első operandusmutatója.


Ebben a kifejezésben nem volt összeadás illetve kivonás, így szorzásokat keres a program. Az operandusokkal itt is meghívja saját magát a rutin, mivel azonban az operandusok már nem bonthatók tovább, egyszerűen elkészíti a számokat a gráf aljára. Lássuk az összeadás második operandusát!


Ebben a kifejezésben sincs egyetlen összeadás illetve kivonás, így az osztás kerül kiértékelésre.
Osztandó kiértékelése:


Ez egy függvény. Ilyenkor a rutin létrehozza a függvény objektumot és a függvény paraméterének kiértékeléséhez meghívja önmagát.


Kiértékelődik a baloldal, ezzel nem foglalkoznék, mivel a négyzetgyök esetében már láttuk, hogy hogyan történik a művelet. A jobb oldal kicsit érdekesebb, mivel több azonos prioritású művelet van benne. Ilyenkor a következő dolog történik:

Kiértékelődik az első szorzás...

... majd folytatódik a kiértékelés a második szorzással, ami beszúródik a kivonás és az első szorzás közötti szintre, így biztosítva a helyes kiértékelési sorrendet. A második szorzás első operandusa az első szorzás eredménye lesz.:

Most kiértékelődik az első lépésekben lévő osztás (/2) második operandusa, ami csak egy szám így egyetlen rekurzív hívással elkészül a szám objektum hozzá. Mindezek után kiértékelődik az osztás utáni szorzás a fentiekhez hasonló módon:

Ez lenne itt a másodfokú egyenletek megoldóképlete egy gráffal felírva.
A módszer látszólag bonyolult és lassú, de vannak előnyei.
 

  • Csak egy szöveg-szám konverziót tartalmaz
  • Könnyen fejleszthető további műveletekkel, függvényekkel
  • A gráf szám-elemei és a programnyelvben használt változók között megfeleltetések létesíthetők (pointerek kerülnek a számok helyére)
  • Nagymennyiségű hasonló művelet elvégzéséhez csak a kiolvasási műveletet kell ismételgetni, az adatszerkezetet csak egyszer kell felépíteni.
Gyakorlati megoldások
A gyakorlati megoldásokat én Pascalban illetve Delphi-ben követtem el, ennek nemes egyszerűséggel az az oka, hogy a C-t nem ismerem. Két módszerre szeretnék megoldást nyújtani, az egyik a lengyel formás értelmezési módszer, a másik az objektumorientált megoldás.

Lengyelforma

Unit Lengyel; INTERFACE
{a verem adatszerkezethez készült típusok}
Type   PVeremelem=^TVeremelem;   TVeremelem=Record     Ertek: Byte;     Ertek2: Real;     Next: PVeremelem;  End;  Verem=Record     First: PVeremelem;     Last: PVeremelem;  End;
{Hia konstansok}
Const   Er_DivBy0 = 1;   Er_Zarjel = 2;   er_Illegal= 3;Var   hiba: byte; Function GetResult(s: String): Real;{ Ez a függvény lengyelformát kap          }
{ paraméterként és az eredményt adja vissza}
Function MakePoland(s: String): String;
{ Kifejezésből lengyelforma }
Function isOK(s: String): Boolean;{ Egyszerű ellenőrző rutin }
 
IMPLEMENTATIONFunction isOK(s: String): Boolean;Var   i,zj: Integer;   Ok: Boolean;Begin   ok:=true;   zj:=0;   For i:=1 to Length(s) do  Begin     if s[i]='(' then Inc(zj);     if s[i]=')' then Dec(zj);     if not (s[i] in ['0'..'9','+','-','*','(',')','/',' ','.']) then Begin;ok:=false;hiba:=er_illegal;End;  End;   if zj<>0 then Begin;ok:=false;Hiba:=Er_zarjel;End;   if (pos('-+',s)<>0)  or (pos('---',s)<>0) or      (pos('+--',s)<>0) or (pos('-*',s)<>0) or      (pos('+*',s)<>0)  or (pos('**',s)<>0) or      (pos('++',s)<>0)  or (pos('()',s)<>0) or      (pos('(*',s)<>0)  or (pos('+)',s)<>0) or      (pos('*)',s)<>0)  or (pos('-)',s)<>0) or      (pos(')(',s)<>0)  or (pos('(+',s)<>0) then     Begin        ok:=false;        Hiba:=Er_illegal;     End;   isok:=ok;End;Procedure InitVerem(var v: Verem);Begin   v.first:=nil;   v.last:=nil;End;Function SeeFirst(var v: verem): byte;Begin   SeeFirst:=v.first^.ertek;End;Function GetFirst(var v: verem): Byte;Var   L: PVeremelem;Begin   GetFirst:=v.first^.ertek;   if v.first=v.last then exit;   l:=v.first;   v.first:=l^.next;   Dispose(l); End; Function SeeFirst2(var v: verem): Real;Begin   SeeFirst2:=v.first^.ertek2; End; Function GetFirst2(var v: verem): Real;Var   L: PVeremelem;Begin   GetFirst2:=v.first^.ertek2;   if v.first=v.last then exit;   l:=v.first;   v.first:=l^.next;   Dispose(l); End; Procedure NewToVerem(var v: verem;value: Byte);Var   P: PVeremElem;Begin   New(P);   p^.next:=nil;   P^.ertek:=value;   if v.first=nil then  Begin     p^.next:=nil;     v.first:=P;     v.Last:=P;  End   Else   Begin     P^.next:=v.first;     v.first:=P;  End; End;Procedure NewToVerem2(var v: verem;value: Real);Var   P: PVeremElem;Begin   New(P);   P^.ertek2:=value;   if v.first=nil then  Begin     p^.next:=nil;     v.first:=P;     v.Last:=P;  End   Else   Begin     P^.next:=v.first;     v.first:=P;  End; End;Const   opss: String='(+-*/)'; { Ez a függvény visszaadja a   paraméterként kapott   műveleti jel prioritását } Function prior(s: char): Byte;Begin   prior:=0;   if s='(' then prior:=1;   if ((s='-') or (s='+')) then prior:=2;   if ((s='*') or (s='/')) then prior:=3;   if s=')' then prior:=4;End;
 
{ Készítsünk lengyelformát } Function makePoland(s: String): String;Var   ss: String;  {Ide készül a lengyelforma }   i: Integer;   V: Verem;   j: Integer;Begin   InitVerem(v);   NewToVerem(v,0);   ss:='';   l:=1;   for i:=1 to Length(s) do  Begin     if s[i] in ['0'..'9','.'] then ss:=ss+s[i];
    { Ha számot találunk, azt egyszerűen átírjuk }
    if (s[i] in ['(',')','+','-','*','/']) then    Begin       if (ss[Length(ss)]<>' ') and (ss<>'') then ss:=ss+' ';       if s[i]<>')' then      Begin         { Ha  műveleti jelet találunk, a nálánál           nagyobb prioritással rendelkezőket           kivesszük a veremből és átírjuk a           lengyelformába...}         While (prior(opss[SeeFirst(v)])>=prior(s[i])) and (s[i]<>'(') do        Begin           ss:=ss+opss[GetFirst(v)]+' ';        End;         {...majd az aktuális műveleti jelet          lerakjuk a verembe }         NewToVerem(v,pos(s[i],opss));      End       Else       Begin         { Ha bezáró zárójelet találunk,           a nyitózárójelig minden műveleti           jelet átírunk a lengyelformába }         While opss[v.first^.ertek]<>'(' do        Begin           if Opss[SeeFirst(v)]<>'(' then ss:=ss+opss[GetFirst(v)]+' ';        End;         { A nyitózárójelet nem írjuk át,           de kivesszük a veremből }         GetFirst(v);      End;     End;   End;   { Kivesszük a veremből a maradék műveleti jeleket }   if (ss[Length(ss)]<>' ') and (ss<>'') then ss:=ss+' ';   while v.first<>v.last do ss:=ss+opss[GetFirst(v)]+' ';   makepoland:=ss;End;
 
{ Itt születik az eredmény } Function GetResult(s: String): Real;Var   v: Verem;   i: Integer;   sx: String;   code: Integer;   h: Real;   o1,o2: Real;Begin   InitVerem(v);   sx:='';   For i:=1 to Length(s) do   Begin     if s[i] in ['0'..'9','.'] then sx:=sx+s[i];    { A számokat kigyűjtjük egy       átemeti változóba (sx) }     if ((s[i]=' ') and (sx<>'')) then     Begin      { Ha egy szám véget ér,         lerakjuk a verembe }       Val(sx,h,code);       NewToVerem2(v,h);       sx:='';     End;     if s[i] in ['+','-','*','/'] then     Begin      { Ha műveleti jelet találunk,         az operandusokat kivesszük         a veremből...}       o2:=GetFirst2(v);       o1:=GetFirst2(v);       Case s[i] of       '+': o1:=o1+o2;       '*': o1:=o1*o2;       '-': o1:=o1-o2;       '/': Begin              if o2=0 then Hiba:=er_divby0 else o1:=o1/o2;            End; {...Elvégezzük a műveletet...}       End;       NewToVerem2(v,o1);      {...az eredményt lerakjuk a verembe}     End;   End;  { A kiértékelés végén kivesszük a veremből     az eredményt }   GetResult:=GetFirst2(v); End; End.
OOP-s megoldás
E probléma gyakorlati megvalósítása igényel némi magyarázatot, ugyanis az objektumorientáltságnak köszönhetően több adatszerkezetet is létre kell hoznunk.
Készítünk egy kifejezés-értelmező objektumot és több kifejezés-elem objektumot.
Lássuk a kifejezéselemeket! Ezek az objektumok egy közös típusból származnak, ezek valósítják meg a számokat, hivatkozásokat, alapműveleteket, függvényeket. A közös típusból való származtatásnak köszönhetően ezek az objektumok adatszerkezetekbe fűzhetők. A kifejezés-elemek alaptípusát én TKfAtom-nak neveztem el, a következő mezői és metódusai vannak:
 
Parent: PKfAtom a gráfban az objektum felett tartózkodó objektum címe
Op1, op2: PKfAtom az objektum két operandusa (már ha van neki)
Constructor Create A létrehozáshoz szükséges metódus, ez inicializálja a mezők kezdeti értékeit is.
Destructor Destroy Az adatszerkezet lebontásához szükséges metódus, benne az objektum meghívja az operandusaihoz tartozó Destroy metódusokat.
Function GetString: String Hibakeresési célzattal célszerű írni egy ilyen metódust, ami a faszerkezet alapján az eredeti kifejezéssel ekvivalens kifejezést ad vissza. (elméletileg )
Function GetValue: Single Ez szolgáltatja az eredményt. Legtöbb esetben úgy működik, hogy meghívja az operandusok azonos metódusát és azokon végzi el a műveleteket. Számoknál egyszerűen visszaadja a számot.
type   PKfAtom=^TKfAtom;   TKfAtom=object     Parent: PKfAtom;     Op1,Op2: PKfAtom;     Constructor Create;     Destructor Destroy; virtual;     Function GetString: String; virtual;     Function GetValue: Single; virtual;   end;

Mint említettem, a kifejezés-elem objektumokat gráfba fűzzük, többek között ezt a feladatot látja el a kifejezés-értelmező objektum. Lássuk a mezőket és metódusokat!
 
 

FirstAtom: PkfAtom A gráf csúcsán elhelyezkedő kifejezés-elem objektum címe. Ha ennek hívjuk a GetString illetve GetValue metódusait, az eredmények a teljes kifejezésre vonatkoznak.
Refs: TRefTable A bemutatott példában lehetőség van a programnyelv és a kifejezés változói közötti közvetlen megfeleltetésre, a Refs egy tömb, ami a kifejezésben használható változókat, konstansokat és a hozzájuk tartozó értékeket illetve változócímeket tartalmazza.
TRefTable=Record            Count: Byte;            Data: Array[1..255] of Record              Name: String[5];              Typ: Byte;              Value: Single;              Addr: Pointer;            end; end;
Constructor Create  A létrehozáshoz szükséges metódus, ez inicializálja a mezők kezdeti értékeit is.
Destructor Destroy Az adatszerkezet lebontásához szükséges metódus, benne az objektum meghívja a Clear metódust.
Procedure Clear A FirstAtom-hoz tartozó Destroy metódust hívja, így kiüríti a kifejezéshez tartozó fa szerkezetet
Procedure SetExpression
(s: String)
Ezt a metódust kell hívni, ha egy kifejezéshez tartozó adatszerkezetet szeretnénk felépíttetni.
Procedure AssignPascalRef
(typ: byte; 
name: String;
var Addr);
A Refs tömbbe vesz fel új változóhozzárendelést. A typ a változó típusát, a name a kifejezésben használható változónevet, a cím pedig a pascalos változót jelenti.
Procedure AssignConstant
(name: String; 
value: Single);
Új konstans hozzárendelést vesz fel a Refs tömbbe. A név a kifejezésben használható konstans neve, a value a konstanshoz tartozó érték.
Function GetString: String Az aktuális adatszerkezet alapján teljes kifejezést visszaadja szöveges formában. Gyakorlatilag a FirstAtom^.GetString
Function GetValue: Single Az aktuális gráf alapján kiszámítja a kifejezés értékét.FirstAtom^.GetValue
Procedure SetExp
(s: String;
var P: PKfAtom;
AParent: PKfAtom)
Ez egy védett metódus, valójában ez készít gráfot egy kifejezésből. Paraméterként megkapja a kiértékelendő kifejezést, egy a mutatót, amibe a kifejezéshez tartozó gráf csúcsát rakja, valamint megkapja a gráfban az aktuális kifejezés csúcsa feletti pont címét is.
  PKif=^TKif;   TKif=object     FirstAtom: PKfAtom;     Refs: TRefTable;     Constructor Create;     Destructor Destroy;     Procedure Clear; virtual;     Procedure SetExpression(s: String); virtual;     Procedure AssignPascalRef(typ: byte; name: String; var Addr); virtual;     Procedure AssignConstant(name: String; value: Single); virtual;     Function GetString: String; virtual;     Function GetValue: Single; virtual;   Protected     Procedure SetExp(s: String; var P: PKfAtom; AParent: PKfAtom); virtual;  end;
Az adatszerkezetek ismertetése után jöjjön a forráslista!
Unit GrtMath; interfacetype { Ez itt az alap kifejezés-elem objektum }   PKfAtom=^TKfAtom;   TKfAtom=object     Parent: PKfAtom;     Op1,Op2: PKfAtom;     Constructor Create;     Destructor Destroy; virtual;     Function GetString: String; virtual;     Function GetValue: Single; virtual;  end;{ A következő objektum a számokat fogja   reprezentálni az adatszerkezetben }   PErtek=^TErtek;   TErtek=object(TKfAtom)     Value: Single;     Function GetString: String; virtual;     Function GetValue: Single; virtual;  end;{ Összeadást, kivonást végző objektum.   A mode változó határozza meg, hogy   Összeadást vagy kivonást végez }   PPlusMinus=^TPlusMinus;   TPlusMinus=object(TKfAtom)     mode: Boolean;     Constructor
Create(amode: Boolean);     Function GetString: String; virtual;     Function GetValue: Single; virtual;  end;{ Szorzó/osztó objektum. Itt is a mode   változó értéke dönt, hogy szorzást   vagy osztást végzünk-e }   PSzorDiv=^TSzorDiv;   TSzorDiv=object(TPlusMinus)     Function GetString: String; virtual;     Function GetValue: Single; virtual;   end; { Ez az objektum írja le a függvényeket }   PFX=^TFX;   TFX=object(TKfAtom)     mode: Byte;     Constructor Create(amode: Byte);     Function GetString: String; virtual;     Function GetValue: Single; virtual;   end; { A következő objektum a változókat és   konstansokat reprezentálja.   A Ref a változó valódi címe,   A Value csak konstansoknál használatos,     A konstans valódi értékét tartalmazza   A mode írja le, hogy az objektum változó     Vagy konstans }   PRef=^TRef;   TRef=object(TKfAtom)     Ref: Pointer;     Value: Single;     mode: Byte;     Constructor Create(amode: Byte);     Function GetString: String; virtual;     Function GetValue: Single; virtual;   end;   TRefTable=Record               Count: Byte;               Data: Array[1..255] of Record                 Name: String[5];                 Typ: Byte;                 Value: Single;                 Addr: Pointer;               end;             end; { Ez az objektum a kifejezés-értékelő }   PKif=^TKif;   TKif=object     FirstAtom: PKfAtom;     Refs: TRefTable;     Constructor Create;     Destructor Destroy;     Procedure Clear; virtual;     Procedure SetExpression(s: String); virtual;     Procedure AssignPascalRef(typ: byte; name: String; var Addr); virtual;     Procedure AssignConstant(name: String; value: Single); virtual;     Function GetString: String; virtual;     Function GetValue: Single; virtual;   Protected     Procedure SetExp(s: String; var P: PKfAtom; AParent: PKfAtom); virtual;  end;Const   { A TFx objektumhoz tartozó függvénykonstansok }   fxSin  = 1;   fxCos  = 2;   fxTan  = 3;   fxSqr  = 4;   fxSqrt = 5;   fxLog  = 6;   fxExp  = 7;   fxAbs  = 8;   fxRnd  = 9;   { A Tref objektumhoz tartozó változótípus konstansok }   tpConst    = 0;   tpInteger  = 1;   tpReal     = 2;   tpSingle   = 3;   tpDouble   = 4;   tpExtended = 5; implementation
 
{ Ez még szöveges művelet, a kapott string-ből   kiszedi a dupla előjeleket } procedure KillPlusMinus(var s: string);begin   While pos('+-',s)<>0 do s:=Copy(s,1,pos('+-',s)-1)+'-'+Copy(s,pos('+-',s)+2,255);   While pos('-+',s)<>0 do s:=Copy(s,1,pos('-+',s)-1)+'-'+Copy(s,pos('+-',s)+2,255);   While pos('--',s)<>0 do s:=Copy(s,1,pos('--',s)-1)+'+'+Copy(s,pos('--',s)+2,255);   While pos('++',s)<>0 do s:=Copy(s,1,pos('++',s)-1)+'+'+Copy(s,pos('++',s)+2,255);end;{== ÖSSZEADÁS-KIVONÁS ===================================================} Constructor TPlusMinus.Create;begin   inherited Create;   mode:=amode;end; Function TPlusMinus.GetString: String;begin   if ((op1<>nil) and (op2<>nil)) then  begin     if mode then GetString:='('+op1^.GetString+'+'+op2^.GetString+')'             else GetString:='('+op1^.GetString+'-'+op2^.GetString+')';  end   else     GetString:='';end; Function TPlusMinus.GetValue: Single;begin   if ((op1<>nil) and (op2<>nil)) then  begin     if mode then GetValue:=op1^.GetValue+op2^.GetValue             else GetValue:=op1^.GetValue-op2^.GetValue;  end   else     GetValue:=0;end; {== SZORZÁS-OSZTÁS ======================================================} Function TSzorDiv.GetString: String;begin   if ((op1<>nil) and (op2<>nil)) then  begin     if mode then GetString:='('+op1^.GetString+'*'+op2^.GetString+')'            else GetString:='('+op1^.GetString+'/'+op2^.GetString+')';  end   else     GetString:='';end; Function TSzorDiv.GetValue: Single;var   s: Single;begin   if ((op1<>nil) and (op2<>nil)) then  begin     s:=op2^.GetValue;     if mode then GetValue:=op1^.GetValue*s            else if s<>0 then GetValue:=op1^.GetValue/s else GetValue:=0;  end   else     GetValue:=0;end; {== FÜGGVÉNYEK ==========================================================} Constructor TFx.Create;begin   inherited Create;   mode:=amode;end; Function TFX.GetString: String;var   s: string;begin   Case mode of   fxSin: s:='Sin(';   fxCos: s:='Cos(';   fxTan: s:='Tan(';   fxSqr: s:='Sqr(';   fxSqrt:s:='Sqrt(';   fxLog: s:='Ln(';   fxExp: s:='Exp(';   fxAbs: s:='Abs(';   fxRnd: s:='Rnd(';  end;   if op1<>nil then GetString:=s+op1^.GetString+')' else GetString:='Hiba';end; Function TFX.GetValue: Single;var   s: Single;   v,vv: Single;begin   if op1<>nil then  begin     s:=0;     v:=op1^.GetValue;     Case mode of     fxSin: s:=Sin(v);     fxCos: s:=Cos(v);     fxTan: begin              vv:=Cos(v);             if vv<>0 then s:=Sin(v)/vv else s:=0;            end;     fxSqr: s:=Sqr(v);     fxSqrt:if v>0 then s:=Sqrt(v) else s:=Sqrt(abs(v));     fxLog: if v<>0 then s:=Ln(v) else s:=0;     fxExp: if v<88 then s:=exp(v) else s:=100000000;     fxAbs: s:=Abs(v);     fxRnd: s:=Random(round(v));    end;     GetValue:=s;   end else GetValue:=0;end; {== SZÁMOK ==============================================================} Function TErtek.GetString: String;var   s: String;begin   Str(value:3:3,s);   GetString:=s;end; Function TErtek.GetValue: Single;begin   GetValue:=Value;end; {== VÁLTOZÓK, KONSTANSOK ================================================} Constructor TRef.Create;begin   inherited Create;   mode:=amode;end; Function TRef.GetString: String;var   Valu: Single;   s: String;begin   Valu:=0;   Case mode of   tpConst    : Valu:=Value;   tpInteger  : Valu:=Integer(ref^);   tpReal     : Valu:=Real(ref^);   tpSingle   : Valu:=Single(ref^);   tpDouble   : Valu:=Double(ref^);   tpExtended : Valu:=Extended(ref^);   end;  { A mód konstansok alapján dől el,     hogy pontosan hogyan kell lekérdezni     a mutatóhoz tartozó értéket }   Str(valu:4:3,s);   GetString:=s;end; Function TRef.GetValue: Single;begin   GetValue:=0;   Case mode of   tpConst    : GetValue:=value;   tpInteger  : GetValue:=Integer(ref^);   tpReal     : GetValue:=Real(ref^);   tpSingle   : GetValue:=Single(ref^);   tpDouble   : GetValue:=Double(ref^);   tpExtended : GetValue:=Extended(ref^);  end; end; {== A KIFEJEZÉS-ÉRTELMEZŐ OBJEKTUM ======================================} Constructor TKif.Create;begin   FirstAtom:=nil;   Refs.Count:=0;   AssignConstant('pi',pi);  { Változók inicializálása, a pi konstans felvétele     a Refs tömbbe } end;Destructor TKif.Destroy;begin   Clear;end;Procedure TKif.AssignConstant(name: String; value: Single);begin   if Refs.Count<255 then  begin     inc(Refs.Count);     Refs.Data[Refs.Count].Value:=Value;     Refs.Data[Refs.Count].Typ:=tpConst;     Refs.Data[Refs.Count].Name:=Name;  end; end;Procedure TKif.AssignPascalRef(typ: byte; name: String; var Addr);begin   if Refs.Count<255 then  begin     inc(Refs.Count);     Refs.Data[Refs.Count].Addr:=@Addr;     Refs.Data[Refs.Count].Typ:=Typ;     Refs.Data[Refs.Count].Name:=Name;  end; end;Function TKif.GetString: String;begin   if FirstAtom<>nil then GetString:=FirstAtom^.GetString else GetString:='üres kifejezés';  { A kifejezés megszerzése egyszerű, csak a FirstAtom     GetString metódusát kell meghívni } end;Function TKif.GetValue: Single;begin   if FirstAtom<>nil then GetValue:=FirstAtom^.GetValue else GetValue:=0;end;Procedure TKif.Clear;begin   if FirstAtom<>nil then FirstAtom^.Destroy;end;Procedure TKif.SetExpression(s: String);begin   Clear;   KillPlusMinus(s);   SetExp(s,FirstAtom,nil);  { A valódi munkát a SetExp metódus végzi,     itt is csak a SetExp-et hívjuk néhány     speciális paraméterrel } end;{ A következő metódus nem tartozik az   objektumhoz, csak azért került ide,   mert a következő metódusban fogjuk   használni. Egyébként azt dönti el,   hogy egy kifejezés zárójelben van-e   vagy sem } Function IsFlZjel(s: String): Boolean;var   i,j: integer;begin   IsFlZJel:=true;   if s<>'' then  begin     if s[1]='(' then    begin       j:=0;       for i:=1 to Length(s)-1 do      begin         if s[i]='(' then inc(j);         if s[i]=')' then dec(j);         if j=0 then IsFlZJel:=false;      end;     end else IsFlZJel:=false;  end; end;{ Ez a rutin végzi a valódi   kifejezés-értékelést } Procedure TKif.SetExp(s: String; var P: PKfAtom; AParent: PKfAtom);var   i,j: integer;   op1: string;   op2: string;   zs,zs2,c: Integer;   vn: Boolean;   value: Single;   q: PKfAtom;begin   zs:=0;   p:=nil;  { Először megnézzük, hogy a kifejezés tartalmaz-e     valamilyen műveleti jelet. Ha nem, akkor ez     vagy változó, vagy érték }   if (pos('+',Copy(s,2,255))=0) and (pos('-',Copy(s,2,255))=0) and      (pos('*',Copy(s,2,255))=0) and (pos('/',Copy(s,2,255))=0) and      (pos('(',Copy(s,2,255))=0) and (pos(')',Copy(s,2,255))=0) then  begin     { Megnézzük, hogy változó-e }     for i:=1 to Refs.Count do    begin       if ((s=Refs.Data[i].Name) and (p=nil)) then      begin         { Ha a kifejezés pontosan egyezik egy           változónévvel, akkor létrehozunk egy           új TRef objektumot és átadjuk neki           a változóhoz tartozó paramétereket }         p:=New(PRef, Create(Refs.Data[i].Typ));         PRef(p)^.Ref:=Refs.Data[i].Addr;         PRef(p)^.Value:=Refs.Data[i].Value;         p^.parent:=aparent;      end;     end;     if p=nil then    begin       { Ha nem változó, akkor valószínűleg szám         lesz a kifejezés, így egy TErtek objektumot         hozunk létre és ennek adjuk át a számot }       Val(s,value,c);       p:=New(PErtek,Create);       PErtek(p)^.value:=value;    end;   end   else   begin     { Ha a kifejezés bonyolultabb, akkor azt kicsit       komolyabb értékelő műveleteknek kell alávetni.       Először összeadást, kivonást keresünk }     for i:=1 to Length(s) do    begin       if s[i]='(' then inc(zs);       if s[i]=')' then dec(zs);      { A műveletek keresésénél csak a nulla         zárójelezettségi szinten lévő műveletek         számítanak }       if (s[i] in ['+','-']) and (i>1) and not (s[i-1] in ['*','/']) and (zs=0) then      begin    { Ha találtunk egy összeadást vagy kivonást, akkor       létrehozzuk a művelethez tartozó objektumot, majd           megkeressük a hozzá tartozó operandusokat (op1,op2) }         op1:='';         op2:='';   { A p=nil vizsgálat azért szükséges, mert lehet, hogy           több összeadás illetve kivonás van a kifejezésben, így           a második, harmadik stb. összeadásnál a p már nem nil           és ilyenkor másképp kell eljárni }         if p=nil then         begin           p:=New(PPlusMinus,Create(s[i]='+'));           p^.parent:=aparent;           vn:=true;           zs2:=0;     { Az objektumot létrehoztuk, keressük az első        operandust }           for j:=i-1 downto 1 do          begin             if s[j]='(' then inc(zs2);             if s[j]=')' then dec(zs2);             if (zs2=0) and (s[j] in ['+','-']) and (j>1) and not (s[j-1] in ['*','/']) then vn:=false;             if vn then op1:=s[j]+op1;          end;         end         else         begin           { Ha ez már a többedik művelet, akkor             a q-ba létrehozunk egy új műveletobjektumot,             aminek az első operandusa az előző művelet             eredménye lesz (a kifejezés balról jobbra             értékelődik ki) }           q:=New(PPlusMinus,Create(s[i]='+'));           q^.parent:=aparent;           p^.parent:=q;           q^.op1:=p;           p:=q;     { A p:=q sor azért kell, mert a programnak             a kifejezéshez tartozó gráf csúcsának             címét kell visszaadnia p-ben }         end;         vn:=true;         zs2:=0;   { A második operandus keresése }         for j:=i+1 to Length(s) do         begin           if s[j]='(' then inc(zs2);           if s[j]=')' then dec(zs2);           if (zs2=0) and (s[j] in ['+','-']) and              (j>1) and not (s[j-1] in ['*','/']) then vn:=false;           if vn then op2:=op2+s[j];        end;    { Ha megvannak az operandusok, ellenőrizzük, hogy           nincsekek-e egy az egyben zárójelben. Ha igen,           a zárójelet megszüntetjük }         if op1<>'' then           if IsFlZJel(op1) then op1:=Copy(op1,2,Length(op1)-2);         if op2<>'' then           if IsFlZJel(op2) then op2:=Copy(op2,2,Length(op2)-2);   { Az operandusként kapott kifejezésrészekkel meghíjuk           újra a kifejezésértelmezőt. Az op1 akkor üres,           ha ez a többedik összeadás, ugyanis ilyenkor           az első operandus már ki van értékelve }         if op1<>'' then SetExp(op1,P^.op1,p);         SetExp(op2,P^.op2,p);      end;     end;     { Ha a kifejezés nem tartalmazott összeadást       vagy kivonást, akkor szorzás, osztás szempontjából       vizsgálódunk. Ezt nem részletezném, mivel       kísértetiesen hasonlít az összeadás, kivonás       értékelésére }     if p=nil then    begin       zs:=0;       for i:=1 to Length(s) do      begin         if s[i]='(' then inc(zs);         if s[i]=')' then dec(zs);         if (s[i] in ['*','/']) and (zs=0) then        begin           op1:='';           op2:='';           if p=nil then          begin             p:=New(PSzorDiv,Create(s[i]='*'));             p^.parent:=aparent;             vn:=true;             zs2:=0;             for j:=i-1 downto 1 do            begin               if s[j]='(' then inc(zs2);               if s[j]=')' then dec(zs2);               if (zs2=0) and (s[j] in ['*','/']) then vn:=false;               if vn then op1:=s[j]+op1;            end;           end           else           begin             q:=New(PSzorDiv,Create(s[i]='*'));             q^.parent:=aparent;             p^.parent:=q;             q^.op1:=p;             p:=q;          end;           vn:=true;           zs2:=0;           for j:=i+1 to Length(s) do          begin             if s[j]='(' then inc(zs2);             if s[j]=')' then dec(zs2);             if (zs2=0) and (s[j] in ['*','/']) then vn:=false;             if vn then op2:=op2+s[j];          end;           if op1<>'' then              if IsFlZJel(op1) then op1:=Copy(op1,2,Length(op1)-2);           if op2<>'' then              if IsFlZJel(op2) then op2:=Copy(op2,2,Length(op2)-2);           if op1<>'' then SetExp(op1,P^.op1,p);           SetExp(op2,P^.op2,p);        end;       end;     end;   end;   { Ha a kifejezés nem változó és nem tartalmaz semmilyen     alapműveletet, akkor csakis függvény lehet... }   if p=nil then  begin     { Létrehozzuk a megfelelő függvényobjektumot... }     if Copy(s,1,3)='sin' then p:=New(PFx, Create(fxSin));

if Copy(s,1,3)='cos' then p:=New(PFx, Create(fxCos));

    if Copy(s,1,3)='tan' then p:=New(PFx, Create(fxTan));     if Copy(s,1,3)='sqr' then p:=New(PFx, Create(fxSqr));     if Copy(s,1,4)='sqrt' then p:=New(PFx, Create(fxSqrt));     if Copy(s,1,3)='log' then p:=New(PFx, Create(fxLog));     if Copy(s,1,3)='exp' then p:=New(PFx, Create(fxExp));     if Copy(s,1,3)='abs' then p:=New(PFx, Create(fxAbs));     if Copy(s,1,3)='rnd' then p:=New(PFx, Create(fxRnd));     if p<>nil then    begin       p^.Parent:=aparent;       op1:=Copy(s,4,255);       if Copy(op1,1,1)='t' then op1:=Copy(op1,2,255);       op1:=Copy(op1,2,Length(op1)-2);      {...majd kiértékeltetjük a paraméterét }       SetExp(op1,P^.op1,p);    end;   end; end; {== AZ ALAP KIFEJEZÉS-ELEM OBJEKTUM =====================================} Constructor TKfAtom.Create;begin   Parent:=nil;   Op1:=nil;   Op2:=nil;end; Destructor TKfAtom.Destroy;begin   if op1<>nil then op1^.Destroy;   if op2<>nil then op2^.Destroy;end; Function TKfAtom.GetString: String;begin   GetString:='';end; Function TKfAtom.GetValue: Single;begin   GetValue:=0;end; {== VÉGE ================================================================} end.

A bemutatott módszer kifejezés-értelmező része nincs optimalizálva (az sok kifejezésnél úgyis csak egyszer fut le), a függvények számítását is lehetne gyorsítani (pl.: sinustáblák használatával) de ez már nem ennek a cikknek a témája, másrészt az OOP-s módszer nagymennyiségű műveletnél még így is akár 50-szer gyorsabb lehet, mint a lengyelforma.