TechCodeview

Før vi forstår konverteringen fra infix til postfix-notasjon, bør vi vite om infix- og postfix-notasjonene separat.

En infix og postfix er uttrykkene. Et uttrykk består av konstanter, variabler og symboler. Symboler kan være operatorer eller parenteser. Alle disse komponentene må ordnes i henhold til et sett med regler slik at alle disse uttrykkene kan evalueres ved hjelp av regelsettet.

Eksempler på uttrykk er:

5 + 6

A - B

(P * 5)

Alle uttrykkene ovenfor har en felles struktur, det vil si at vi har en operator mellom de to operandene. En operand er et objekt eller en verdi som operasjonen skal utføres på. I uttrykkene ovenfor er 5, 6 operandene mens '+', '-' og '*' er operatorene.

Hva er infiksnotasjon?

Når operatoren er skrevet mellom operandene, er den kjent som infiksnotasjon . Operand trenger ikke alltid være en konstant eller variabel; det kan også være et uttrykk i seg selv.

For eksempel,

(p + q) * (r + s)

java streng til heltall konvertering

I uttrykket ovenfor er begge uttrykkene til multiplikasjonsoperatoren operandene, dvs. (p + q) , og (r + s) er operandene.

I uttrykket ovenfor er det tre operatorer. Operandene for den første plussoperatoren er p og q, operandene for den andre plussoperatoren er r og s. Mens du utfører operasjoner på uttrykket, må vi følge et sett med regler for å evaluere resultatet. I ovenfor uttrykk vil addisjonsoperasjonen bli utført på de to uttrykkene, dvs. p+q og r+s, og deretter vil multiplikasjonsoperasjonen bli utført.

Syntaks for infiksnotasjon er gitt nedenfor:

Hvis det bare er én operator i uttrykket, krever vi ikke bruk av noen regel. For eksempel, 5 + 2; i dette uttrykket kan addisjonsoperasjonen utføres mellom de to operandene (5 og 2), og resultatet av operasjonen vil være 7.

Hvis det er flere operatorer i uttrykket, må noen regel følges for å evaluere uttrykket.

Hvis uttrykket er:

mysql vis alle brukere

4+6*2

Hvis plussoperatoren evalueres først, vil uttrykket se slik ut:

10 * 2 = 20

Hvis multiplikasjonsoperatoren evalueres først, vil uttrykket se slik ut:

4 + 12 = 16

cm til fot og tommer

Problemet ovenfor kan løses ved å følge reglene for operatørprioritet. I det algebraiske uttrykket er rekkefølgen til operatørens prioritet gitt i tabellen nedenfor:

Den første preferansen er gitt til parentesen; deretter gis neste preferanse til eksponentene. I tilfellet med flere eksponentoperatorer, vil operasjonen bli brukt fra høyre mot venstre.

For eksempel:

2^2^3 = 2^8

= 256

Etter eksponent-, multiplikasjons- og divisjonsoperatorer evalueres. Hvis begge operatorene er til stede i uttrykket, vil operasjonen bli brukt fra venstre mot høyre.

Den neste preferansen gis til addisjon og subtraksjon. Hvis begge operatorene er tilgjengelige i uttrykket, går vi fra venstre til høyre.

Operatørene som har samme forrang kalt som operatørassosiativitet . Hvis vi går fra venstre til høyre, er det kjent som venstreassosiativt. Hvis vi går fra høyre til venstre, er det kjent som høyreassosiativt.

Problem med infiksnotasjon

For å evaluere infiksuttrykket, bør vi vite om operatørens forrang regler, og hvis operatørene har samme forrang, bør vi følge assosiativitet regler. Bruken av parentes er svært viktig i infiksnotasjon for å kontrollere rekkefølgen operasjonen skal utføres i. Parentes forbedrer lesbarheten til uttrykket. Et infiksuttrykk er den vanligste måten å skrive uttrykk på, men det er ikke lett å analysere og evaluere infiksuttrykket uten tvetydighet. Så matematikere og logikere studerte dette problemet og oppdaget to andre måter å skrive uttrykk på, som er prefiks og postfiks. Begge uttrykkene krever ingen parentes og kan analyseres uten tvetydighet. Det krever ikke operatørprioritet og assosiativitetsregler.

