Co je infixová notace?

Infixový zápis je zápis, ve kterém je výraz zapsán v obvyklém nebo normálním formátu. Je to zápis, ve kterém operátory leží mezi operandy. Příklady infixové notace jsou A+B, A*B, A/B atd.

Jak můžeme vidět na výše uvedených příkladech, všechny operátory existují mezi operandy, takže jde o infixové zápisy. Proto lze syntaxi infixové notace zapsat jako:

Analýza výrazů Infix

Abychom mohli analyzovat jakýkoli výraz, musíme se postarat o dvě věci, tj. Přednost operátora a Asociativnost . Přednost operátora znamená přednost jakéhokoli operátora před jiným operátorem. Například:

A + B * C → A + (B * C)

Protože operátor násobení má vyšší prioritu před operátorem sčítání, výraz B * C bude vyhodnocen jako první. Výsledek násobení B * C se přičte k A.

Přednostní pořadí

Asociativita znamená, že ve výrazu existují operátory se stejnou prioritou. Například ve výrazu, tj. A + B - C, mají operátory '+' a '-' stejnou přednost, takže jsou vyhodnocovány pomocí asociativity. Protože '+' i '-' jsou asociativní vlevo, budou vyhodnoceny jako (A + B) - C.

Pořadí asociativnosti

Pojďme pochopit asociativitu na příkladu.

1 + 2*3 + 30/5

Protože ve výše uvedeném výrazu mají * a / stejnou přednost, použijeme pravidlo asociativity. Jak můžeme ve výše uvedené tabulce pozorovat, že operátory * a / mají asociativitu zleva doprava, budeme skenovat od operátoru nejvíce vlevo. Operátor, který přijde jako první, bude vyhodnocen jako první. Operátor * se objeví před operátorem / a nejprve se provede násobení.

1+ (2*3) + (30/5)

1+6+6 = 13

Co je předponová notace?

Předponová notace je další forma výrazu, ale nevyžaduje další informace, jako je priorita a asociativita, zatímco infixová notace vyžaduje informace o prioritě a asociativitě. Je také známý jako polská notace . V předponové notaci je operátor před operandy. Syntaxe předponového zápisu je uvedena níže:

Například, pokud je infixový výraz 5+1, pak je předponový výraz odpovídající tomuto infixovému výrazu +51.

Pokud je infixový výraz:

a * b + c

↓

*ab+c

↓

+*abc (výraz předpony)

Zvažte další příklad:

A + B * C

První sken: Ve výše uvedeném výrazu má operátor násobení vyšší prioritu než operátor sčítání; předponový zápis B*C by byl (*BC).

A + *BC

Druhý sken: Při druhém skenování by předpona byla:

+A *BC

Ve výše uvedeném výrazu používáme dvě skenování k převodu infixu na prefixový výraz. Pokud je výraz složitý, vyžadujeme větší počet skenů. Musíme použít metodu, která vyžaduje pouze jedno skenování a poskytuje požadovaný výsledek. Pokud dosáhneme požadovaného výstupu jedním skenem, pak by byl algoritmus efektivní. To je možné pouze pomocí zásobníku.

Převod Infixu na Prefix pomocí Stack

K + L - M * N + (O^P) * W/U/V * T + Q

Pokud převádíme výraz z infixu na předponu, musíme nejprve výraz obrátit.

Opačný výraz by byl:

Q + T * V/U/W *) P^O(+ N*M - L + K

Pro získání předponového výrazu jsme vytvořili tabulku, která se skládá ze tří sloupců, tj. vstupní výraz, zásobník a předponový výraz. Když narazíme na jakýkoli symbol, jednoduše jej přidáme do předponového výrazu. Pokud narazíme na operátora, strčíme ho do zásobníku.

náhodné číslo v java

Výše uvedený výraz, tj. QTVUWPO^*//*NM*LK+-++, není konečným výrazem. Musíme tento výraz obrátit, abychom získali výraz předpony.

Pravidla pro převod výrazu infix na prefix:

• Nejprve změňte infixový výraz uvedený v problému.
• Naskenujte výraz zleva doprava.
• Kdykoli operandy dorazí, vytiskněte je.
• Pokud operátor dorazí a zjistí se, že stoh je prázdný, jednoduše zatlačte obsluhu do stohu.
• Pokud má operátor příchozí pošty vyšší prioritu než TOP zásobníku, zatlačte operátora příchozí pošty do zásobníku.
• Pokud má příchozí operátor stejnou prioritu s TOP zásobníku, zatlačte operátora příchozí pošty do zásobníku.
• Pokud má operátor příchozí pošty nižší prioritu než horní část zásobníku, vysuňte a vytiskněte horní část zásobníku. Znovu otestujte příchozí operátor proti horní části zásobníku a vytáhněte operátor ze zásobníku, dokud nenajde operátor s nižší prioritou nebo stejnou prioritou.
• Pokud má příchozí operátor stejnou prioritu jako horní část zásobníku a operátor příchozí pošty je ^, pak horní část zásobníku rozbalte, dokud není podmínka pravdivá. Pokud podmínka neplatí, stiskněte operátor ^.
• Když se dostaneme na konec výrazu, vyskočíme a vytiskneme všechny operátory z horní části zásobníku.
• Pokud je operátor ')', zatlačte jej do zásobníku.
• Pokud je operátorem '(', pak vytáhněte všechny operátory ze zásobníku, dokud nenajde ) otevírací závorku v zásobníku.
• Pokud je horní část stohu ')', zatlačte operátora na stoh.
• Na konci otočte výstup.

Pseudokód převodu infixu na předponu

 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))>