TechCodeview

Innan vi förstår konverteringen från infix till postfix-notation bör vi känna till infix- och postfix-notationerna separat.

En infix och postfix är uttrycken. Ett uttryck består av konstanter, variabler och symboler. Symboler kan vara operatorer eller parenteser. Alla dessa komponenter måste ordnas enligt en uppsättning regler så att alla dessa uttryck kan utvärderas med hjälp av regeluppsättningen.

Exempel på uttryck är:

5 + 6

A - B

(P * 5)

Alla ovanstående uttryck har en gemensam struktur, det vill säga vi har en operator mellan de två operanderna. En operand är ett objekt eller ett värde som operationen ska utföras på. I uttrycken ovan är 5, 6 operanderna medan '+', '-' och '*' är operatorerna.

Vad är infix notation?

När operatorn skrivs mellan operanderna kallas den infix notation . Operand behöver inte alltid vara en konstant eller variabel; det kan också vara ett uttryck i sig.

Till exempel,

(p + q) * (r + s)

I uttrycket ovan är båda uttrycken för multiplikationsoperatorn operanderna, dvs. (p + q) , och (r + s) är operanderna.

I uttrycket ovan finns det tre operatorer. Operanderna för den första plusoperatorn är p och q, operanderna för den andra plusoperatorn är r och s. När du utför operationer på uttrycket måste vi följa några regler för att utvärdera resultatet. I den ovanstående uttryck skulle additionsoperationen utföras på de två uttrycken, dvs p+q och r+s, och sedan skulle multiplikationsoperationen utföras.

Syntax för infixnotation ges nedan:

vad är linux-filsystemet

Om det bara finns en operator i uttrycket behöver vi inte tillämpa någon regel. Till exempel, 5 + 2; i detta uttryck kan additionsoperationen utföras mellan de två operanderna (5 och 2), och resultatet av operationen skulle bli 7.

Om det finns flera operatorer i uttrycket måste någon regel följas för att utvärdera uttrycket.

Om uttrycket är:

4+6*2

Om plusoperatorn utvärderas först, skulle uttrycket se ut så här:

10 * 2 = 20

Om multiplikationsoperatorn utvärderas först, skulle uttrycket se ut så här:

4 + 12 = 16

Ovanstående problem kan lösas genom att följa reglerna för operatörsföreträde. I det algebraiska uttrycket ges ordningen för operatorns prioritet i tabellen nedan:

Den första preferensen ges till parentesen; därefter ges exponenterna nästa preferens. I fallet med flera exponentoperatorer kommer operationen att tillämpas från höger till vänster.

Till exempel:

2^2^3 = 2^8

= 256

Efter exponent-, multiplikations- och divisionsoperatorer utvärderas. Om båda operatorerna finns i uttrycket kommer operationen att tillämpas från vänster till höger.

Nästa preferens ges till addition och subtraktion. Om båda operatorerna är tillgängliga i uttrycket går vi från vänster till höger.

Operatörerna som har samma företräde kallas som operatörsassociativitet . Om vi ​​går från vänster till höger, är det känt som vänsterassociativt. Om vi ​​går från höger till vänster är det känt som högerassociativt.

Problem med infix notation

För att utvärdera infix-uttrycket bör vi känna till operatörsföreträde regler, och om operatörerna har samma företräde, bör vi följa associativitet regler. Användningen av parentes är mycket viktig i infix notation för att styra i vilken ordning operationen ska utföras. Parentes förbättrar uttryckets läsbarhet. Ett infixuttryck är det vanligaste sättet att skriva uttryck, men det är inte lätt att analysera och utvärdera infixuttrycket utan tvetydighet. Så, matematiker och logiker studerade detta problem och upptäckte två andra sätt att skriva uttryck som är prefix och postfix. Båda uttrycken kräver ingen parentes och kan tolkas utan tvetydighet. Det kräver inte operatörsföreträde och associativitetsregler.

