Van-e erre lehetőség (inv. lengyel logika)?
Egyértelműsitett matematikai, logikai kifejezéseket (expressions) szeretnék eltárolni, de nem a szokott módon, bináris fában, hanem láncolt listában.
Akik profibbak ezen a téren, azok szerint vajon lehetséges ez?
válasza:Az 1D tömb NEM láncolt lista.
A láncolt lista lényege, hogy pointerekkel (vagy referenciákkal, olymindegy) vannak láncolva a memoriában külön helyen tárolt elemei, ergo pl simán ki tudsz venni egy elemet a közepéről, de nem tudod indexelni (konstans időben).
Na a tömb, az ennek pont az ellentéte.
Olvasgass még kicsit a témában, mert így nagyon fölöslegesem beszélgetünk (a semmiről).
Tudod, vannak programnyelvek, amelyekben eleve ismeretlen fogalom a pointer.
Láncolt lista ezekben is megvalósitható, jobbára úgy, hogy az adatelemből és egy uint indexből képezel egy struktúrát, ami az alapjául szolgál egy dinamikus (vagy statikus) tömbnek.
Mi ebben a furcsa?
A tömböt te indexeled, mint fejlesztő, de a felhasználó már úgy használja, és csak úgy, ahogy te ezt lehetővé teszed neki. Ő nem fog indexelni semmit.
Lásd: stack tömbös megvalósitása.
Ezt irod:
"A láncolt lista lényege, hogy pointerekkel (vagy referenciákkal, olymindegy) vannak láncolva a memoriában külön helyen tárolt elemei, ergo pl simán ki tudsz venni egy elemet a közepéről, de nem tudod indexelni (konstans időben)."
Nem tudom, ebben mi jelentősége van a memóriabeli elhelyezkedésnek?
Az elem kivétel, vagy betoldás tömbös megvalósitás esetén is ugyanaz, mint pointer esetében. A listaindexet irod át. Ennyi.
Az indexelhetőség hiánya meg nem érdeme a láncolt listának. Emliteni is fölösleges volt.
válasza:Áhá! Megértettem mire gondolsz.
"Tudod, vannak programnyelvek, amelyekben eleve ismeretlen fogalom a pointer."
Ez egyébként nem igaz, a legtöbb nyelvben van valami referencia típus, egyedül a funkcionális nyelvekben nem, de ott azért mert az adat immutable így nem is lenne értelme, de ez most lényegtelen.
Gyakorlatilag a tömböt egy "virtuális memóriának" használod és pointerek helyett sima tömbindexek a mutatók. Szerintem ennek nincs sok értelme, de oké.
Most akkor végülis azt akarjuk, hogy ugyanaz a lista bejárható legyen infix meg postfix módon is ha jól értem. Ez meg eléggé egyszerű, hisz csak szimplán két különböző "next" mutatód lesz a struktúrában.
struct Node {
T data;
int infixNext; // ugye ez a következő elemre "mutat" infix módon
int postfixNext; // ez meg postfix módon
}
Szóval pl arra a bemenetre, hogy 3 + 2:
Ugye infixben ez: 3 + 2
Postfixben: 3 2 +
Szóval a Nodeok azok:
index| data | infixNext | postfixNext
0 | 3 | 1 | 2
1 | + | 2 | -1
2 | 2 | -1 | 1
A táblázat nem lesz szép valószínüleg. -1-el a "nullpointert" jelöltem.
Köszönöm, értékelem a segitő szándékot, de úgy vélem, az én megoldásom érthetőbb is és egyszerűbb is.
Ha van egy kifejezés, mondjuk
infix: 8 - ( 2 * 3 ) + 1
pstfx: 8 2 3 * - 1 +
Akkor ezt kiirom egy láncolt listába egy az egyben (csak zárójel nélkül): 8 - 2 * 3 + 1
Ennek a listaindexelt tartalma 8[1], -[2], 2[3], *[4], 3[5], +[6], 1[7]
Ebből lesz egy újm a pstfx-nek megfelelő szekvencia.
Ha ezen a listán végigmegy valaki:
8 [1], - [2], 2 [3], * [4], 3 [5], + [6], 1 [7]
Akkor visszakapja a kifejezést, zárójelek nélkül:
8 - 2 * 3 + 1
az indexek átirásával (8 [3], ...) meg a postfix formát, amit már könnyedén kiértékelhet bárki.
válasza:Most komolyan az a nap megfejtése, hogy beírod egy kifejezés elemeit egy tömbbe sorban?
Ráadásul a zárójeleket elhagyva, ami miatt ugye rossz eredményt fog adni.
Most komoly, hogy emiatt a bohóckodás miatt tornáztunk ezen ennyit?!?
Te még a dolog megértéséig se jutottál el.
A kifejezés "felbontása" elkezdődik, ezzel párhuzamosan kerül láncolt listába kiirásra a kifejezés, végül a láncolt lista bejárási sorrendje változik csak, igy alakul ki a postfix forma.
Kapcsolódó kérdések:
Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!