Č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

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

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.

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 &#x2192; prefix+= infix[i] else if infix[i] is &apos;(&apos; &#x2192; stack.push(infix[i]) else if infix[i] is &apos;)&apos; &#x2192; pop and print the values of stack till the symbol &apos;)&apos; is not found else if infix[i] is an operator(+, -, *, /, ^) &#x2192; if the stack is empty then push infix[i] on the top of the stack. Else &#x2192; If precedence(infix[i] &gt; precedence(stack.top)) &#x2192; Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) &amp;&amp; infix[i] == &apos;^&apos;) &#x2192; Pop and print the top values of the stack till the condition is true &#x2192; Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) &#x2192; 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))>