Preden razumemo pretvorbo iz infiksnega v postfiksni zapis, bi morali vedeti o infiksnem in postfiksnem zapisu ločeno.

Infiks in postfiks sta izraza. Izraz je sestavljen iz konstant, spremenljivk in simbolov. Simboli so lahko operatorji ali oklepaji. Vse te komponente morajo biti urejene v skladu z nizom pravil, tako da je mogoče vse te izraze ovrednotiti z uporabo niza pravil.

Primeri izrazov so:

5 + 6

A - B

(P * 5)

Vsi zgornji izrazi imajo skupno strukturo, tj. med obema operandoma imamo operator. Operand je objekt ali vrednost, na kateri je treba izvesti operacijo. V zgornjih izrazih sta 5, 6 operanda, medtem ko so '+', '-' in '*' operatorji.

Kaj je infiksni zapis?

Ko je operator zapisan med operandi, je znan kot infiksni zapis . Ni nujno, da je operand vedno konstanta ali spremenljivka; lahko je tudi sam izraz.

na primer

(p + q) * (r + s)

V zgornjem izrazu sta oba izraza operatorja množenja operanda, tj. (p + q) , in (r + s) so operandi.

algoritem razvrščanja z združevanjem

V zgornjem izrazu so trije operatorji. Operanda za prvi operator plus sta p in q, operanda za drugi operator plus sta r in s. Med izvajanjem operacije na izrazu, moramo za ovrednotenje rezultata upoštevati določen niz pravil. V zgornjem izrazu bi bila operacija seštevanja izvedena na dveh izrazih, tj. p+q in r+s, nato pa bi bila izvedena operacija množenja.

Sintaksa zapisa infiksa je podana spodaj:

Če je v izrazu samo en operator, ne zahtevamo uporabe nobenega pravila. Na primer, 5 + 2; v tem izrazu se lahko izvede operacija seštevanja med obema operandoma (5 in 2), rezultat operacije pa bi bil 7.

Če je v izrazu več operatorjev, je treba za ovrednotenje izraza upoštevati neko pravilo.

Če je izraz:

4+6*2

Če se najprej ovrednoti operator plus, bi bil izraz videti tako:

10 * 2 = 20

Če se najprej ovrednoti operator množenja, bi bil izraz videti takole:

4 + 12 = 16

Zgornjo težavo je mogoče rešiti z upoštevanjem pravil o prednosti operaterjev. V algebraičnem izrazu je prednostni vrstni red operatorjev podan v spodnji tabeli:

Prva prednost je dana oklepaju; potem je naslednja prednost dana eksponentom. V primeru več eksponentnih operatorjev bo operacija uporabljena od desne proti levi.

Na primer:

2^2^3 = 2^8

= 256

Po eksponentu se ovrednotijo ​​operatorji množenja in deljenja. Če sta v izrazu prisotna oba operatorja, bo operacija uporabljena od leve proti desni.

Naslednja prednost je dana seštevanju in odštevanju. Če sta v izrazu na voljo oba operatorja, gremo od leve proti desni.

Operatorji, ki imajo enako prednost, imenovani kot operatorska asociativnost . Če gremo od leve proti desni, je to znano kot levo-asociativno. Če gremo od desne proti levi, je to znano kot desno asociativno.

Težava z infiksnim zapisom

Za ovrednotenje infiksnega izraza bi morali vedeti o prednost operaterja in če imajo operaterji enako prednost, potem moramo upoštevati asociativnost pravila. Uporaba oklepaja je zelo pomembna v zapisu infiksa za nadzor vrstnega reda, v katerem je treba izvesti operacijo. Oklepaj izboljša berljivost izraza. Infiksni izraz je najpogostejši način pisanja izraza, vendar ni enostavno razčleniti in ovrednotiti infiksnega izraza brez dvoumnosti. Tako so matematiki in logiki preučevali ta problem in odkrili dva druga načina pisanja izrazov, ki sta predpona in postfiksa. Oba izraza ne zahtevata nobenih oklepajev in ju je mogoče razčleniti brez dvoumnosti. Ne zahteva prednosti operaterjev in pravil asociativnosti.

