Pirms izprast pārveidošanu no infiksa uz postfix apzīmējumu, mums atsevišķi jāzina par infiksa un postfiksa apzīmējumiem.

Infikss un postfikss ir izteicieni. Izteiksme sastāv no konstantēm, mainīgajiem un simboliem. Simboli var būt operatori vai iekavas. Visas šīs sastāvdaļas ir jāsakārto saskaņā ar noteikumu kopumu, lai visas šīs izteiksmes varētu novērtēt, izmantojot noteikumu kopu.

Izteicienu piemēri ir:

5+6

A–B

(P * 5)

Visām iepriekšminētajām izteiksmēm ir kopīga struktūra, t.i., starp abiem operandiem ir operators. Operands ir objekts vai vērtība, ar kuru jāveic darbība. Iepriekš minētajās izteiksmēs 5, 6 ir operandi, savukārt '+', '-' un '*' ir operatori.

Kas ir infiksa apzīmējums?

Ja operators ir ierakstīts starp operandiem, tas ir pazīstams kā infiksa apzīmējums . Operandam nav vienmēr jābūt konstantei vai mainīgajam; tā var būt arī pati izteiksme.

Piemēram,

(p + q) * (r + s)

Iepriekš minētajā izteiksmē abas reizināšanas operatora izteiksmes ir operandi, t.i., (p+q) , un (r + s) ir operandi.

Iepriekš minētajā izteiksmē ir trīs operatori. Operandi pirmajam plus operatoram ir p un q, operandi otrajam plus operatoram ir r un s. Veicot operācijas ar izteiksmi, mums ir jāievēro daži noteikumu kopumi, lai novērtētu rezultātu. Iekš virs izteiksmes, saskaitīšanas darbība tiktu veikta abām izteiksmēm, t.i., p+q un r+s, un pēc tam tiktu veikta reizināšanas darbība.

Infiksa apzīmējuma sintakse ir norādīta zemāk:

Ja izteiksmē ir tikai viens operators, mums nav jāpiemēro neviens noteikums. Piemēram, 5 + 2; šajā izteiksmē var veikt saskaitīšanas darbību starp diviem operandiem (5 un 2), un darbības rezultāts būtu 7.

Ja izteiksmē ir vairāki operatori, tad, lai novērtētu izteiksmi, ir jāievēro daži noteikumi.

sapludināt kārtot java

Ja izteiksme ir:

4+6*2

Ja vispirms tiek novērtēts plus operators, tad izteiksme izskatītos šādi:

10 * 2 = 20

Ja vispirms tiek novērtēts reizināšanas operators, tad izteiksme izskatītos šādi:

4 + 12 = 16

Iepriekš minēto problēmu var atrisināt, ievērojot operatora prioritātes noteikumus. Algebriskajā izteiksmē operatora prioritātes secība ir norādīta zemāk esošajā tabulā:

Pirmā priekšroka tiek dota iekavām; tad nākamā priekšroka tiek dota eksponentiem. Vairāku eksponentu operatoru gadījumā darbība tiks piemērota no labās uz kreiso pusi.

Piemēram:

2^2^3 = 2^8

= 256

Pēc eksponenta tiek novērtēti reizināšanas un dalīšanas operatori. Ja izteiksmē ir abi operatori, darbība tiks piemērota no kreisās puses uz labo.

Nākamā priekšroka tiek dota saskaitīšanai un atņemšanai. Ja izteiksmē ir pieejami abi operatori, mēs ejam no kreisās puses uz labo.

Operatori, kuriem ir tāda pati prioritāte, tiek apzīmēti kā operatora asociativitāte . Ja mēs ejam no kreisās puses uz labo, tad to sauc par kreiso asociatīvo. Ja mēs ejam no labās puses uz kreiso, tad to sauc par labo-asociatīvo.

Problēma ar infix apzīmējumu

Lai novērtētu infiksa izteiksmi, mums jāzina par operatora prioritāte noteikumiem, un, ja operatoriem ir tāda pati prioritāte, mums ir jāievēro asociativitāte noteikumiem. Iekavu izmantošana ir ļoti svarīga infiksa apzīmējumā, lai kontrolētu operācijas izpildes secību. Iekavas uzlabo izteiksmes lasāmību. Infiksa izteiksme ir visizplatītākais izteiksmes rakstīšanas veids, taču nav viegli parsēt un novērtēt infiksa izteiksmi bez neskaidrības. Tātad matemātiķi un loģiķi pētīja šo problēmu un atklāja divus citus izteiksmju rakstīšanas veidus, kas ir prefikss un postfikss. Abām izteiksmēm nav vajadzīgas iekavas, un tās var parsēt bez neskaidrībām. Tam nav nepieciešami operatora prioritātes un asociācijas noteikumi.

masīvs pret masīvu sarakstu

Postfix izteiksme

