Mielőtt megértené az infixről postfix jelölésre való átalakítást, külön kell ismernünk az infix és a postfix jelöléseket.

Az infix és postfix a kifejezések. Egy kifejezés konstansokból, változókból és szimbólumokból áll. A szimbólumok lehetnek operátorok vagy zárójelek. Mindezeket az összetevőket egy szabálykészlet szerint kell elrendezni, hogy ezek a kifejezések kiértékelhetők legyenek a szabálykészlet segítségével.

Példák a kifejezésekre:

5 + 6

A-B

(P * 5)

Az összes fenti kifejezésnek közös a szerkezete, azaz van egy operátorunk a két operandus között. Az operandus egy objektum vagy érték, amelyen a műveletet végre kell hajtani. A fenti kifejezésekben az 5, 6 az operandusok, míg a '+', '-' és '*' az operátorok.

Mi az infix jelölés?

Ha az operátort az operandusok közé írjuk, akkor az úgynevezett infix jelölés . Az operandusnak nem kell mindig állandónak vagy változónak lennie; maga is kifejezés lehet.

Például,

script shell végrehajtása

(p + q) * (r + s)

A fenti kifejezésben a szorzási operátor mindkét kifejezése az operandus, azaz (p + q) , és (r + s) az operandusok.

A fenti kifejezésben három operátor található. Az első plusz operátor operandusai p és q, a második plusz operátor operandusai r és s. Végrehajtása közben a műveleteket a kifejezésen, követnünk kell néhány szabályt az eredmény értékeléséhez. Ban,-ben A fenti kifejezésnél összeadási műveletet hajtunk végre a két kifejezésen, azaz a p+q és az r+s, majd a szorzási műveletet hajtjuk végre.

Az infix jelölések szintaxisa az alábbiakban látható:

Ha csak egy operátor van a kifejezésben, akkor nincs szükség szabály alkalmazására. Például 5 + 2; ebben a kifejezésben a két operandus (5 és 2) között összeadási művelet végezhető, és a művelet eredménye 7 lenne.

Ha több operátor van a kifejezésben, akkor a kifejezés kiértékeléséhez bizonyos szabályokat kell követni.

Ha a kifejezés:

4+6*2

Ha először a plusz operátor kerül kiértékelésre, akkor a kifejezés így néz ki:

10 * 2 = 20

Ha először a szorzási operátort értékeljük ki, akkor a kifejezés így néz ki:

4 + 12 = 16

A fenti probléma megoldható az operátori elsőbbségi szabályok betartásával. Az algebrai kifejezésben az operátor elsőbbségének sorrendjét az alábbi táblázat adja meg:

Elsősorban a zárójelet részesítjük előnyben; akkor a következő előnyben részesítik a kitevőket. Több kitevő operátor esetén a művelet jobbról balra kerül alkalmazásra.

Például:

2^2^3 = 2^8

= 256

A kitevő után a szorzás és az osztás operátorait értékeljük. Ha mindkét operátor jelen van a kifejezésben, akkor a művelet balról jobbra kerül alkalmazásra.

A következő előnyben részesítik az összeadást és a kivonást. Ha mindkét operátor elérhető a kifejezésben, akkor balról jobbra haladunk.

Azok az operátorok, amelyeknek ugyanaz a prioritása, mint operátor asszociativitás . Ha balról jobbra haladunk, akkor ezt bal-asszociatívnak nevezzük. Ha jobbról balra haladunk, akkor jobbra-asszociatívnak nevezzük.

Probléma az infix jelöléssel

Az infix kifejezés értékeléséhez tudnunk kell a operátori elsőbbség szabályokat, és ha az operátorok elsőbbsége megegyezik, akkor kövessük a asszociativitás szabályokat. A zárójelek használata nagyon fontos az infix jelöléseknél, hogy szabályozzuk a művelet végrehajtásának sorrendjét. A zárójel javítja a kifejezés olvashatóságát. Az infix kifejezés a kifejezés írásának legáltalánosabb módja, de nem könnyű az infix kifejezést kétértelműség nélkül elemezni és kiértékelni. Tehát a matematikusok és a logikusok tanulmányozták ezt a problémát, és felfedeztek két másik módot a kifejezések írására, amelyek az elő- és az utótag. Mindkét kifejezés nem igényel zárójelet, és kétértelműség nélkül értelmezhető. Nem igényel operátori elsőbbséget és asszociativitási szabályokat.