Postfix uttryck

Postfix-uttrycket är ett uttryck där operatorn skrivs efter operanderna. Till exempel kan postfix-uttrycket för infixnotation ( 2+3) skrivas som 23+.

Några nyckelpunkter angående postfix-uttrycket är:

• I postfix-uttryck utförs operationer i den ordning som de har skrivits från vänster till höger.
• Det kräver ingen parentes.
• Vi behöver inte tillämpa operatörsföreträdesregler och associativitetsregler.

Algoritm för att utvärdera postfix-uttrycket

• Skanna uttrycket från vänster till höger tills vi stöter på någon operator.
• Utför operationen
• Ersätt uttrycket med dess beräknade värde.
• Upprepa stegen från 1 till 3 tills inga fler operatörer finns.

Låt oss förstå ovanstående algoritm genom ett exempel.

Infixuttryck: 2 + 3 * 4

Vi kommer att börja skanna från vänster större delen av uttrycket. Multiplikationsoperatorn är en operator som visas först när du skannar från vänster till höger. Nu skulle uttrycket vara:

replaceall i string java

Uttryck = 2 + 34*

= 2 + 12

Återigen kommer vi att skanna från vänster till höger, och uttrycket skulle vara:

Uttryck = 2 12 +

= 14

Utvärdering av postfix-uttryck med stack.

• Skanna uttrycket från vänster till höger.
• Om vi ​​stöter på någon operand i uttrycket, så trycker vi in ​​operanden i stacken.
• När vi stöter på någon operator i uttrycket poppar vi motsvarande operander från stacken.
• När vi är klara med skanningen av uttrycket finns det slutliga värdet kvar i stacken.

Låt oss förstå utvärderingen av postfix-uttryck med stack.

Exempel 1: Postfix-uttryck: 2 3 4 * +

Resultatet av uttrycket ovan är 14.

Exempel 2: Postfix-uttryck: 3 4 * 2 5 * +

Resultatet av uttrycket ovan är 22.

Algoritm för att utvärdera postfix-uttryck

1. Läs en karaktär
2. Om tecknet är en siffra, konvertera tecknet till int och tryck in heltal i stacken.
3. Om karaktären är en operator,
   • Plocka elementen från högen två gånger och få två operander.
   • Utför operationen
   • Skjut in resultatet i högen.

Konvertering av infix till postfix

Här kommer vi att använda stackdatastrukturen för konvertering av infixuttryck till prefixuttryck. Närhelst en operatör stöter på, trycker vi in ​​operatören i stacken. Om vi ​​stöter på en operand, så lägger vi till operanden till uttrycket.

Regler för konvertering från infix till postfix-uttryck

1. Skriv ut operanden när de anländer.
2. Om stapeln är tom eller innehåller en vänstra parentes ovanpå, tryck på den inkommande operatören till stacken.
3. Om den inkommande symbolen är '(', tryck på den till högen.
4. Om den inkommande symbolen är ')', poppar du högen och skriv ut operatorerna tills den vänstra parentesen hittas.
5. Om den inkommande symbolen har högre prioritet än toppen av högen, tryck den på högen.
6. Om den inkommande symbolen har lägre prioritet än toppen av högen, poppar du och skriv ut toppen av högen. Testa sedan den inkommande operatören mot den nya toppen av stapeln.
7. Om den inkommande operatören har samma prioritet med toppen av stacken, använd då associativitetsreglerna. Om associativiteten är från vänster till höger, poppa och skriv ut toppen av stapeln och tryck sedan på den inkommande operatorn. Om associativiteten är från höger till vänster, tryck på den inkommande operatören.
8. I slutet av uttrycket, pop och skriv ut alla operatorer i stacken.

Låt oss förstå genom ett exempel.

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

Det sista postfix-uttrycket för infix-uttryck (K + L - M*N + (O^P) * W/U/V * T + Q) är KL+MN*-OP^W*U/V/T*+Q+ .