Voordat we de conversie van infix- naar postfix-notatie begrijpen, moeten we de infix- en postfix-notatie afzonderlijk kennen.

Een tussenvoegsel en een achtervoegsel zijn de uitdrukkingen. Een expressie bestaat uit constanten, variabelen en symbolen. Symbolen kunnen operatoren of haakjes zijn. Al deze componenten moeten worden gerangschikt volgens een set regels, zodat al deze uitdrukkingen kunnen worden geëvalueerd met behulp van de set regels.

Voorbeelden van uitdrukkingen zijn:

5 + 6

A - B

(P*5)

Alle bovenstaande expressies hebben een gemeenschappelijke structuur, dat wil zeggen dat we een operator tussen de twee operanden hebben. Een operand is een object of een waarde waarop de bewerking moet worden uitgevoerd. In de bovenstaande uitdrukkingen zijn 5, 6 de operanden, terwijl '+', '-' en '*' de operators zijn.

Wat is infix-notatie?

Wanneer de operator tussen de operanden wordt geschreven, staat deze bekend als infix-notatie . Operand hoeft niet altijd een constante of variabele te zijn; het kan ook een uitdrukking zelf zijn.

Bijvoorbeeld,

(p + q) * (r + s)

In de bovenstaande uitdrukking zijn beide uitdrukkingen van de vermenigvuldigingsoperator de operanden, dat wil zeggen: (p + q) , En (r + s) zijn de operanden.

In de bovenstaande uitdrukking zijn er drie operatoren. De operanden voor de eerste plus-operator zijn p en q, de operanden voor de tweede plus-operator zijn r en s. Tijdens het uitvoeren van de bewerkingen op de uitdrukking, moeten we een aantal regels volgen om het resultaat te evalueren. In de bovenstaande uitdrukking, zou de optelbewerking worden uitgevoerd op de twee uitdrukkingen, d.w.z. p+q en r+s, en vervolgens zou de vermenigvuldigingsbewerking worden uitgevoerd.

De syntaxis van de infix-notatie wordt hieronder gegeven:

Als de expressie slechts één operator bevat, hoeven we geen enkele regel toe te passen. Bijvoorbeeld 5 + 2; in deze uitdrukking kan een optelbewerking worden uitgevoerd tussen de twee operanden (5 en 2), en het resultaat van de bewerking zou 7 zijn.

Als de expressie meerdere operators bevat, moet er een regel worden gevolgd om de expressie te evalueren.

Als de uitdrukking is:

4+6*2

Als de plus-operator eerst wordt geëvalueerd, ziet de expressie er als volgt uit:

10 * 2 = 20

gedeeltelijke afhankelijkheid

Als de vermenigvuldigingsoperator eerst wordt geëvalueerd, ziet de uitdrukking er als volgt uit:

4 + 12 = 16

Het bovenstaande probleem kan worden opgelost door de voorrangsregels van de operator te volgen. In de algebraïsche uitdrukking wordt de volgorde van de prioriteit van de operator gegeven in de onderstaande tabel:

De eerste voorkeur gaat uit naar het haakje; vervolgens wordt de voorkeur gegeven aan de exponenten. In het geval van meerdere exponentoperatoren wordt de bewerking van rechts naar links toegepast.

Bijvoorbeeld:

2^2^3 = 2^8

= 256

Nadat de exponent-, vermenigvuldigings- en delingsoperatoren zijn geëvalueerd. Als beide operators in de uitdrukking aanwezig zijn, wordt de bewerking van links naar rechts toegepast.

De volgende voorkeur gaat uit naar optellen en aftrekken. Als beide operatoren beschikbaar zijn in de uitdrukking, gaan we van links naar rechts.

De operatoren met dezelfde prioriteit worden genoemd als associativiteit van de operator . Als we van links naar rechts gaan, wordt dit links-associatief genoemd. Als we van rechts naar links gaan, staat dit bekend als rechtsassociatief.

Probleem met tussenvoegselnotatie

Om de infix-expressie te evalueren, moeten we kennis hebben van de prioriteit van de operator regels, en als de operatoren dezelfde prioriteit hebben, dan moeten we de associativiteit reglement. Het gebruik van haakjes is erg belangrijk bij de infix-notatie om de volgorde te bepalen waarin de bewerking moet worden uitgevoerd. Haakjes verbeteren de leesbaarheid van de uitdrukking. Een tussenvoegselexpressie is de meest gebruikelijke manier om een ​​uitdrukking te schrijven, maar het is niet eenvoudig om de tussenvoegselexpressie zonder dubbelzinnigheid te ontleden en te evalueren. Wiskundigen en logici hebben dit probleem dus bestudeerd en twee andere manieren ontdekt om uitdrukkingen te schrijven, namelijk een voorvoegsel en een achtervoegsel. Beide uitdrukkingen vereisen geen haakjes en kunnen zonder dubbelzinnigheid worden geparseerd. Er zijn geen operatorprioriteit- en associativiteitsregels vereist.

