Prieš suprasdami konvertavimą iš infix į postfix žymėjimą, turėtume žinoti apie infix ir postfix žymes atskirai.

Infiksas ir postfiksas yra išraiškos. Išraiška susideda iš konstantų, kintamųjų ir simbolių. Simboliai gali būti operatoriai arba skliaustai. Visi šie komponentai turi būti išdėstyti pagal taisyklių rinkinį, kad visas šias išraiškas būtų galima įvertinti naudojant taisyklių rinkinį.

Išraiškų pavyzdžiai yra:

5 + 6

A-B

(P * 5)

Visos aukščiau pateiktos išraiškos turi bendrą struktūrą, ty turime operatorių tarp dviejų operandų. Operandas yra objektas arba reikšmė, su kuria turi būti atlikta operacija. Aukščiau pateiktose išraiškose 5, 6 yra operandai, o „+“, „-“ ir „*“ yra operatoriai.

Kas yra infikso žymėjimas?

Kai operatorius įrašomas tarp operandų, jis vadinamas infikso žymėjimas . Operandas nebūtinai visada turi būti konstanta arba kintamasis; tai gali būti ir pati išraiška.

Pavyzdžiui,

(p + q) * (r + s)

Aukščiau pateiktoje išraiškoje abi daugybos operatoriaus išraiškos yra operandai, t.y. (p + q) , ir (r + s) yra operandai.

Aukščiau pateiktoje išraiškoje yra trys operatoriai. Pirmojo pliuso operatoriaus operandai yra p ir q, antrojo pliuso operatoriai yra r ir s. Atliekant operacijų su išraiška, turime laikytis tam tikrų taisyklių rinkinio, kad įvertintume rezultatą. Viduje aukščiau esanti išraiška, sudėjimo operacija būtų atliekama su dviem išraiškomis, ty p+q ir r+s, o tada būtų atlikta daugybos operacija.

Infikso žymėjimo sintaksė pateikta žemiau:

Jei reiškinyje yra tik vienas operatorius, mes nereikalaujame taikyti jokios taisyklės. Pavyzdžiui, 5 + 2; šioje išraiškoje galima atlikti sudėjimo operaciją tarp dviejų operandų (5 ir 2), o operacijos rezultatas būtų 7.

Jei išraiškoje yra keli operatoriai, norint įvertinti išraišką reikia laikytis tam tikros taisyklės.

Jei išraiška yra:

4+6*2

Jei pirmiausia įvertinamas pliuso operatorius, išraiška atrodys taip:

10 * 2 = 20

Jei pirmiausia įvertinamas daugybos operatorius, tada išraiška atrodytų taip:

4 + 12 = 16

Aukščiau pateiktą problemą galima išspręsti laikantis operatoriaus pirmumo taisyklių. Algebrinėje išraiškoje operatorių pirmumo tvarka pateikta toliau esančioje lentelėje:

Pirmenybė teikiama skliausteliams; tada pirmenybė teikiama eksponentams. Kelių eksponentų operatorių atveju operacija bus taikoma iš dešinės į kairę.

Pavyzdžiui:

2^2^3 = 2^8

turi kitą java

= 256

Po eksponento įvertinami daugybos ir padalijimo operatoriai. Jei išraiškoje yra abu operatoriai, operacija bus taikoma iš kairės į dešinę.

Kita pirmenybė teikiama sudėjimui ir atėmimui. Jei išraiškoje yra abu operatoriai, tada einame iš kairės į dešinę.

Operatoriai, turintys tą pačią pirmenybę, vadinami kaip operatoriaus asociatyvumas . Jei einame iš kairės į dešinę, tai žinoma kaip kairioji asociatyvioji. Jei einame iš dešinės į kairę, tai žinoma kaip dešinė-asociatyvioji.

Problema su infix žymėjimu

Norėdami įvertinti infikso išraišką, turėtume žinoti apie operatoriaus pirmenybė taisyklės, o jei operatoriai turi tokią pačią pirmenybę, turėtume vadovautis asociatyvumas taisykles. Skliaustų naudojimas yra labai svarbus infikso žymėjime, siekiant kontroliuoti operacijos atlikimo tvarką. Skliaustai pagerina išraiškos skaitomumą. Infiksinė išraiška yra labiausiai paplitęs išraiškos rašymo būdas, tačiau nėra lengva išanalizuoti ir įvertinti infikso išraišką be dviprasmybių. Taigi, matematikai ir logikai ištyrė šią problemą ir atrado du kitus posakių rašymo būdus, kurie yra priešdėlis ir postfiksas. Abi išraiškos nereikalauja jokių skliaustų ir gali būti analizuojamos be dviprasmybių. Tam nereikia operatoriaus pirmumo ir asociatyvumo taisyklių.