replaceall v nizu java

Postfiksni izraz

Postfiksni izraz je izraz, v katerem je operator zapisan za operandi. Na primer, postfiksni izraz infiksnega zapisa ( 2+3) lahko zapišemo kot 23+.

Nekatere ključne točke v zvezi s postfiksnim izrazom so:

• V postfiksnem izrazu se operacije izvajajo v vrstnem redu, v katerem so zapisane od leve proti desni.
• Ne potrebuje nobenega oklepaja.
• Ni nam treba uporabiti pravil prednosti operatorjev in pravil asociativnosti.

Algoritem za vrednotenje postfiksnega izraza

• Skenirajte izraz od leve proti desni, dokler ne naletimo na kateri koli operator.
• Izvedite operacijo
• Zamenjajte izraz z njegovo izračunano vrednostjo.
• Ponavljajte korake od 1 do 3, dokler ne obstaja več noben operater.

Razumejmo zgornji algoritem na primeru.

Infiksni izraz: 2 + 3 * 4

Večji del izraza bomo začeli skenirati z leve strani. Operator množenja je operator, ki se pojavi prvi med skeniranjem od leve proti desni. Zdaj bi bil izraz:

java pretvori niz v int

Izraz = 2 + 34*

= 2 + 12

Spet bomo skenirali od leve proti desni in izraz bi bil:

Izraz = 2 12 +

= 14

Vrednotenje postfiksnega izraza z uporabo sklada.

• Preglejte izraz od leve proti desni.
• Če v izrazu naletimo na kateri koli operand, ga potisnemo v sklad.
• Ko v izrazu naletimo na kateri koli operator, iz sklada odstranimo ustrezne operande.
• Ko končamo s skeniranjem izraza, končna vrednost ostane v skladu.

Razumejmo vrednotenje postfiksnega izraza z uporabo sklada.

Primer 1: Postfiksni izraz: 2 3 4 * +

Rezultat zgornjega izraza je 14.

Primer 2: Postfiksni izraz: 3 4 * 2 5 * +

Rezultat zgornjega izraza je 22.

Algoritem za vrednotenje postfiksnega izraza

1. Preberi znak
2. Če je znak cifra, pretvorite znak v int in potisnite celo število v sklad.
3. Če je znak operator,
   • Dvakrat izločite elemente iz sklada in dobite dva operanda.
   • Izvedite operacijo
   • Rezultat potisnite v sklad.

Pretvorba infiksa v postfiks

Tukaj bomo uporabili podatkovno strukturo sklada za pretvorbo infiksnega izraza v predponski izraz. Kadarkoli naleti operater, ga potisnemo v sklad. Če naletimo na operand, ga dodamo izrazu.

Pravila za pretvorbo iz infiksnega v postfiksni izraz

1. Natisnite operand, ko prispejo.
2. Če je sklad prazen ali vsebuje levi oklepaj na vrhu, potisnite dohodni operator na sklad.
3. Če je dohodni simbol '(', ga potisnite na sklad.
4. Če je dohodni simbol ')', odstranite sklad in natisnite operatorje, dokler ne najdete levega oklepaja.
5. Če ima dohodni simbol višjo prednost kot vrh sklada, ga potisnite na sklad.
6. Če ima dohodni simbol nižjo prednost kot vrh sklada, izpnite in natisnite vrh sklada. Nato preizkusite dohodni operater na novem vrhu sklada.
7. Če ima dohodni operator enako prednost kot vrh sklada, uporabite pravila asociativnosti. Če je asociativnost od leve proti desni, potem izpnite in natisnite vrh sklada, nato pritisnite dohodni operator. Če je asociativnost od desne proti levi, pritisnite dohodni operater.
8. Na koncu izraza izpnite in natisnite vse operatorje sklada.

Razumejmo skozi primer.

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

Končni postfiksni izraz infiksnega izraza (K + L - M*N + (O^P) * W/U/V * T + Q) je KL+MN*-OP^W*U/V/T*+Q+ .