Prije razumijevanja pretvorbe iz infiksnog u postfiksni zapis, trebali bismo znati o infiksnom i postfiksnom zapisu zasebno.

Infiks i postfiks su izrazi. Izraz se sastoji od konstanti, varijabli i simbola. Simboli mogu biti operatori ili zagrade. Sve te komponente moraju biti raspoređene prema skupu pravila tako da se svi ovi izrazi mogu procijeniti pomoću skupa pravila.

Primjeri izraza su:

inorder traversal

5 + 6

A - B

(P * 5)

Svi gornji izrazi imaju zajedničku strukturu, tj. imamo operator između dva operanda. Operand je objekt ili vrijednost na kojoj se operacija treba izvesti. U gornjim izrazima, 5, 6 su operandi dok su '+', '-' i '*' operatori.

Što je infiksna notacija?

Kada je operator napisan između operanda, tada je poznat kao infiksni zapis . Operand ne mora uvijek biti konstanta ili varijabla; može biti i sam izraz.

Na primjer,

(p + q) * (r + s)

U gornjem izrazu, oba izraza operatora množenja su operandi, tj. (p + q) , i (r + s) su operandi.

U gornjem izrazu postoje tri operatora. Operandi za prvi plus operator su p i q, operandi za drugi plus operator su r i s. Tijekom izvođenja operacije na izrazu, moramo slijediti neki skup pravila za procjenu rezultata. u iznad izraza, operacija zbrajanja bi se izvršila na dva izraza, tj., p+q i r+s, a zatim bi se izvršila operacija množenja.

Sintaksa notacije infiksa data je u nastavku:

Ako postoji samo jedan operator u izrazu, ne zahtijevamo primjenu nikakvog pravila. Na primjer, 5 + 2; u ovom izrazu, operacija zbrajanja može se izvesti između dva operanda (5 i 2), a rezultat operacije bi bio 7.

Ako postoji više operatora u izrazu, potrebno je slijediti neko pravilo za procjenu izraza.

Ako je izraz:

4+6*2

Ako se prvo izračuna plus operator, onda bi izraz izgledao ovako:

10 * 2 = 20

Ako se prvo izračuna operator množenja, onda bi izraz izgledao ovako:

4 + 12 = 16

Gore navedeni problem može se riješiti slijedeći pravila prvenstva operatora. U algebarskom izrazu redoslijed prioriteta operatora dat je u donjoj tablici:

Prva se prednost daje zagradama; tada se sljedeća prednost daje eksponentima. U slučaju više eksponentnih operatora, operacija će se primijeniti s desna na lijevo.

Na primjer:

2^2^3 = 2^8

= 256

Nakon eksponenta, procjenjuju se operatori množenja i dijeljenja. Ako su oba operatora prisutna u izrazu, tada će se operacija primijeniti slijeva na desno.

Sljedeća prednost je dana zbrajanju i oduzimanju. Ako su oba operatora dostupna u izrazu, tada idemo slijeva nadesno.

Operatori koji imaju isti prioritet nazivaju se kao asocijativnost operatora . Ako idemo s lijeva na desno, onda je to poznato kao lijevo-asocijativno. Ako idemo s desna na lijevo, onda je to poznato kao desnoasocijativno.

Problem s zapisom infiksa

Da bismo ocijenili infiks izraz, trebali bismo znati o prednost operatora pravila, a ako operatori imaju isti prioritet, tada bismo trebali slijediti asocijativnost pravila. Korištenje zagrada vrlo je važno u zapisu infiksa za kontrolu redoslijeda kojim se operacija treba izvesti. Zagrade poboljšavaju čitljivost izraza. Infiks izraz je najčešći način pisanja izraza, ali nije lako raščlaniti i ocijeniti infiks izraz bez dvosmislenosti. Tako su matematičari i logičari proučavali ovaj problem i otkrili dva druga načina pisanja izraza, a to su prefiks i postfiks. Oba izraza ne zahtijevaju nikakve zagrade i mogu se raščlaniti bez dvosmislenosti. Ne zahtijeva prioritet operatora i pravila asocijativnosti.

