Što je infiksna notacija?
Infiksna notacija je notacija u kojoj je izraz napisan u uobičajenom ili normalnom formatu. To je zapis u kojem se operatori nalaze između operanda. Primjeri infiksnog zapisa su A+B, A*B, A/B itd.
ssh puni oblik
Kao što možemo vidjeti u gornjim primjerima, svi operatori postoje između operanda, tako da su infiks zapisi. Stoga se sintaksa infiks notacije može napisati kao:
Raščlanjivanje Infiks izraza
Kako bismo raščlanili bilo koji izraz, moramo voditi računa o dvije stvari, tj. Prioritet operatora i Asocijativnost . Prednost operatora znači prednost bilo kojeg operatora nad drugim operatorom. Na primjer:
A + B * C → A + (B * C)
Budući da operator množenja ima veću prednost nad operatorom zbrajanja, B * C izraz će se prvi procijeniti. Rezultat množenja B * C dodaje se A.
Redoslijed prvenstva
| Operatori | Simboli |
|---|---|
| Zagrada | {}, (), [] |
| Eksponencijalni zapis | ^ |
| Množenje i dijeljenje | *, / |
| Zbrajanje i oduzimanje | +, - |
Asocijativnost znači kada u izrazu postoje operatori s istim prvenstvom. Na primjer, u izrazu, tj. A + B - C, '+' i '-' operatori imaju isti prioritet, pa se procjenjuju uz pomoć asocijativnosti. Budući da su i '+' i '-' lijevo-asocijativni, ocijenili bi se kao (A + B) - C.
Redoslijed asocijativnosti
| Operatori | Asocijativnost |
|---|---|
| ^ | S desna na lijevo |
| *, / | S lijeva nadesno |
| +, - | S lijeva nadesno |
Razumimo asocijativnost kroz primjer.
1 + 2*3 + 30/5
Budući da u gornjem izrazu * i / imaju isti prioritet, primijenit ćemo pravilo asocijativnosti. Kao što možemo vidjeti u gornjoj tablici da * i / operatori imaju asocijativnost slijeva na desno, pa ćemo skenirati od krajnjeg lijevog operatora. Operator koji prvi dođe prvi će biti ocijenjen. Operator * pojavljuje se prije operatora /, a množenje bi se prvo izvršilo.
1+ (2*3) + (30/5)
1+6+6 = 13
Što je prefiksna notacija?
Prefiksna notacija je još jedan oblik izražavanja, ali ne zahtijeva druge informacije kao što su prvenstvo i asocijativnost, dok infiksna notacija zahtijeva informacije o prednosti i asocijativnosti. Također je poznat kao poljski zapis . U prefiksnoj notaciji, operator dolazi ispred operanda. Sintaksa notacije prefiksa data je u nastavku:
Na primjer, ako je infiks izraz 5+1, tada je prefiks izraz koji odgovara ovom infiks izrazu +51.
Ako je infiks izraz:
a * b + c
↓
*ab+c
↓
+*abc (prefiksni izraz)
Razmotrite još jedan primjer:
A + B * C
Prvo skeniranje: U gornjem izrazu, operator množenja ima veći prioritet od operatora zbrajanja; prefiksni zapis za B*C bio bi (*BC).
A + *BC
Drugo skeniranje: U drugom skeniranju, prefiks bi bio:
+A * pr
U gornjem izrazu koristimo dva skeniranja za pretvaranje infiksa u prefiks izraz. Ako je izraz složen, tada nam je potreban veći broj skeniranja. Moramo koristiti onu metodu koja zahtijeva samo jedno skeniranje, a daje željeni rezultat. Ako postignemo željeni rezultat jednim skeniranjem, tada bi algoritam bio učinkovit. To je moguće samo korištenjem hrpe.
Pretvorba infiksa u prefiks pomoću skupa
K + L - M * N + (O^P) * W/U/V * T + Q
Ako pretvaramo izraz iz infiksa u prefiks, prvo moramo obrnuti izraz.
Obrnuti izraz bi bio:
Q + T * V/U/W * ) P^O(+ N*M - L + K
vrste binarnog stabla
Da bismo dobili prefiksni izraz, kreirali smo tablicu koja se sastoji od tri stupca, tj. ulazni izraz, stog i prefiksni izraz. Kada naiđemo na bilo koji simbol, jednostavno ga dodamo u prefiksni izraz. Ako naiđemo na operatora, gurnut ćemo ga u stog.
| Ulazni izraz | Stog | Prefiksni izraz |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| U | +* | QTV |
| / | +*/ | QTV |
| U | +*/ | QTVU |
| / | +*// | QTVU |
| U | +*// | 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+-++ |
Gornji izraz, tj. QTVUWPO^*//*NM*LK+-++, nije konačni izraz. Moramo obrnuti ovaj izraz da bismo dobili prefiksni izraz.
Pravila za pretvorbu infiksa u prefiks izraz:
- Prvo obrnite infiks izraz dat u problemu.
- Skenirajte izraz s lijeva na desno.
- Kad god operandi stignu, ispišite ih.
- Ako operater stigne i ustanovi se da je stog prazan, jednostavno ga gurnite u stog.
- Ako dolazni operator ima veću prednost od VRHA stoga, gurnite dolaznog operatora u stog.
- Ako dolazni operator ima istu prednost s VRHOM stoga, gurnite dolaznog operatora u stog.
- Ako dolazni operator ima nižu prednost od VRHA niza, iskočite i ispišite vrh niza. Ponovno testirajte dolazni operator u odnosu na vrh snopa i izbacite operator s snopa dok ne pronađe operator s nižim ili istim prioritetom.
- Ako dolazni operator ima isti prioritet kao i vrh stoga, a dolazni operator je ^, tada iskačite vrh stoga dok uvjet nije istinit. Ako uvjet nije istinit, pritisnite operator ^.
- Kada dođemo do kraja izraza, iskočimo i ispišemo sve operatore s vrha niza.
- Ako je operator ')', gurnite ga u stog.
- Ako je operator '(', izbaci sve operatore sa stoga dok ne pronađe ) otvarajuću zagradu u stogu.
- Ako je vrh snopa ')', gurnite operator na snop.
- Na kraju obrnite izlaz.
Pseudokod pretvorbe infiksa u prefiks
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))>