Čo je infixová notácia?
Infixový zápis je zápis, v ktorom je výraz napísaný v bežnom alebo normálnom formáte. Je to zápis, v ktorom operátory ležia medzi operandmi. Príklady infixovej notácie sú A+B, A*B, A/B atď.
Ako môžeme vidieť vo vyššie uvedených príkladoch, medzi operandmi existujú všetky operátory, takže ide o infixové zápisy. Preto možno syntax infixovej notácie zapísať ako:
Analýza výrazov Infix
Aby sme mohli analyzovať akýkoľvek výraz, musíme sa postarať o dve veci, tj. Prednosť operátora a Asociativita . Prednosť operátora znamená prednosť ktoréhokoľvek operátora pred iným operátorom. Napríklad:
čiastočná diferenciácia v latexe
A + B * C → A + (B * C)
Keďže operátor násobenia má vyššiu prioritu pred operátorom sčítania, výraz B * C bude vyhodnotený ako prvý. Výsledok násobenia B * C sa pripočíta k A.
Prednostné poradie
| Operátori | Symboly |
|---|---|
| Zátvorky | { }, ( ), [ ] |
| Exponenciálny zápis | ^ |
| Násobenie a delenie | *, / |
| Sčítanie a odčítanie | +, - |
Asociativita znamená, že vo výraze existujú operátory s rovnakou prioritou. Napríklad vo výraze, t. j. A + B - C, majú operátory '+' a '-' rovnakú prednosť, takže sa vyhodnocujú pomocou asociativity. Keďže '+' aj '-' sú ľavo-asociatívne, budú hodnotené ako (A + B) - C.
Poradie asociatívnosti
| Operátori | Asociativita |
|---|---|
| ^ | Zprava doľava |
| *, / | Zľava doprava |
| +, - | Zľava doprava |
Poďme pochopiť asociativitu na príklade.
1 + 2*3 + 30/5
Keďže vo vyššie uvedenom výraze majú * a / rovnakú prednosť, použijeme pravidlo asociativity. Ako môžeme vidieť vo vyššie uvedenej tabuľke, operátory * a / majú asociatívnosť zľava doprava, takže budeme skenovať od operátora úplne vľavo. Operátor, ktorý príde ako prvý, bude vyhodnotený ako prvý. Operátor * sa objaví pred operátorom / a násobenie sa vykoná ako prvé.
1+ (2*3) + (30/5)
1+6+6 = 13
Čo je predponová notácia?
Predponová notácia je iná forma výrazu, ale nevyžaduje ďalšie informácie, ako je priorita a asociativita, zatiaľ čo infixová notácia vyžaduje informáciu o priorite a asociativite. Je tiež známy ako poľská notácia . V predponovom zápise je operátor pred operandmi. Syntax prefixovej notácie je uvedená nižšie:
Napríklad, ak je infixový výraz 5+1, potom predponový výraz zodpovedajúci tomuto infixovému výrazu je +51.
Ak je infixový výraz:
a * b + c
↓
*ab+c
↓
+*abc (výraz predpony)
Zvážte ďalší príklad:
A + B * C
konverzia reťazca na int v jazyku Java
Prvý sken: Vo vyššie uvedenom výraze má operátor násobenia vyššiu prioritu ako operátor sčítania; predponový zápis B*C by bol (*BC).
A + *BC
Druhé skenovanie: V druhom skenovaní by predpona bola:
+A *BC
Vo vyššie uvedenom výraze používame dva skeny na konverziu výrazu infix na výraz prefix. Ak je výraz zložitý, potom požadujeme väčší počet skenov. Musíme použiť metódu, ktorá vyžaduje iba jedno skenovanie a poskytuje požadovaný výsledok. Ak dosiahneme požadovaný výstup jedným skenovaním, algoritmus by bol efektívny. To je možné iba pomocou zásobníka.
Konverzia Infixu na Prefix pomocou Stack
K + L - M * N + (O^P) * W/U/V * T + Q
diagram modelu e-r
Ak konvertujeme výraz z infixu na predponu, musíme výraz najskôr obrátiť.
Obrátený výraz by bol:
Q + T* V/U/W*) P^O(+ N*M - L + K
Na získanie predponového výrazu sme vytvorili tabuľku, ktorá pozostáva z troch stĺpcov, t. j. vstupného výrazu, zásobníka a predponového výrazu. Keď narazíme na akýkoľvek symbol, jednoducho ho pridáme do predponového výrazu. Ak narazíme na operátora, zatlačíme ho do zásobníka.
| Vstupný výraz | Stoh | Predponový výraz |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| V | +* | QTV |
| / | +*/ | QTV |
| IN | +*/ | QTVU |
| / | +*// | QTVU |
| IN | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| P | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| O | +*//*)^ | QTVUWPO |
| ( | +*//* | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| N | ++ | QTVUWPO^*//*N |
| * | +** | QTVUWPO^*//*N |
| M | +** | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| L | ++- | QTVUWPO^*//*NM*L |
| + | +-+ | QTVUWPO^*//*NM*L |
| K | +-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK+-++ |
Vyššie uvedený výraz, t.j. QTVUWPO^*//*NM*LK+-++, nie je konečným výrazom. Tento výraz musíme obrátiť, aby sme získali predponový výraz.
Pravidlá pre prevod výrazu infix na predponu:
- Najprv zmeňte infixový výraz uvedený v probléme.
- Naskenujte výraz zľava doprava.
- Vždy, keď prídu operandy, vytlačte ich.
- Ak príde operátor a zistí sa, že stoh je prázdny, potom ho jednoducho zatlačte do stohu.
- Ak má operátor prichádzajúcej pošty vyššiu prioritu ako TOP zásobníka, zatlačte operátora prichádzajúcej pošty do zásobníka.
- Ak má operátor prichádzajúcej pošty rovnakú prioritu s TOP zásobníka, zatlačte operátora prichádzajúcej pošty do zásobníka.
- Ak má operátor prichádzajúcej pošty nižšiu prioritu ako HORNÁ časť stohu, otvorte ju a vytlačte hornú časť stohu. Znovu otestujte prichádzajúci operátor oproti hornej časti zásobníka a vyberte operátor zo zásobníka, kým nenájde operátor s nižšou alebo rovnakou prioritou.
- Ak má operátor prichádzajúcej pošty rovnakú prioritu ako horná časť zásobníka a operátor prichádzajúcej pošty je ^, potom otvárajte hornú časť zásobníka, kým nie je podmienka pravdivá. Ak podmienka nie je pravdivá, stlačte operátor ^.
- Keď sa dostaneme na koniec výrazu, vyskočíme a vytlačíme všetky operátory z vrchu zásobníka.
- Ak je operátor ')', zatlačte ho do zásobníka.
- Ak je operátor '(', potom vyberte všetky operátory zo zásobníka, kým nenájde ) otváraciu zátvorku v zásobníku.
- Ak je horná časť stohu ')', zatlačte operátora na stoh.
- Na konci otočte výstup.
Pseudokód konverzie infixu na predponu
Function InfixtoPrefix( stack, infix) infix = reverse(infix) loop i = 0 to infix.length if infix[i] is operand → prefix+= infix[i] else if infix[i] is '(' → stack.push(infix[i]) else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found else if infix[i] is an operator(+, -, *, /, ^) → if the stack is empty then push infix[i] on the top of the stack. Else → If precedence(infix[i] > precedence(stack.top)) → Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) && infix[i] == '^') → Pop and print the top values of the stack till the condition is true → Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) → Push infix[i] on to the stack Else if(infix[i] <precedence(stack.top)) → pop the stack values and print them till is not empty infix[i] < precedence(stack.top) push on to end loop remaining elements of prefix="reverse(prefix)" return pre> <hr></precedence(stack.top))>