TechCodeview

Abans d'entendre la conversió de notació infixa a postfix, hauríem de conèixer per separat les notacions infix i postfix.

Un infix i un postfix són les expressions. Una expressió consta de constants, variables i símbols. Els símbols poden ser operadors o parèntesis. Tots aquests components s'han d'ordenar segons un conjunt de regles perquè totes aquestes expressions es puguin avaluar mitjançant el conjunt de regles.

Exemples d'expressions són:

5 + 6

herència java

A-B

(P * 5)

Totes les expressions anteriors tenen una estructura comuna, és a dir, tenim un operador entre els dos operands. Un operand és un objecte o un valor sobre el qual s'ha de realitzar l'operació. En les expressions anteriors, 5, 6 són els operands mentre que '+', '-' i '*' són els operadors.

Què és la notació infixa?

Quan l'operador s'escriu entre els operands, es coneix com a notació infixa . L'operand no ha de ser sempre una constant o una variable; també pot ser una expressió en si mateixa.

Per exemple,

(p + q) * (r + s)

En l'expressió anterior, ambdues expressions de l'operador de multiplicació són els operands, és a dir, (p + q) , i (r + s) són els operands.

En l'expressió anterior, hi ha tres operadors. Els operands del primer operador més són p i q, els operands del segon operador més són r i s. Mentre es realitza el operacions sobre l'expressió, hem de seguir un conjunt de regles per avaluar el resultat. En el l'expressió anterior, es realitzaria l'operació d'addició a les dues expressions, és a dir, p+q i r+s, i després es realitzaria l'operació de multiplicació.

La sintaxi de la notació infixa es mostra a continuació:

Si només hi ha un operador a l'expressió, no cal aplicar cap regla. Per exemple, 5 + 2; en aquesta expressió, l'operació d'addició es pot realitzar entre els dos operands (5 i 2), i el resultat de l'operació seria 7.

Si hi ha diversos operadors a l'expressió, cal seguir alguna regla per avaluar l'expressió.

Si l'expressió és:

4 + 6 * 2

Si l'operador més s'avalua primer, l'expressió seria així:

10 * 2 = 20

Si primer s'avalua l'operador de multiplicació, l'expressió es veuria així:

4 + 12 = 16

El problema anterior es pot resoldre seguint les regles de precedència de l'operador. En l'expressió algebraica, l'ordre de precedència de l'operador es dóna a la taula següent:

La primera preferència es dóna al parèntesi; aleshores es dóna preferència als exponents. En el cas d'operadors de múltiples exponents, l'operació s'aplicarà de dreta a esquerra.

Per exemple:

2^2^3 = 2^8

= 256

Després d'avaluar els operadors d'exponent, multiplicació i divisió. Si els dos operadors estan presents a l'expressió, l'operació s'aplicarà d'esquerra a dreta.

La següent preferència es dóna a la suma i la resta. Si els dos operadors estan disponibles a l'expressió, anem d'esquerra a dreta.

Els operadors que tenen la mateixa precedència s'anomenen com associativitat de l'operador . Si anem d'esquerra a dreta, es coneix com a associatiu d'esquerra. Si anem de dreta a esquerra, es coneix com a dret-associatiu.

Problema amb la notació infixa

Per avaluar l'expressió infixa, hauríem de conèixer el precedència de l'operador regles, i si els operadors tenen la mateixa precedència, hauríem de seguir les associativitat regles. L'ús del parèntesi és molt important en la notació infixa per controlar l'ordre en què s'ha de realitzar l'operació. Els parèntesis milloren la llegibilitat de l'expressió. Una expressió infixa és la forma més comuna d'escriure l'expressió, però no és fàcil analitzar i avaluar l'expressió infixa sense ambigüitat. Així doncs, els matemàtics i els lògics van estudiar aquest problema i van descobrir dues altres maneres d'escriure expressions que són el prefix i el postfix. Les dues expressions no requereixen cap parèntesi i es poden analitzar sense ambigüitat. No requereix precedència d'operadors i regles d'associativitat.