Postfix-expressie

De postfix-expressie is een expressie waarin de operator na de operanden wordt geschreven. De postfix-expressie van de tussenvoegselnotatie ( 2+3) kan bijvoorbeeld worden geschreven als 23+.

Enkele belangrijke punten met betrekking tot de postfix-expressie zijn:

• Bij postfix-expressies worden bewerkingen uitgevoerd in de volgorde waarin ze zijn geschreven, van links naar rechts.
• Er zijn geen haakjes nodig.
• We hoeven geen operatorvoorrangsregels en associativiteitsregels toe te passen.

Algoritme om de postfix-expressie te evalueren

• Scan de uitdrukking van links naar rechts totdat we een operator tegenkomen.
• Voer de bewerking uit
• Vervang de expressie door de berekende waarde ervan.
• Herhaal de stappen 1 tot en met 3 totdat er geen operatoren meer zijn.

Laten we het bovenstaande algoritme begrijpen aan de hand van een voorbeeld.

Infix-expressie: 2 + 3 * 4

We beginnen vanaf het grootste deel van de uitdrukking vanaf de linkerkant te scannen. De vermenigvuldigingsoperator is een operator die als eerste verschijnt tijdens het scannen van links naar rechts. De uitdrukking zou nu zijn:

Hoe geblokkeerde nummers op Android te vinden

Uitdrukking = 2 + 34*

= 2 + 12

Nogmaals, we scannen van links naar rechts en de uitdrukking zou zijn:

Expressie = 2 12 +

= 14

Evaluatie van postfix-expressie met behulp van stack.

• Scan de uitdrukking van links naar rechts.
• Als we een operand in de uitdrukking tegenkomen, duwen we de operand in de stapel.
• Wanneer we een operator in de uitdrukking tegenkomen, halen we de overeenkomstige operanden van de stapel.
• Wanneer we klaar zijn met het scannen van de uitdrukking, blijft de uiteindelijke waarde in de stapel staan.

Laten we de evaluatie van postfix-expressie met behulp van stack begrijpen.

Voorbeeld 1: Postfix-expressie: 2 3 4 * +

Het resultaat van de bovenstaande uitdrukking is 14.

Voorbeeld 2: Postfix-expressie: 3 4 * 2 5 * +

Het resultaat van de bovenstaande uitdrukking is 22.

Algoritme om postfix-expressie te evalueren

1. Lees een personage
2. Als het teken een cijfer is, converteert u het teken naar int en duwt u het gehele getal in de stapel.
3. Als het personage een operator is,
   • Haal de elementen twee keer uit de stapel en verkrijg twee operanden.
   • Voer de bewerking uit
   • Duw het resultaat in de stapel.

Conversie van infix naar postfix

Hier zullen we de stapelgegevensstructuur gebruiken voor de conversie van infix-expressie naar prefix-expressie. Wanneer een operator tegenkomt, duwen we de operator in de stapel. Als we een operand tegenkomen, voegen we de operand toe aan de uitdrukking.

Regels voor de conversie van infix- naar postfix-expressie

1. Druk de operand af zodra ze binnenkomen.
2. Als de stapel leeg is of een linkerhaakje bovenaan bevat, duwt u de binnenkomende operator op de stapel.
3. Als het binnenkomende symbool '(' is, duw het dan op de stapel.
4. Als het binnenkomende symbool ')' is, knalt u de stapel open en drukt u de operatoren af ​​totdat het linkerhaakje is gevonden.
5. Als het binnenkomende symbool een hogere prioriteit heeft dan de bovenkant van de stapel, duw het dan op de stapel.
6. Als het binnenkomende symbool een lagere prioriteit heeft dan de bovenkant van de stapel, knal dan de bovenkant van de stapel af en druk deze af. Test vervolgens de inkomende operator tegen de nieuwe bovenkant van de stapel.
7. Als de inkomende operator dezelfde prioriteit heeft als de bovenkant van de stapel, gebruik dan de associativiteitsregels. Als de associativiteit van links naar rechts is, knal en druk dan de bovenkant van de stapel af en duw vervolgens op de binnenkomende operator. Als de associativiteit van rechts naar links is, duw dan op de binnenkomende operator.
8. Aan het einde van de expressie popt u alle operatoren van de stapel op en drukt u deze af.

Laten we het begrijpen aan de hand van een voorbeeld.

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

De laatste postfix-expressie van tussenvoegsel-expressie(K + L - M*N + (O^P) * W/U/V * T + Q) is KL+MN*-OP^W*U/V/T*+Q+ .