Postfix izteiksme ir izteiksme, kurā operators ir rakstīts aiz operandiem. Piemēram, infiksa apzīmējuma postfiksa izteiksmi ( 2+3) var rakstīt kā 23+.

Daži galvenie punkti attiecībā uz postfix izteiksmi ir šādi:

• Postfix izteiksmē darbības tiek veiktas tādā secībā, kādā tās ir rakstītas no kreisās puses uz labo.
• Tam nav vajadzīgas nekādas iekavas.
• Mums nav jāpiemēro operatoru prioritātes noteikumi un asociācijas kārtulas.

Algoritms postfix izteiksmes novērtēšanai

• Skenējiet izteiksmi no kreisās puses uz labo, līdz mēs saskaramies ar jebkuru operatoru.
• Veikt operāciju
• Aizstāt izteiksmi ar tās aprēķināto vērtību.
• Atkārtojiet darbības no 1 līdz 3, līdz vairs nav operatoru.

Izpratīsim iepriekš minēto algoritmu, izmantojot piemēru.

alfabēta numurēšana

Infiksa izteiksme: 2 + 3 * 4

Mēs sāksim skenēt lielāko daļu izteiksmes no kreisās puses. Reizināšanas operators ir operators, kas parādās pirmais, skenējot no kreisās puses uz labo. Tagad izteiciens būtu šāds:

Izteiksme = 2 + 34*

= 2 + 12

Atkal mēs skenēsim no kreisās puses uz labo, un izteiksme būtu šāda:

Izteiksme = 2 12 +

= 14

Postfix izteiksmes novērtēšana, izmantojot steku.

• Skenējiet izteiksmi no kreisās uz labo pusi.
• Ja izteiksmē sastopam kādu operandu, tad operandu ievietojam kaudzē.
• Kad izteiksmē sastopamies ar jebkuru operatoru, mēs izņemam atbilstošos operandus no steka.
• Kad mēs pabeidzam izteiksmes skenēšanu, galīgā vērtība paliek kaudzē.

Sapratīsim postfix izteiksmes novērtēšanu, izmantojot steku.

1. piemērs: Postfix izteiksme: 2 3 4 * +

Iepriekš minētās izteiksmes rezultāts ir 14.

2. piemērs: Postfix izteiksme: 3 4 * 2 5 * +

Iepriekš minētās izteiksmes rezultāts ir 22.

Algoritms postfix izteiksmes novērtēšanai

1. Lasīt varoni
2. Ja rakstzīme ir cipars, pārveidojiet rakstzīmi par int un ievietojiet veselu skaitli kaudzē.
3. Ja rakstzīme ir operators,
   • Divreiz izspiediet elementus no kaudzes, iegūstot divus operandus.
   • Veikt operāciju
   • Ievietojiet rezultātu kaudzē.

Infix konvertēšana uz postfix

Šeit mēs izmantosim steku datu struktūru, lai pārveidotu infiksa izteiksmi par prefiksa izteiksmi. Ikreiz, kad operators saskaras, mēs iespiežam operatoru kaudzē. Ja mēs sastopam operandu, mēs pievienojam operandu izteiksmei.

Noteikumi konvertēšanai no infix izteiksmes uz postfix izteiksmi

1. Izdrukājiet operandu, tiklīdz tie nonāk.
2. Ja steks ir tukšs vai augšpusē ir kreisās iekavas, uzspiediet ienākošo operatoru uz kaudzītes.
3. Ja ienākošais simbols ir '(', piespiediet to uz kaudzītes.
4. Ja ienākošais simbols ir ')', izspiediet kaudzi un drukājiet operatorus, līdz tiek atrasta kreisā iekava.
5. Ja ienākošajam simbolam ir augstāka prioritāte nekā kaudzes augšdaļai, uzspiediet to uz kaudzes.
6. Ja ienākošajam simbolam ir zemāka prioritāte nekā kaudzes augšdaļai, izspiediet un izdrukājiet kaudzes augšdaļu. Pēc tam pārbaudiet ienākošo operatoru pret jauno kaudzes augšdaļu.
7. Ja ienākošajam operatoram ir tāda pati prioritāte kā steka augšpusē, izmantojiet asociativitātes noteikumus. Ja asociativitāte ir no kreisās puses uz labo, tad izspiediet un izdrukājiet kaudzes augšdaļu, pēc tam nospiediet ienākošo operatoru. Ja asociativitāte ir no labās puses uz kreiso, nospiediet ienākošo operatoru.
8. Izteiksmes beigās izspiediet un izdrukājiet visus kaudzes operatorus.

Sapratīsim, izmantojot piemēru.

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

Infiksa izteiksmes galīgā pēcfiksācijas izteiksme (K + L - M*N + (O^P) * W/U/V * T + Q) ir KL+MN*-OP^W*U/V/T*+Q+ .