Com trobar números bloquejats a Android

Expressió Postfix

L'expressió postfix és una expressió en què l'operador s'escriu després dels operands. Per exemple, l'expressió postfixa de la notació infixa ( 2+3) es pot escriure com 23+.

Alguns punts clau sobre l'expressió postfix són:

• En l'expressió postfixa, les operacions es realitzen en l'ordre en què s'han escrit d'esquerra a dreta.
• No requereix cap parèntesi.
• No cal que apliquem regles de precedència d'operadors i regles d'associativitat.

Algorisme per avaluar l'expressió postfix

• Escaneja l'expressió d'esquerra a dreta fins que ens trobem amb qualsevol operador.
• Realitza l'operació
• Substituïu l'expressió pel seu valor calculat.
• Repetiu els passos de l'1 al 3 fins que no hi hagi més operadors.

Entendrem l'algorisme anterior a través d'un exemple.

Expressió infixa: 2 + 3 * 4

Començarem a escanejar des de l'esquerra la major part de l'expressió. L'operador de multiplicació és un operador que apareix primer mentre s'escaneja d'esquerra a dreta. Ara, l'expressió seria:

Expressió = 2 + 34*

= 2 + 12

De nou, escanejarem d'esquerra a dreta, i l'expressió seria:

Expressió = 2 12 +

= 14

Avaluació de l'expressió postfix mitjançant stack.

• Escaneja l'expressió d'esquerra a dreta.
• Si ens trobem amb qualsevol operand a l'expressió, llavors empenyem l'operand a la pila.
• Quan ens trobem amb qualsevol operador a l'expressió, aleshores fem sortir els operands corresponents de la pila.
• Quan acabem amb l'escaneig de l'expressió, el valor final roman a la pila.

Entenem l'avaluació de l'expressió postfix mitjançant stack.

Exemple 1: Expressió postfix: 2 3 4 * +

El resultat de l'expressió anterior és 14.

Exemple 2: Expressió postfix: 3 4 * 2 5 * +

El resultat de l'expressió anterior és 22.

Algorisme per avaluar l'expressió postfix

1. Llegir un personatge
2. Si el caràcter és un dígit, convertiu-lo en int i introduïu l'enter a la pila.
3. Si el personatge és un operador,
   • Treu els elements de la pila dues vegades obtenint dos operands.
   • Realitza l'operació
   • Introduïu el resultat a la pila.

Conversió d'infix a postfix

Aquí, utilitzarem l'estructura de dades de pila per a la conversió de l'expressió infixa a l'expressió prefixa. Sempre que es trobi un operador, empenyem l'operador a la pila. Si ens trobem amb un operand, afegim l'operand a l'expressió.

Regles per a la conversió d'expressió infixa a postfix

qui va crear l'escola

1. Imprimeix l'operand a mesura que arriben.
2. Si la pila està buida o conté un parèntesi esquerre a la part superior, premeu l'operador entrant a la pila.
3. Si el símbol entrant és '(', premeu-lo a la pila.
4. Si el símbol d'entrada és ')', obre la pila i imprimeix els operadors fins que es trobi el parèntesi esquerre.
5. Si el símbol entrant té una prioritat més alta que la part superior de la pila, premeu-lo a la pila.
6. Si el símbol entrant té una precedència inferior a la part superior de la pila, apareix i imprimeix la part superior de la pila. A continuació, proveu l'operador entrant amb la nova part superior de la pila.
7. Si l'operador entrant té la mateixa prioritat amb la part superior de la pila, feu servir les regles d'associativitat. Si l'associativitat és d'esquerra a dreta, apareix i imprimeix la part superior de la pila i després premeu l'operador entrant. Si l'associativitat és de dreta a esquerra, premeu l'operador entrant.
8. Al final de l'expressió, apareix i imprimeix tots els operadors de la pila.

Entenem-ho a través d'un exemple.

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

L'expressió postfix final de l'expressió infixa (K + L - M*N + (O^P) * W/U/V * T + Q) és KL+MN*-OP^W*U/V/T*+Q+ .