Wat is infix-notatie?
Een tussenvoegselnotatie is een notatie waarin een uitdrukking in een gebruikelijk of normaal formaat wordt geschreven. Het is een notatie waarbij de operatoren tussen de operanden liggen. De voorbeelden van tussenvoegselnotatie zijn A+B, A*B, A/B, enz.
Zoals we in de bovenstaande voorbeelden kunnen zien, bestaan alle operatoren tussen de operanden, dus het zijn infix-notaties. Daarom kan de syntaxis van de infix-notatie als volgt worden geschreven:
Infix-expressies parseren
Om een uitdrukking te ontleden, moeten we voor twee dingen zorgen, namelijk: Voorrang van operator En Associativiteit . Operatorvoorrang betekent de voorrang van een operator boven een andere operator. Bijvoorbeeld:
lijst als array
A + B * C → A + (B * C)
Omdat de vermenigvuldigingsoperator een hogere prioriteit heeft dan de opteloperator, wordt de B * C-expressie eerst geëvalueerd. Het resultaat van de vermenigvuldiging van B * C wordt opgeteld bij de A.
Voorrangsvolgorde
| Exploitanten | Symbolen |
|---|---|
| Haakje | { }, (), [ ] |
| Exponentiële notatie | ^ |
| Vermenigvuldiging en deling | *, / |
| Optellen en aftrekken | +, - |
Associativiteit betekent dat er operatoren met dezelfde prioriteit in de uitdrukking voorkomen. In de uitdrukking, d.w.z. A + B - C, hebben de operatoren '+' en '-' bijvoorbeeld dezelfde prioriteit, dus worden ze geëvalueerd met behulp van associativiteit. Omdat zowel '+' als '-' linksassociatief zijn, worden ze geëvalueerd als (A + B) - C.
Associatieve orde
| Exploitanten | Associativiteit |
|---|---|
| ^ | Rechts naar links |
| *, / | Van links naar rechts |
| +, - | Van links naar rechts |
Laten we de associativiteit begrijpen aan de hand van een voorbeeld.
1 + 2*3 + 30/5
Omdat in de bovenstaande uitdrukking * en / dezelfde prioriteit hebben, zullen we de associativiteitsregel toepassen. Zoals we in de bovenstaande tabel kunnen zien, zijn * en /-operatoren associativiteit van links naar rechts, dus scannen we vanaf de meest linkse operator. De operator die als eerste komt, wordt als eerste beoordeeld. De operator * verschijnt vóór de operator / en de vermenigvuldiging wordt eerst uitgevoerd.
1+ (2*3) + (30/5)
1+6+6=13
Wat is voorvoegselnotatie?
Een voorvoegselnotatie is een andere vorm van expressie, maar vereist geen andere informatie zoals voorrang en associativiteit, terwijl een tussenvoegselnotatie informatie over voorrang en associativiteit vereist. Het is ook bekend als Poolse notatie . In de prefixnotatie komt een operator vóór de operanden. De syntaxis van de voorvoegselnotatie wordt hieronder gegeven:
Bijvoorbeeld, als de tussenvoegselexpressie 5+1 is, dan is de voorvoegselexpressie die overeenkomt met deze tussenvoegselexpressie +51.
Als de tussenvoegselexpressie is:
een * b + c
↓
*ab+c
↓
+*abc (voorvoegselexpressie)
Beschouw een ander voorbeeld:
A+B*C
Eerste scan: In de bovenstaande uitdrukking heeft de vermenigvuldigingsoperator een hogere prioriteit dan de opteloperator; de voorvoegselnotatie van B*C zou (*BC) zijn.
A + *BC
Tweede scan: Bij de tweede scan zou het voorvoegsel zijn:
+A *BC
In de bovenstaande expressie gebruiken we twee scans om infix naar prefix-expressie te converteren. Als de uitdrukking complex is, hebben we een groter aantal scans nodig. We moeten die methode gebruiken die slechts één scan vereist en het gewenste resultaat oplevert. Als we via één scan de gewenste output bereiken, zou het algoritme efficiënt zijn. Dit is alleen mogelijk door gebruik te maken van een stapel.
Conversie van Infix naar Prefix met behulp van Stack
K + L - M * N + (O^P) * W/U/V * T + Q
Als we de uitdrukking van tussenvoegsel naar voorvoegsel converteren, moeten we eerst de uitdrukking omkeren.
De omgekeerde uitdrukking zou zijn:
Q + T * V/U/W * ) P^O(+ N*M - L + K
Om de prefix-expressie te verkrijgen, hebben we een tabel gemaakt die uit drie kolommen bestaat, d.w.z. invoerexpressie, stapel en prefix-expressie. Wanneer we een symbool tegenkomen, voegen we het eenvoudigweg toe aan de prefix-expressie. Als we de operator tegenkomen, duwen we hem in de stapel.
| Invoerexpressie | Stapel | Voorvoegselexpressie |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| IN | +* | QTV |
| / | +*/ | QTV |
| IN | +*/ | QTVU |
| / | +*// | QTVU |
| IN | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| P | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| O | +*//*)^ | QTVUWPO |
| ( | +*//* | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| N | ++ | QTVUWPO^*//*N |
| * | +** | QTVUWPO^*//*N |
| M | +** | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| L | ++- | QTVUWPO^*//*NM*L |
| + | +-+ | QTVUWPO^*//*NM*L |
| K | +-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK+-++ |
De bovenstaande uitdrukking, d.w.z. QTVUWPO^*//*NM*LK+-++, is geen definitieve uitdrukking. We moeten deze uitdrukking omkeren om de prefix-expressie te verkrijgen.
Regels voor de conversie van infix naar prefix-expressie:
- Draai eerst de infix-expressie om die in de opgave wordt gegeven.
- Scan de uitdrukking van links naar rechts.
- Wanneer de operanden binnenkomen, drukt u ze af.
- Als de operator arriveert en de stapel blijkt leeg te zijn, duwt u de operator eenvoudigweg in de stapel.
- Als de inkomende operator een hogere prioriteit heeft dan de TOP van de stapel, duwt u de inkomende operator in de stapel.
- Als de inkomende operator dezelfde voorrang heeft met een TOP van de stapel, duw dan de inkomende operator in de stapel.
- Als de inkomende operator een lagere prioriteit heeft dan de TOP van de stapel, knal dan de bovenkant van de stapel af en druk deze af. Test de binnenkomende operator opnieuw tegen de bovenkant van de stapel en haal de operator van de stapel totdat hij de operator met een lagere prioriteit of dezelfde prioriteit vindt.
- Als de inkomende operator dezelfde prioriteit heeft ten opzichte van de bovenkant van de stapel en de inkomende operator ^ is, laat dan de bovenkant van de stapel vallen totdat de voorwaarde waar is. Als de voorwaarde niet waar is, drukt u op de operator ^.
- Wanneer we het einde van de uitdrukking bereiken, knallen en drukken we alle operatoren vanaf de bovenkant van de stapel af.
- Als de operator ')' is, duw hem dan in de stapel.
- Als de operator '(' is, verwijder dan alle operators van de stapel totdat ) openingshaakje in de stapel wordt gevonden.
- Als de bovenkant van de stapel ')' is, duwt u de operator op de stapel.
- Draai aan het einde de uitvoer om.
Pseudocode van conversie van tussenvoegsel naar voorvoegsel
Function InfixtoPrefix( stack, infix) infix = reverse(infix) loop i = 0 to infix.length if infix[i] is operand → prefix+= infix[i] else if infix[i] is '(' → stack.push(infix[i]) else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found else if infix[i] is an operator(+, -, *, /, ^) → if the stack is empty then push infix[i] on the top of the stack. Else → If precedence(infix[i] > precedence(stack.top)) → Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) && infix[i] == '^') → Pop and print the top values of the stack till the condition is true → Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) → Push infix[i] on to the stack Else if(infix[i] <precedence(stack.top)) → pop the stack values and print them till is not empty infix[i] < precedence(stack.top) push on to end loop remaining elements of prefix="reverse(prefix)" return pre> <hr></precedence(stack.top))>