Postfix išraiška

Postfix išraiška yra išraiška, kurioje operatorius rašomas po operandų. Pavyzdžiui, infikso žymėjimo postfikso išraiška ( 2+3) gali būti parašyta kaip 23+.

Kai kurie pagrindiniai punktai, susiję su postfix išraiška, yra šie:

• Postfix išraiškoje operacijos atliekamos tokia tvarka, kokia buvo parašytos iš kairės į dešinę.
• Tam nereikia jokių skliaustų.
• Mums nereikia taikyti operatorių pirmumo taisyklių ir asociatyvumo taisyklių.

Algoritmas, skirtas įvertinti postfix išraišką

• Nuskaitykite išraišką iš kairės į dešinę, kol susidursime su bet kuriuo operatoriumi.
• Atlikite operaciją
• Pakeiskite išraišką jos apskaičiuota verte.
• Kartokite veiksmus nuo 1 iki 3, kol nebeliks operatorių.

Supraskime aukščiau pateiktą algoritmą per pavyzdį.

Infikso išraiška: 2 + 3 * 4

Pradėsime nuskaityti iš kairės didžiąją išraiškos dalį. Daugybos operatorius yra operatorius, kuris pasirodo pirmasis nuskaitant iš kairės į dešinę. Dabar išraiška būtų tokia:

string.valueof

Išraiška = 2 + 34*

= 2 + 12

Vėlgi, mes nuskaitysime iš kairės į dešinę, o išraiška būtų tokia:

Išraiška = 2 12 +

= 14

Postfix išraiškos įvertinimas naudojant steką.

• Nuskaitykite išraišką iš kairės į dešinę.
• Jei išraiškoje susiduriame su kokiu nors operandu, operandą įstumiame į krūvą.
• Kai išraiškoje susiduriame su bet kuriuo operatoriumi, atitinkamus operandus iškeliame iš krūvos.
• Kai baigiame nuskaityti išraišką, galutinė reikšmė lieka krūvoje.

Supraskime postfix išraiškos įvertinimą naudojant krūvą.

1 pavyzdys: Postfix išraiška: 2 3 4 * +

Aukščiau pateiktos išraiškos rezultatas yra 14.

2 pavyzdys: Postfix išraiška: 3 4 * 2 5 * +

Aukščiau pateiktos išraiškos rezultatas yra 22.

Algoritmas įvertinti postfix išraišką

1. Skaityti personažą
2. Jei simbolis yra skaitmuo, paverskite simbolį į int ir įstumkite sveikąjį skaičių į krūvą.
3. Jei simbolis yra operatorius,
   • Du kartus iškelkite elementus iš krūvos ir gaukite du operandus.
   • Atlikite operaciją
   • Stumkite rezultatą į krūvą.

Infix konvertavimas į postfix

Čia mes naudosime kamino duomenų struktūrą, norėdami konvertuoti infikso išraišką į priešdėlio išraišką. Kai tik operatorius susiduria, mes įstumiame operatorių į krūvą. Jei susiduriame su operandu, operandą pridedame prie išraiškos.

Konvertavimo iš infix į postfix išraiškos taisyklės

1. Atspausdinkite operandą, kai jie atvyks.
2. Jei krūva tuščia arba viršuje yra kairysis skliaustas, stumkite gaunamą operatorių ant krūvos.
3. Jei gaunamas simbolis yra „(“, stumkite jį į krūvą.
4. Jei gaunamas simbolis yra „)“, išmeskite krūvą ir spausdinkite operatorius, kol rasite kairįjį skliaustelį.
5. Jei gaunamas simbolis turi didesnį pirmumą nei krūvos viršus, stumkite jį ant krūvos.
6. Jei gaunamas simbolis turi mažesnę pirmenybę nei krūvos viršus, ištraukite ir atspausdinkite krūvos viršų. Tada patikrinkite gaunamą operatorių, lyginant su nauju krūvos viršumi.
7. Jei gaunamas operatorius turi tokią pat pirmenybę kaip kamino viršus, naudokite asociatyvumo taisykles. Jei asociatyvumas yra iš kairės į dešinę, tada atidarykite ir atspausdinkite krūvos viršų, tada paspauskite gaunamą operatorių. Jei asociatyvumas yra iš dešinės į kairę, paspauskite įeinantį operatorių.
8. Pasibaigus išraiškai, atspausdinkite ir atspausdinkite visus krūvos operatorius.

Supraskime per pavyzdį.

Infikso išraiška: K + L - M*N + (O^P) * W/U/V * T + Q

Galutinė infikso išraiškos postfikso išraiška (K + L - M*N + (O^P) * W/U/V * T + Q) yra KL+MN*-OP^W*U/V/T*+Q+ .