Før vi forstår konverteringen fra infix til postfix-notation, bør vi kende til infix- og postfix-notationerne separat.

Et infix og postfix er udtrykkene. Et udtryk består af konstanter, variabler og symboler. Symboler kan være operatorer eller parenteser. Alle disse komponenter skal arrangeres efter et sæt regler, så alle disse udtryk kan evalueres ved hjælp af regelsættet.

Eksempler på udtryk er:

5 + 6

A - B

(P * 5)

Alle ovenstående udtryk har en fælles struktur, dvs. vi har en operator mellem de to operander. En operand er et objekt eller en værdi, som operationen skal udføres på. I ovenstående udtryk er 5, 6 operanderne, mens '+', '-' og '*' er operatorerne.

Hvad er infix-notation?

Når operatoren er skrevet mellem operanderne, er den kendt som infix notation . Operand behøver ikke altid at være en konstant eller en variabel; det kan også være et udtryk i sig selv.

For eksempel,

(p + q) * (r + s)

konvertere en dato til en streng

I ovenstående udtryk er begge udtryk for multiplikationsoperatoren operanderne, dvs. (p + q) , og (r + s) er operanderne.

I ovenstående udtryk er der tre operatorer. Operanderne for den første plusoperator er p og q, operanderne for den anden plusoperator er r og s. Mens du udfører operationer på udtrykket, er vi nødt til at følge nogle sæt regler for at evaluere resultatet. I den ovenstående udtryk ville additionsoperationen blive udført på de to udtryk, dvs. p+q og r+s, og derefter ville multiplikationsoperationen blive udført.

Syntaks for infix-notation er angivet nedenfor:

Hvis der kun er én operator i udtrykket, kræver vi ikke anvendelse af nogen regel. For eksempel, 5 + 2; i dette udtryk kan additionsoperationen udføres mellem de to operander (5 og 2), og resultatet af operationen ville være 7.

Hvis der er flere operatorer i udtrykket, skal en eller anden regel følges for at evaluere udtrykket.

Hvis udtrykket er:

array vs arraylist

4+6*2

Hvis plusoperatoren evalueres først, vil udtrykket se sådan ud:

10 * 2 = 20

Hvis multiplikationsoperatoren evalueres først, vil udtrykket se sådan ud:

4 + 12 = 16

hvor mange 0 i en milliard

Ovenstående problem kan løses ved at følge operatørens forrangsregler. I det algebraiske udtryk er rækkefølgen af ​​operatorens forrang givet i nedenstående tabel:

Den første præference gives til parentesen; derefter gives næste præference til eksponenterne. I tilfælde af flere eksponentoperatorer, så vil operationen blive anvendt fra højre mod venstre.

For eksempel:

2^2^3 = 2^8

= 256

Efter eksponent-, multiplikations- og divisionsoperatorer evalueres. Hvis begge operatorer er til stede i udtrykket, vil operationen blive anvendt fra venstre mod højre.

Den næste præference gives til addition og subtraktion. Hvis begge operatorer er tilgængelige i udtrykket, så går vi fra venstre mod højre.

De operatører, der har samme forrang betegnes som operatørassociativitet . Hvis vi går fra venstre mod højre, er det kendt som venstreassociativt. Hvis vi går fra højre til venstre, er det kendt som højreassociativt.

Problem med infix-notation

For at evaluere infix-udtrykket bør vi kende til operatørens forrang regler, og hvis operatørerne har samme forrang, så bør vi følge associativitet regler. Brugen af ​​parentes er meget vigtig i infiksnotation for at kontrollere den rækkefølge, hvori operationen skal udføres. Parentes forbedrer udtrykkets læsbarhed. Et infix-udtryk er den mest almindelige måde at skrive udtryk på, men det er ikke let at parse og evaluere infix-udtrykket uden tvetydighed. Så matematikere og logikere studerede dette problem og opdagede to andre måder at skrive udtryk på, som er præfiks og postfiks. Begge udtryk kræver ingen parentes og kan parses uden tvetydighed. Det kræver ikke operatørforrang og associativitetsregler.