Postfix kifejezés

A postfix kifejezés olyan kifejezés, amelyben az operátor az operandusok után van írva. Például az infix jelölés (2+3) postfix kifejezése 23+-ként írható fel.

Néhány kulcsfontosságú pont a postfix kifejezéssel kapcsolatban:

• A postfix kifejezésben a műveletek a balról jobbra írt sorrendben hajtódnak végre.
• Nem igényel zárójelet.
• Nem kell alkalmaznunk az operátor elsőbbségi és asszociativitási szabályokat.

Algoritmus a postfix kifejezés kiértékelésére

• Vizsgálja meg a kifejezést balról jobbra, amíg nem találkozunk operátorral.
• Hajtsa végre a műveletet
• Cserélje ki a kifejezést a számított értékére.
• Ismételje meg a lépéseket 1-től 3-ig, amíg már nem lesz több operátor.

Értsük meg a fenti algoritmust egy példán keresztül.

Infix kifejezés: 2 + 3 * 4

A szkennelést a kifejezés nagy részének bal oldaláról kezdjük. A szorzási operátor egy olyan operátor, amely először jelenik meg balról jobbra haladva. Most a kifejezés a következő lenne:

Kifejezés = 2 + 34*

= 2 + 12

Ismét balról jobbra szkennelünk, és a kifejezés a következő lenne:

Kifejezés = 2 12 +

= 14

Postfix kifejezés kiértékelése verem segítségével.

• Olvassa be a kifejezést balról jobbra.
• Ha bármilyen operandust találunk a kifejezésben, akkor az operandust a verembe toljuk.
• Ha bármilyen operátorral találkozunk a kifejezésben, akkor kidobjuk a megfelelő operandusokat a veremből.
• Amikor befejeztük a kifejezés beolvasását, a végső érték a veremben marad.

Ismerjük meg a postfix kifejezés kiértékelését verem segítségével.

1. példa: Postfix kifejezés: 2 3 4 * +

A fenti kifejezés eredménye 14.

2. példa: Postfix kifejezés: 3 4 * 2 5 * +

A fenti kifejezés eredménye 22.

Algoritmus a postfix kifejezés kiértékelésére

1. Olvass egy karaktert
2. Ha a karakter egy számjegy, alakítsa át a karaktert int-re, és nyomja be az egész számot a verembe.
3. Ha a karakter operátor,
   • Kétszer emelje ki az elemeket a veremből, így két operandust kap.
   • Hajtsa végre a műveletet
   • Tolja az eredményt a verembe.

Az infix átalakítása postfixre

Itt a verem adatszerkezetet fogjuk használni az infix kifejezések prefix kifejezésekké való átalakítására. Amikor egy operátor találkozik, betoljuk az operátort a verembe. Ha operandussal találkozunk, akkor az operandust hozzáfűzzük a kifejezéshez.

Szabályok az infixről postfix kifejezésre való átalakításhoz

1. Nyomtassa ki az operandust, amint megérkeznek.
2. Ha a verem üres, vagy bal oldali zárójelet tartalmaz a tetején, tolja a bejövő operátort a veremre.
3. Ha a bejövő szimbólum '(', akkor tolja a verembe.
4. Ha a bejövő jel a ')', ugorja ki a veremet, és nyomtassa ki az operátorokat, amíg meg nem találja a bal zárójelet.
5. Ha a bejövő szimbólumnak nagyobb a prioritása, mint a verem tetejének, nyomja rá a veremre.
6. Ha a bejövő szimbólum prioritása kisebb, mint a verem teteje, nyissa ki és nyomtassa ki a verem tetejét. Ezután tesztelje a bejövő operátort a verem új tetejével szemben.
7. Ha a bejövő operátor elsőbbsége megegyezik a verem tetejével, akkor használja az asszociativitási szabályokat. Ha az asszociativitás balról jobbra halad, akkor nyissa ki és nyomtassa ki a verem tetejét, majd nyomja meg a bejövő operátort. Ha az asszociativitás jobbról balra történik, akkor nyomja meg a bejövő operátort.
8. A kifejezés végén nyissa ki és nyomtassa ki a verem összes operátorát.

Értsük meg egy példán keresztül.

Infix kifejezés: K + L - M*N + (O^P) * W/U/V * T + Q

Az infix kifejezés végső utófix kifejezése (K + L - M*N + (O^P) * W/U/V * T + Q) KL+MN*-OP^W*U/V/T*+Q+ .