TechCodeview

Než pochopíme převod z infixové na postfixovou notaci, měli bychom vědět o infixové a postfixové notaci samostatně.

Infix a postfix jsou výrazy. Výraz se skládá z konstant, proměnných a symbolů. Symboly mohou být operátory nebo závorky. Všechny tyto komponenty musí být uspořádány podle sady pravidel, aby bylo možné všechny tyto výrazy vyhodnotit pomocí sady pravidel.

Příklady výrazů jsou:

5 + 6

A – B

(P * 5)

Všechny výše uvedené výrazy mají společnou strukturu, tj. mezi dvěma operandy máme operátor. Operand je objekt nebo hodnota, na které má být operace provedena. Ve výše uvedených výrazech jsou 5, 6 operandy, zatímco '+', '-' a '*' jsou operátory.

průměr vs průměr

Co je infixová notace?

Když je operátor zapsán mezi operandy, pak je známý jako infixový zápis . Operand nemusí být vždy konstanta nebo proměnná; může to být i samotný výraz.

Například,

(p + q) * (r + s)

Ve výše uvedeném výrazu jsou oba výrazy operátoru násobení operandy, tj. (p + q) , a (r + s) jsou operandy.

Ve výše uvedeném výrazu jsou tři operátory. Operandy pro první operátor plus jsou p a q, operandy pro druhý operátor plus jsou r a s. Při provádění operací s výrazem, musíme pro vyhodnocení výsledku dodržet nějakou sadu pravidel. V nad výrazem by byla provedena operace sčítání na dvou výrazech, tj. p+q a r+s, a poté by byla provedena operace násobení.

Syntaxe infixové notace je uvedena níže:

Pokud je ve výrazu pouze jeden operátor, nevyžadujeme použití žádného pravidla. Například 5 + 2; v tomto výrazu lze provést operaci sčítání mezi dvěma operandy (5 a 2) a výsledek operace by byl 7.

Pokud je ve výrazu více operátorů, pak je pro vyhodnocení výrazu potřeba dodržet nějaké pravidlo.

Pokud je výraz:

4+6*2

Pokud je nejprve vyhodnocen operátor plus, bude výraz vypadat takto:

10 * 2 = 20

Pokud je nejprve vyhodnocen operátor násobení, bude výraz vypadat takto:

4 + 12 = 16

Výše uvedený problém lze vyřešit dodržováním pravidel přednosti operátora. V algebraickém výrazu je pořadí priorit operátorů uvedeno v následující tabulce:

První přednost je dána závorce; pak další přednost je dána exponentům. V případě vícenásobných exponentů bude operace aplikována zprava doleva.

Například:

2^2^3 = 2^8

= 256

Po exponentu, násobení a dělení jsou vyhodnoceny operátory. Pokud jsou ve výrazu přítomny oba operátory, bude operace aplikována zleva doprava.

Další předností je sčítání a odčítání. Pokud jsou ve výrazu k dispozici oba operátory, jdeme zleva doprava.

Operátory, které mají stejnou prioritu, se nazývají jako asociativnost operátorů . Pokud jdeme zleva doprava, pak se to nazývá levá asociativní. Jdeme-li zprava doleva, pak se nazývá pravá asociativní.

Problém s infixovým zápisem

Abychom mohli vyhodnotit infixový výraz, měli bychom vědět o přednost operátora pravidla, a pokud mají operátoři stejnou přednost, měli bychom se řídit asociativnost pravidla. Použití závorek je velmi důležité v infixové notaci pro kontrolu pořadí, ve kterém má být operace provedena. Závorky zlepšují čitelnost výrazu. Infixový výraz je nejběžnějším způsobem zápisu výrazu, ale není snadné analyzovat a vyhodnotit infixový výraz bez nejasností. Matematici a logici tedy studovali tento problém a objevili dva další způsoby psaní výrazů, kterými jsou předpona a přípona. Oba výrazy nevyžadují žádné závorky a lze je bez dvojznačnosti analyzovat. Nevyžaduje pravidla priority operátorů a asociativnosti.