Postfix udtryk

Postfix-udtrykket er et udtryk, hvor operatoren er skrevet efter operanderne. For eksempel kan postfix-udtrykket for infix-notation ( 2+3) skrives som 23+.

Nogle nøglepunkter vedrørende postfix-udtrykket er:

• I postfix-udtryk udføres operationer i den rækkefølge, de har skrevet fra venstre mod højre.
• Det kræver ikke nogen parentes.
• Vi behøver ikke at anvende operatørpræferenceregler og associativitetsregler.

Algoritme til at evaluere postfix-udtrykket

• Scan udtrykket fra venstre mod højre, indtil vi støder på en operator.
• Udfør operationen
• Erstat udtrykket med dets beregnede værdi.
• Gentag trinene fra 1 til 3, indtil der ikke findes flere operatører.

Lad os forstå ovenstående algoritme gennem et eksempel.

Infix-udtryk: 2 + 3 * 4

Vi begynder at scanne det meste af udtrykket fra venstre. Multiplikationsoperatoren er en operator, der vises først under scanning fra venstre mod højre. Nu ville udtrykket være:

bash andet hvis

Udtryk = 2 + 34*

= 2 + 12

Igen vil vi scanne fra venstre mod højre, og udtrykket ville være:

Udtryk = 2 12 +

= 14

Evaluering af postfix-udtryk ved hjælp af stak.

• Scan udtrykket fra venstre mod højre.
• Hvis vi støder på en operand i udtrykket, så skubber vi operanden i stakken.
• Når vi støder på en operator i udtrykket, springer vi de tilsvarende operander fra stakken.
• Når vi er færdige med scanningen af ​​udtrykket, forbliver den endelige værdi i stakken.

Lad os forstå evalueringen af ​​postfix-udtryk ved hjælp af stack.

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

Resultatet af ovenstående udtryk er 14.

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

Resultatet af ovenstående udtryk er 22.

substring metode java

Algoritme til at evaluere postfix-udtryk

1. Læs en karakter
2. Hvis tegnet er et ciffer, skal du konvertere tegnet til int og skubbe hele tallet ind i stakken.
3. Hvis karakteren er en operator,
   • Pop elementerne fra stakken to gange og få to operander.
   • Udfør operationen
   • Skub resultatet ind i stakken.

Konvertering af infix til postfix

Her vil vi bruge stakdatastrukturen til konvertering af infix-udtryk til præfiksudtryk. Når en operatør støder på, skubber vi operatøren ind i stakken. Hvis vi støder på en operand, så føjer vi operanden til udtrykket.

Regler for konvertering fra infix- til postfix-udtryk

1. Udskriv operanden, når de ankommer.
2. Hvis stakken er tom eller indeholder en venstre parentes øverst, skal du skubbe den indgående operatør på stakken.
3. Hvis det indkommende symbol er '(', skub det på stakken.
4. Hvis det indkommende symbol er ')', pop stakken og udskriv operatorerne, indtil den venstre parentes er fundet.
5. Hvis det indkommende symbol har højere forrang end toppen af ​​stakken, skal du skubbe det på stakken.
6. Hvis det indkommende symbol har lavere forrang end toppen af ​​stakken, skal du pop og udskrive toppen af ​​stakken. Test derefter den indkommende operatør mod den nye top af stakken.
7. Hvis den indgående operatør har samme forrang med toppen af ​​stakken, så brug associativitetsreglerne. Hvis associativiteten er fra venstre mod højre, så pop og udskriv toppen af ​​stakken, og tryk derefter på den indkommende operator. Hvis associativiteten er fra højre mod venstre, skal du trykke på den indkommende operator.
8. I slutningen af ​​udtrykket skal du pop og udskrive alle operatorerne i stakken.

Lad os forstå gennem et eksempel.

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

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