Informatika gyűjtemény

Egy szinttel feljebb 30. óra - Kifejezés kiértékelés

2004050607080910

<<  30. óra - Kifejezés kiértékelés  >>

<<  Feladatok  >>

NézetNyomtat

30. óra - Kifejezés kiértékelés
Címkék > Óra

29. óra - Kifejezés kiértékelés

Kriván Bálint
Utólag belepiszkált: Erben Péter

Bevezetés

  1. Mit akarunk?
    Kifejezéseket kiértékelni.
  2. Mi az a kifejezés?
    A kifejezés egy olyan karaktersorozat, ami egy matematikai műveletsort ír le. A kifejezésben szerepelhetnek számkonstansok, műveleti jelek, zárójelek, haladó szinten pedig függvények és változónevek is. A kifejezéseket szeretjük infix alakban felírni. Ez azt jelenti,hogy ha egy művelet kétváltozós, akkor a két operandus közé írjuk a műveleti jelet. Például:
    1+2
    Az is jó, hogy lehet zárójelezni:
    1+2*(3-4)/(5*(6+7))
  3. Mit szeretnénk a kifejezésekkel kezdeni?
    Olyan programot írunk, ami helyesen értelmezi a kifejezést, és meghatározza az értékét. Itt több fontos részlet pontosítandó:
    • Mi a teendő, ha a kifejezés hibás, tehát nem felel meg a matematika szabályainak?
    • Mi a teendő, ha a kiértékelés során nem megengedett műveletet kellene végezni (például osztás nullával)?
    • Milyen számhalmazban keressük a végeredményt? Egész? Racionális? Dupla pontos "valós"?
  4. Miért jó ez?
    Ha sikerül algoritmikusan kiértékelni kifejezéseket, akkor tudunk olyan programot írni, ami mondjuk egy felhasználó által begépelt függvényt ábrázol. Készíthetünk nagypontosságú számológépet is.
  5. Hogy a legjobb?
    A kifejezést úgynevezett fordított lengyel formára hozzuk, majd ezt már egyszerű kiértékelni. A fordított lengyel forma elkészítésekor kiderülnek a formai (szintaktikai) hibák, és megszabadulunk a zárójelektől.

Tokenizálás

A kifejezések kiértékelésekor már nem karakterekkel, hanem tokenekkel szeretnénk dolgozni. A tokenek meghatározása a tokenizálás, más néven lexikális elemzés. Egy kifejezésben a következő tokenek fordulhatnak elő:
  • Szám. Lehet egész vagy tizedestört, esetleg a normálalak is megengedett.
  • Zárójel.
  • Műveleti jel. Egyváltozós vagy kétváltozós lehet.
  • Függvény név.
  • Függvény argumentumokat elválasztó vessző.
A tokenizálás egy lehetséges megoldása: token.java.

A tokenizálás során felmerülő kérdések és problémák

  • Megengedünk-e olyan számkonstansokat, amelyek értéke feltehetően meghaladja a gépünk által ábrázolható legnagyobb (például 64-bites) értéket? Tehát hibaüzenetet adunk-e a következő kifejezésre:
    123456789123456789123456789000000000+1
  • Ha függvényeket is akarunk használni, akkor hogyan különböztetjük meg a függvényparamétereket elválasztó vesszőt a tizedes vesszőtől?
    3,14 + max(3,14, 4)
    Egy programozó persze bátran használ pontot a tizedes vessző helyett, de ez nem csak rajta múlik, bizonyos nyelvek (például C#) beépített "nemzetköziesítéssel" vannak ellátva, és tudják, hogy Magyarországon vessző van pont helyett. Az ilyen nyelveknél a tokenizálás után a pontot vissza kell cserélni vesszőre.
  • Használunk-e negatív számokat, vagy az "unáris minusz" segítségével valósítjuk meg őket? Halmozhatjuk-e az unáris minuszokat?
    12+-----------23
  • Használunk-e normálalakot?
    42*6E23

Infixből Postfix avagy lengyelformára hozás

Ha lefutott a lexikális elemzés, akkor adott tokenek (elemek) egy sorozata. Ebből fogjuk előállítani a fordított lengyel formát. (A szaknyelv röviden lengyelformának is nevezi ezt.)

Példa

INFIXPOSTFIX
(8 + 2 * 5)/(1 + 3 * 2 - 4) 8 2 5 * + 1 3 2 * + 4 - /

Algoritmus

Shunting-yard algoritmus ("rendező pályaudvar")

Részletek

Tehát az algoritmus:
  • Amíg van elem, addig olvasunk:
    • Beolvasunk egy elemet.
    • Ha szám, akkor betesszük a kimeneti sorba.
    • Ha egy függvény, akkor betesszük a verembe.
    • Ha egy vessző (több argumentumos függvény):
      • Amíg a verem tetején nem találunk egy nyitó zárójelet, addig betesszük az összes operátort a kimeneti sorba. Ha nem találunk nyitó zárójelet, akkor hibás a kifejezés.
    • Ha egy operátor (o1), akkor:
      • Amíg van egy o2 operátor a verem tetején, és:
        - o1 jobbról asszociatív és a precedenciája kisebb, mint o2-nek, vagy
        - o1 nem asszociatív jobbról és a precedenciája kisebb vagy egyenlő o2-val, akkor:
        o2-et kivesszük a veremből és betesszük a kimeneti sorba;
      • o1-et betesszük a verembe
    • Ha egy nyitó zárójel, akkor betesszük a verembe.
    • Ha egy záró zárójel:
      • Amíg az elem nem nyitó zárojel, betesszük a veremből a sorba.
      • Kivesszük a nyitót a veremből
      • Ha a következő elem függvény, akkor betesszük a sorba
      • Ha nem találtunk nyitó zárójelet, akkor az kínos -> hibás kifejezés
  • Ha már nincs elem a bemenetből:
    • Amíg van még operátor a veremben:
      • Ha az operátor egy zárójel, akkor hibás a kifejezés
      • Kivesszük a veremből és betesszük a kimeneti sorba.
  • Vége.
Precedenciához: Jelen esetben én nagyobb számmal jelölöm a fontosabbat, ez lehet, hogy máshol nem így van. (prioritásnál általában kisebb a fontosabb, ezt mindenki maga döntse el, hogy neki hogy szimpatikusabb)

Postfix kiértékelése

  1. Az első részével megvagyunk, most ezt szeretnénk használni
  2. Praktikusan legyünk képesek egy csak konstansokból álló kifejezést kiértékelni, tehát: (8 + 2 * 5)/(1 + 3 * 2 - 4) bemenetre mondjuk azt, hogy: 6
  3. Tehát itt jön a kiértékelés algoritmusa, itt kitérünk az operátorok (1 és 2 argumentumú - unáris, bináris) szerepére, függvények stb.
Ha ez hamar kész van, akkor lehet játszadozni, számológépet írni, függvény-ábrázolót kreálni (persze mint házi feladat). Akár az operandusoknál bevezetni nem csak konstanst, hanem ismeretleneket is (szimbolikus kiértékelés). De ezt nem tervezem órán, csak felvetjük, hogy van erre lehetőség, ha megfelelően generikusan oldjuk meg a problémákat. (Például már a legelejétől nem feltételezzük, hogy konkrét számokkal számolunk)