Postfix-uttrykk

Postfix-uttrykket er et uttrykk der operatoren er skrevet etter operandene. For eksempel kan postfix-uttrykket for infiksnotasjon ( 2+3) skrives som 23+.

Noen nøkkelpunkter angående postfix-uttrykket er:

• I postfix-uttrykk utføres operasjoner i den rekkefølgen de har skrevet fra venstre mot høyre.
• Det krever ingen parenteser.
• Vi trenger ikke å bruke regler for operatørprioritet og assosiativitetsregler.

Algoritme for å evaluere postfix-uttrykket

• Skann uttrykket fra venstre til høyre til vi møter en operatør.
• Utfør operasjonen
• Erstatt uttrykket med dets beregnede verdi.
• Gjenta trinnene fra 1 til 3 til det ikke finnes flere operatører.

La oss forstå algoritmen ovenfor gjennom et eksempel.

Infiksuttrykk: 2 + 3 * 4

Vi vil begynne å skanne det meste av uttrykket fra venstre. Multiplikasjonsoperatoren er en operator som vises først under skanning fra venstre til høyre. Nå vil uttrykket være:

hva er bikube

Uttrykk = 2 + 34*

= 2 + 12

Igjen vil vi skanne fra venstre til høyre, og uttrykket vil være:

Uttrykk = 2 12 +

= 14

Evaluering av postfix-uttrykk ved bruk av stack.

• Skann uttrykket fra venstre til høyre.
• Hvis vi møter noen operand i uttrykket, så skyver vi operanden i stabelen.
• Når vi støter på en operator i uttrykket, spretter vi de tilsvarende operandene fra stabelen.
• Når vi er ferdige med skanningen av uttrykket, forblir den endelige verdien i stabelen.

La oss forstå evalueringen av postfix-uttrykk ved å bruke stack.

Eksempel 1: Postfix-uttrykk: 2 3 4 * +

Resultatet av uttrykket ovenfor er 14.

Eksempel 2: Postfix-uttrykk: 3 4 * 2 5 * +

Resultatet av uttrykket ovenfor er 22.

json fra java-objekt

Algoritme for å evaluere postfix-uttrykk

1. Les en karakter
2. Hvis tegnet er et siffer, konverter tegnet til int og skyv heltallet inn i stabelen.
3. Hvis tegnet er en operatør,
   • Sprett elementene fra stabelen to ganger og oppnå to operander.
   • Utfør operasjonen
   • Skyv resultatet inn i stabelen.

Konvertering av infix til postfix

Her vil vi bruke stabeldatastrukturen for konvertering av infiksuttrykk til prefiksuttrykk. Hver gang en operatør støter på, skyver vi operatøren inn i stabelen. Hvis vi møter en operand, legger vi operanden til uttrykket.

Regler for konvertering fra infix- til postfix-uttrykk

1. Skriv ut operanden når de kommer.
2. Hvis stabelen er tom eller inneholder en venstre parentes på toppen, skyver du den innkommende operatøren over på stabelen.
3. Hvis det innkommende symbolet er '(', skyv det på stabelen.
4. Hvis det innkommende symbolet er ')', sprett stabelen og skriv ut operatorene til venstre parentes er funnet.
5. Hvis det innkommende symbolet har høyere prioritet enn toppen av stabelen, skyver du det på stabelen.
6. Hvis det innkommende symbolet har lavere prioritet enn toppen av stabelen, sprett og skriv ut toppen av stabelen. Test deretter den innkommende operatøren mot den nye toppen av stabelen.
7. Hvis den innkommende operatøren har samme prioritet med toppen av stabelen, bruk assosiativitetsreglene. Hvis assosiativiteten er fra venstre til høyre, trykk og skriv ut toppen av stabelen og skyv deretter den innkommende operatoren. Hvis assosiativiteten er fra høyre til venstre, trykk på den innkommende operatøren.
8. På slutten av uttrykket, pop og skriv ut alle operatorene til stabelen.

La oss forstå gjennom et eksempel.

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

Det endelige postfix-uttrykket for infiksuttrykk (K + L - M*N + (O^P) * W/U/V * T + Q) er KL+MN*-OP^W*U/V/T*+Q+ .