Postfixový výraz

Postfixový výraz je výraz, ve kterém je operátor zapsán za operandy. Například postfixový výraz infixové notace ( 2+3) lze zapsat jako 23+.

Některé klíčové body týkající se výrazu postfix jsou:

• V postfixovém výrazu se operace provádějí v pořadí, v jakém byly zapsány zleva doprava.
• Nevyžaduje žádné závorky.
• Nemusíme uplatňovat pravidla priority operátorů a pravidla asociativnosti.

Algoritmus pro vyhodnocení postfixového výrazu

• Skenujte výraz zleva doprava, dokud nenarazíme na jakýkoli operátor.
• Proveďte operaci
• Nahraďte výraz jeho vypočítanou hodnotou.
• Opakujte kroky 1 až 3, dokud nebudou existovat žádné další operátory.

Pojďme pochopit výše uvedený algoritmus na příkladu.

Infixový výraz: 2 + 3 * 4

Začneme skenovat většinu výrazu zleva. Operátor násobení je operátor, který se objeví jako první při skenování zleva doprava. Nyní by výraz byl:

jak najít blokovaná čísla na android

Výraz = 2 + 34*

= 2 + 12

Opět budeme skenovat zleva doprava a výraz bude:

Výraz = 2 12 +

= 14

Vyhodnocení postfixového výrazu pomocí zásobníku.

• Naskenujte výraz zleva doprava.
• Pokud ve výrazu narazíme na nějaký operand, pak operand vložíme do zásobníku.
• Když ve výrazu narazíme na jakýkoli operátor, vytáhneme odpovídající operandy ze zásobníku.
• Když skončíme se skenováním výrazu, konečná hodnota zůstane v zásobníku.

Pojďme pochopit vyhodnocení postfixového výrazu pomocí zásobníku.

Příklad 1: Postfixový výraz: 2 3 4 * +

Výsledkem výše uvedeného výrazu je 14.

Příklad 2: Postfixový výraz: 3 4 * 2 5 * +

Výsledkem výše uvedeného výrazu je 22.

Algoritmus pro vyhodnocení postfixového výrazu

1. Přečtěte si postavu
2. Pokud je znakem číslice, převeďte znak na int a vložte celé číslo do zásobníku.
3. Pokud je znakem operátor,
   • Vyberte prvky ze zásobníku dvakrát a získáte dva operandy.
   • Proveďte operaci
   • Vložte výsledek do zásobníku.

Převod infixu na postfix

Zde použijeme datovou strukturu zásobníku pro převod infixového výrazu na prefixový výraz. Kdykoli se operátor setká, vtlačíme operátora do zásobníku. Pokud narazíme na operand, pak operand připojíme k výrazu.

Pravidla pro převod z infixu na postfixový výraz

1. Vytiskněte operand, jakmile dorazí.
2. Pokud je zásobník prázdný nebo obsahuje levou závorku nahoře, zatlačte operátora příchozí pošty na zásobník.
3. Pokud je příchozí symbol '(', posuňte jej do zásobníku.
4. Pokud je příchozí symbol ')', vysuňte zásobník a tiskněte operátory, dokud nenajdete levou závorku.
5. Pokud má příchozí symbol vyšší prioritu než horní část hromádky, zatlačte jej na hromádku.
6. Pokud má příchozí symbol nižší prioritu než horní část stohu, zvýrazněte a vytiskněte horní část stohu. Poté otestujte příchozí operátor proti novému vrcholu zásobníku.
7. Pokud má příchozí operátor stejnou prioritu jako horní část zásobníku, použijte pravidla asociativity. Pokud je asociativita zleva doprava, pak vyklopte a vytiskněte horní část zásobníku a poté stiskněte příchozí operátor. Pokud je asociativita zprava doleva, stiskněte příchozí operátor.
8. Na konci výrazu vyberte a vytiskněte všechny operátory zásobníku.

Pojďme to pochopit na příkladu.

Infixový výraz: K + L - M*N + (O^P) * 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+ .