Predtým, ako pochopíme konverziu z infixovej na postfixovú notáciu, mali by sme vedieť o infixovej a postfixovej notácii oddelene.
t flip flop
Infix a postfix sú výrazy. Výraz sa skladá z konštánt, premenných a symbolov. Symboly môžu byť operátory alebo zátvorky. Všetky tieto komponenty musia byť usporiadané podľa súboru pravidiel, aby bolo možné všetky tieto výrazy vyhodnotiť pomocou súboru pravidiel.
Príklady výrazov sú:
5 + 6
A – B
(P * 5)
Všetky vyššie uvedené výrazy majú spoločnú štruktúru, t.j. medzi týmito dvoma operandami máme operátor. Operand je objekt alebo hodnota, na ktorej sa má operácia vykonať. Vo vyššie uvedených výrazoch sú 5, 6 operandy, zatiaľ čo '+', '-' a '*' sú operátory.
Čo je infixová notácia?
Keď je operátor zapísaný medzi operandy, potom je známy ako infixový zápis . Operand nemusí byť vždy konštanta alebo premenná; môže to byť aj samotný výraz.
Napríklad,
(p + q) * (r + s)
Vo vyššie uvedenom výraze sú oba výrazy operátora násobenia operandy, t.j. (p + q) , a (r + s) sú operandy.
Vo vyššie uvedenom výraze existujú tri operátory. Operandy pre prvý plusový operátor sú p a q, operandy pre druhý plusový operátor sú r a s. Počas vykonávania operácie s výrazom, musíme na vyhodnotenie výsledku dodržať určitý súbor pravidiel. V nad výrazom, operácia sčítania by sa vykonala na dvoch výrazoch, t.j. p+q a r+s, a potom by sa vykonala operácia násobenia.
Syntax infixovej notácie je uvedená nižšie:
Ak je vo výraze iba jeden operátor, nevyžadujeme použitie žiadneho pravidla. Napríklad 5 + 2; v tomto výraze je možné vykonať operáciu sčítania medzi dvoma operandmi (5 a 2) a výsledok operácie by bol 7.
Ak je vo výraze viacero operátorov, na vyhodnotenie výrazu je potrebné dodržať nejaké pravidlo.
Ak je výraz:
4+6*2
Ak sa najprv vyhodnotí operátor plus, výraz bude vyzerať takto:
10 * 2 = 20
Ak sa operátor násobenia vyhodnotí ako prvý, výraz bude vyzerať takto:
4 + 12 = 16
Vyššie uvedený problém možno vyriešiť dodržiavaním pravidiel priority operátora. V algebraickom výraze je poradie priority operátorov uvedené v tabuľke nižšie:
| Operátori | Symboly |
|---|---|
| Zátvorky | ( ), {}, [ ] |
| Exponenty | ^ |
| Násobenie a delenie | *, / |
| Sčítanie a odčítanie | + , - |
Prvá prednosť sa dáva zátvorke; potom sa uprednostnia exponenty. V prípade viacerých exponentov sa operácia použije sprava doľava.
čo je 10 z 1 milióna
Napríklad:
2^2^3 = 2^8
= 256
Po exponente, násobení a delení sa vyhodnotia operátory. Ak sú vo výraze prítomné obidva operátory, operácia sa použije zľava doprava.
Ďalšou prednosťou je sčítanie a odčítanie. Ak sú vo výraze dostupné obidva operátory, ideme zľava doprava.
Operátori, ktorí majú rovnakú prioritu, sa nazývajú ako operátorská asociativita . Ak ideme zľava doprava, potom je to známe ako ľavo-asociatívne. Ak ideme sprava doľava, potom je to známe ako pravo-asociatívne.
Problém s infixovým zápisom
Na vyhodnotenie infixového výrazu by sme mali vedieť o prednosť operátora pravidlá, a ak majú operátori rovnakú prednosť, potom by sme sa mali riadiť asociatívnosť pravidlá. Použitie zátvoriek je veľmi dôležité v infixovom zápise na kontrolu poradia, v ktorom sa má operácia vykonať. Zátvorky zlepšujú čitateľnosť výrazu. Infixový výraz je najbežnejším spôsobom písania výrazu, ale nie je jednoduché analyzovať a vyhodnotiť infixový výraz bez nejednoznačnosti. Matematici a logici teda študovali tento problém a objavili dva ďalšie spôsoby písania výrazov, ktorými sú predpona a postfix. Oba výrazy nevyžadujú žiadne zátvorky a možno ich analyzovať bez nejednoznačnosti. Nevyžaduje pravidlá priority operátorov a asociatívnosti.
Postfixový výraz
Postfixový výraz je výraz, v ktorom je operátor zapísaný za operandy. Napríklad postfixový výraz infixovej notácie ( 2+3) možno zapísať ako 23+.
Niektoré kľúčové body týkajúce sa výrazu postfix sú:
- V postfixovom výraze sa operácie vykonávajú v poradí, v akom sa písali zľava doprava.
- Nevyžaduje žiadne zátvorky.
- Nepotrebujeme uplatňovať pravidlá priority operátorov a pravidlá asociácie.
Algoritmus na vyhodnotenie postfixového výrazu
previesť reťazec na int
- Skenujte výraz zľava doprava, kým nenájdeme operátora.
- Vykonajte operáciu
- Nahraďte výraz jeho vypočítanou hodnotou.
- Opakujte kroky 1 až 3, kým nebudú existovať žiadne ďalšie operátory.
Poďme pochopiť vyššie uvedený algoritmus prostredníctvom príkladu.
Vložený výraz: 2 + 3 * 4
Väčšinu výrazu začneme skenovať zľava. Operátor násobenia je operátor, ktorý sa objaví ako prvý pri skenovaní zľava doprava. Teraz by výraz bol:
Výraz = 2 + 34*
= 2 + 12
Opäť budeme skenovať zľava doprava a výraz bude:
programovanie cobol
Výraz = 2 12 +
= 14
Vyhodnotenie postfixového výrazu pomocou zásobníka.
- Naskenujte výraz zľava doprava.
- Ak sa vo výraze stretneme s akýmkoľvek operandom, potom operand vložíme do zásobníka.
- Keď sa vo výraze stretneme s ľubovoľným operátorom, vytiahneme zodpovedajúce operandy zo zásobníka.
- Keď skončíme so skenovaním výrazu, konečná hodnota zostane v zásobníku.
Poďme pochopiť vyhodnotenie postfixového výrazu pomocou zásobníka.
Príklad 1: Postfixový výraz: 2 3 4 * +
| Vstup | Stoh | |
|---|---|---|
| 2 3 4 * + | prázdny | Stlačiť 2 |
| 3 4 * + | 2 | Stlačiť 3 |
| 4*+ | 3 2 | Stlačiť 4 |
| * + | 4 3 2 | Pop 4 a 3 a vykonajte 4*3 = 12. Zatlačte 12 do zásobníka. |
| + | 12 2 | Vyberte 12 a 2 zo zásobníka a vykonajte 12+2 = 14. Zatlačte 14 do zásobníka. |
Výsledkom vyššie uvedeného výrazu je 14.
Príklad 2: Postfixový výraz: 3 4 * 2 5 * +
| Vstup | Stoh | |
|---|---|---|
| 3 4 * 2 5 * + | prázdny | Stlačiť 3 |
| 4*2 5*+ | 3 | Stlačiť 4 |
| *2 5 * + | 4 3 | Vyberte 3 a 4 zo zásobníka a vykonajte 3*4 = 12. Zatlačte 12 do zásobníka. |
| 2 5 * + | 12 | Stlačiť 2 |
| 5*+ | 2 12 | Stlačiť 5 |
| *+ | 5 2 12 | Vyberte 5 a 2 zo zásobníka a vykonajte 5*2 = 10. Zatlačte 10 do zásobníka. |
| + | 10 12 | Vyberte 10 a 12 zo zásobníka a vykonajte 10+12 = 22. Zatlačte 22 do zásobníka. |
Výsledkom vyššie uvedeného výrazu je 22.
Algoritmus na vyhodnotenie postfixového výrazu
- Prečítajte si postavu
- Ak je znakom číslica, konvertujte znak na int a vložte celé číslo do zásobníka.
- Ak je znakom operátor,
- Vyberte prvky zo zásobníka dvakrát, čím získate dva operandy.
- Vykonajte operáciu
- Výsledok zatlačte do zásobníka.
Konverzia infixu na postfix
Tu použijeme dátovú štruktúru zásobníka na konverziu infixového výrazu na prefixový výraz. Kedykoľvek sa operátor stretne, vtlačíme operátora do zásobníka. Ak sa stretneme s operandom, potom operand pripojíme k výrazu.
Pravidlá pre prevod z výrazu infix na výraz postfix
- Vytlačte operand, keď prídu.
- Ak je zásobník prázdny alebo obsahuje navrchu ľavú zátvorku, zatlačte operátora prichádzajúcej správy na zásobník.
- Ak je prichádzajúci symbol '(', zatlačte ho na zásobník.
- Ak je prichádzajúci symbol ')', otvorte zásobník a tlačte operátory, kým nenájdete ľavú zátvorku.
- Ak má prichádzajúci symbol vyššiu prioritu ako horná časť stĺpca, zatlačte ho na stĺpec.
- Ak má prichádzajúci symbol nižšiu prioritu ako horná časť stohu, otvorte a vytlačte hornú časť stohu. Potom otestujte prichádzajúci operátor s novým vrcholom zásobníka.
- Ak má prichádzajúci operátor rovnakú prioritu ako horná časť zásobníka, použite pravidlá asociativity. Ak je asociativita zľava doprava, vytlačte a vytlačte hornú časť zásobníka a potom stlačte operátor prichádzajúcej pošty. Ak je asociativita sprava doľava, stlačte prichádzajúci operátor.
- Na konci výrazu vyberte a vytlačte všetky operátory zásobníka.
Poďme to pochopiť na príklade.
Infixný výraz: K + L - M*N + (O^P) * W/U/V * T + Q
| Vstupný výraz | Stoh | Postfixový výraz |
|---|---|---|
| K | K | |
| + | + | |
| L | + | K L |
| - | - | K L+ |
| M | - | K L+ M |
| * | -* | K L+ M |
| N | -* | K L + M N |
| + | + | K L + M N* K L + M N* - |
| ( | + ( | K L + M N *- |
| O | + ( | KL + M N * - O |
| ^ | + (^ | KL + M N* - O |
| P | + (^ | KL + M N* - O P |
| ) | + | KL + M N* - O P^ |
| * | + * | KL + M N* - O P^ |
| IN | + * | KL + M N* - O P ^ W |
| / | + / | K L + M N* - O P ^ W * |
| IN | + / | KL + M N* - O P ^W*U |
| / | + / | K L + M N* - O P ^W*U/ |
| V | + / | KL + MON*-UP^W*U/F |
| * | + * | KL+MON*-UP^W*U/F/ |
| T | + * | KL+MN*-UP^W*U/F/T |
| + | + | KL+MON*-UP^W*U/F/T* KL+MN*-UP^W*U/F/T*+ |
| Q | + | KL+MN*-OP^W*U/V/T*Q |
| KL+MN*-OP^W*U/V/T*+Q+ |
Konečný postfixový výraz infixového výrazu (K + L - M*N + (O^P) * W/U/V * T + Q) je KL+MN*-OP^W*U/V/T*+Q+ .