kako pronaći blokirane brojeve na androidu

Postfiksni izraz

Postfiksni izraz je izraz u kojem se operator nalazi iza operanda. Na primjer, postfiksni izraz infiksnog zapisa (2+3) može se napisati kao 23+.

Neke ključne točke u vezi s postfiksnim izrazom su:

• U postfiksnom izrazu, operacije se izvode redoslijedom kojim su napisane s lijeva na desno.
• Ne zahtijeva nikakvu zagradu.
• Ne moramo primjenjivati ​​pravila prvenstva operatora i pravila asocijativnosti.

Algoritam za procjenu postfiksnog izraza

• Skenirajte izraz s lijeva na desno dok ne naiđemo na bilo koji operator.
• Izvedite operaciju
• Zamijenite izraz njegovom izračunatom vrijednošću.
• Ponavljajte korake od 1 do 3 dok više ne postoji nijedan operator.

Razmotrimo gornji algoritam kroz primjer.

Infiksni izraz: 2 + 3 * 4

Počet ćemo skenirati s lijeve strane većeg dijela izraza. Operator množenja je operator koji se prvi pojavljuje tijekom skeniranja slijeva nadesno. Sada bi izraz bio:

Izraz = 2 + 34*

= 2 + 12

Opet ćemo skenirati s lijeva na desno, a izraz bi bio:

Izraz = 2 12 +

= 14

Evaluacija postfiksnog izraza pomoću stoga.

• Skenirajte izraz s lijeva na desno.
• Ako naiđemo na bilo koji operand u izrazu, tada guramo operand u stog.
• Kada naiđemo na bilo koji operator u izrazu, tada izbacujemo odgovarajuće operande sa stoga.
• Kada završimo sa skeniranjem izraza, konačna vrijednost ostaje u stogu.

Razumimo procjenu postfiksnog izraza pomoću stoga.

Primjer 1: Postfiksni izraz: 2 3 4 * +

Rezultat gornjeg izraza je 14.

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

Rezultat gornjeg izraza je 22.

Algoritam za procjenu postfiksnog izraza

1. Pročitaj lik
2. Ako je znak znamenka, pretvorite znak u int i gurnite cijeli broj u stog.
3. Ako je znak operator,
   • Izbacite elemente iz snopa dva puta dobivajući dva operanda.
   • Izvedite operaciju
   • Gurnite rezultat u stog.

Pretvorba infiksa u postfiks

Ovdje ćemo koristiti strukturu podataka stog za konverziju infiksnog izraza u prefiksni izraz. Kad god naiđe operator, guramo ga u stog. Ako naiđemo na operand, tada operand dodajemo izrazu.

Pravila za pretvorbu iz infiksnog u postfiksni izraz

preimenuj u linux direktoriju

1. Ispišite operand kako stignu.
2. Ako je stog prazan ili sadrži lijevu zagradu na vrhu, gurnite dolazni operator na stog.
3. Ako je dolazni simbol '(', gurnite ga na hrpu.
4. Ako je dolazni simbol ')', iskočite snop i ispišite operatore dok se ne pronađe lijeva zagrada.
5. Ako dolazni simbol ima veću prednost od vrha snopa, gurnite ga na snop.
6. Ako dolazni simbol ima nižu prednost od vrha niza, iskočite i ispišite vrh niza. Zatim testirajte dolazni operator u odnosu na novi vrh stoga.
7. Ako dolazni operator ima isti prioritet kao i vrh stoga, upotrijebite pravila asocijativnosti. Ako je asocijativnost slijeva nadesno, iskočite i ispišite vrh hrpe, a zatim pritisnite dolazni operator. Ako je asocijativnost s desna na lijevo, pritisnite dolazni operator.
8. Na kraju izraza popnite i ispišite sve operatore snopa.

Shvatimo kroz primjer.

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

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