Kaj je infiksni zapis?
Infiksni zapis je zapis, v katerem je izraz zapisan v običajni ali običajni obliki. To je zapis, v katerem so operatorji med operandi. Primeri zapisa infiksa so A+B, A*B, A/B itd.
Kot lahko vidimo v zgornjih primerih, vsi operatorji obstajajo med operandi, torej so infiksni zapisi. Zato lahko sintakso infiksnega zapisa zapišemo kot:
Razčlenjevanje Infix izrazov
Da bi razčlenili katerikoli izraz, moramo poskrbeti za dve stvari, tj. Prednost operaterja in Asociativnost . Prednost operaterja pomeni prednost katerega koli operatorja pred drugim operaterjem. Na primer:
A + B * C → A + (B * C)
Ker ima operator množenja višjo prednost pred operatorjem seštevanja, bo najprej ovrednoten izraz B * C. Rezultat množenja B * C se doda A.
Prednostni vrstni red
| Operaterji | Simboli |
|---|---|
| Oklepaj | { }, ( ), [ ] |
| Eksponentni zapis | ^ |
| Množenje in deljenje | *, / |
| Seštevanje in odštevanje | +, - |
Asociativnost pomeni, da v izrazu obstajajo operatorji z enako prednostjo. Na primer, v izrazu, tj. A + B - C, imata operatorja '+' in '-' enako prednost, zato sta ovrednotena s pomočjo asociativnosti. Ker sta tako '+' kot '-' levo asociativna, bi bila ovrednotena kot (A + B) - C.
Vrstni red asociativnosti
| Operaterji | Asociativnost |
|---|---|
| ^ | Od desne proti levi |
| *, / | Od leve proti desni |
| +, - | Od leve proti desni |
Razumejmo asociativnost na primeru.
formatni niz java
1 + 2*3 + 30/5
Ker imata v zgornjem izrazu * in / enako prednost, bomo uporabili pravilo asociativnosti. Kot lahko opazimo v zgornji tabeli, imata operatorja * in / asociativnost od leve proti desni, zato bomo skenirali od skrajno levega operatorja. Prvi bo ocenjen operater, ki bo prvi. Operator * se pojavi pred operatorjem / in najprej se izvede množenje.
1+ (2*3) + (30/5)
1+6+6 = 13
Kaj je zapis predpone?
Predponski zapis je druga oblika izražanja, vendar ne zahteva drugih informacij, kot sta prednost in asociativnost, medtem ko infiksni zapis zahteva informacije o prednosti in asociativnosti. Znan je tudi kot poljski zapis . V zapisu s predponami je operator pred operandi. Sintaksa zapisa predpone je podana spodaj:
na primer če je infiksni izraz 5+1, potem je predponski izraz, ki ustreza temu infiksnemu izrazu, +51.
Če je infiksni izraz:
a * b + c
↓
*ab+c
↓
+*abc (predponski izraz)
t ff
Razmislite o drugem primeru:
A + B * C
Prvo skeniranje: V zgornjem izrazu ima operator množenja višjo prednost kot operator seštevanja; predponski zapis B*C bi bil (*BC).
A + *BC
Drugi pregled: Pri drugem skeniranju bi bila predpona:
+A *BC
V zgornjem izrazu uporabljamo dva skeniranja za pretvorbo infiksa v predpono. Če je izraz kompleksen, potrebujemo večje število skeniranj. Uporabiti moramo tisto metodo, ki zahteva samo eno skeniranje in zagotavlja želeni rezultat. Če z enim skeniranjem dosežemo želeni rezultat, bi bil algoritem učinkovit. To je mogoče le z uporabo sklada.
Pretvorba Infiksa v Predpono z uporabo sklada
K + L - M * N + (O^P) * W/U/V * T + Q
Če pretvarjamo izraz iz infiksa v predpono, moramo izraz najprej obrniti.
Obratni izraz bi bil:
Q + T * V/U/W * ) P^O(+ N*M - L + K
Za pridobitev predponskega izraza smo ustvarili tabelo, ki je sestavljena iz treh stolpcev, tj. vhodnega izraza, sklada in predponskega izraza. Ko naletimo na kateri koli simbol, ga preprosto dodamo v predponski izraz. Če naletimo na operaterja, ga bomo potisnili v sklad.
| Vhodni izraz | Stack | Predponski izraz |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| IN | +* | 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+-++ |
Zgornji izraz, tj. QTVUWPO^*//*NM*LK+-++, ni končni izraz. Ta izraz moramo obrniti, da dobimo predponski izraz.
Pravila za pretvorbo infiksa v predpono:
- Najprej obrnite infiksni izraz, podan v težavi.
- Preglejte izraz od leve proti desni.
- Ko prispejo operandi, jih natisnite.
- Če pride operater in se ugotovi, da je sklad prazen, preprosto potisnite operaterja v sklad.
- Če ima dohodni operater višjo prednost kot VRH sklada, potisnite dohodni operator v sklad.
- Če ima dohodni operater enako prednost kot NA VRHU sklada, potisnite dohodni operator v sklad.
- Če ima dohodni operater nižjo prednost kot VRH sklada, izpnite in natisnite vrh sklada. Znova preizkusite dohodni operator glede na vrh sklada in izločite operatorja iz sklada, dokler ne najde operatorja z nižjo ali enako prednostjo.
- Če ima vhodni operator enako prednost kot vrh sklada in je vhodni operator ^, potem dvignite vrh sklada, dokler pogoj ni resničen. Če pogoj ni resničen, pritisnite operator ^.
- Ko pridemo do konca izraza, odstranimo in natisnemo vse operatorje z vrha sklada.
- Če je operator ')', ga potisnite v sklad.
- Če je operator '(', potem izloči vse operatorje iz sklada, dokler ne najde ) odprtega oklepaja v skladu.
- Če je vrh sklada ')', potisnite operator na sklad.
- Na koncu obrnite izhod.
Psevdokoda pretvorbe infiksa v predpono
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))>