Què és la notació infixa?
Una notació infixa és una notació en la qual s'escriu una expressió en un format habitual o normal. És una notació en què els operadors es troben entre els operands. Els exemples de notació infixa són A+B, A*B, A/B, etc.
Com podem veure en els exemples anteriors, tots els operadors existeixen entre els operands, de manera que són notacions infixes. Per tant, la sintaxi de la notació infixa es pot escriure com:
Anàlisi d'expressions Infix
Per analitzar qualsevol expressió, hem de tenir cura de dues coses, és a dir, Precedència de l'operador i Associativitat . Precedència de l'operador significa la precedència de qualsevol operador sobre un altre operador. Per exemple:
A + B * C → A + (B * C)
Com que l'operador de multiplicació té una prioritat més alta sobre l'operador d'addició, primer s'avaluarà l'expressió B * C. El resultat de la multiplicació de B * C s'afegeix a la A.
Ordre de preferència
| Operadors | Símbols |
|---|---|
| Parèntesis | { }, ( ), [ ] |
| Notació exponencial | ^ |
| Multiplicació i divisió | *, / |
| Sumes i restes | +, - |
Associativitat significa quan els operadors amb la mateixa precedència existeixen a l'expressió. Per exemple, a l'expressió, és a dir, A + B - C, els operadors '+' i '-' tenen la mateixa precedència, de manera que s'avaluen amb l'ajuda de l'associativitat. Com que '+' i '-' són associatius a l'esquerra, es valorarien com (A + B) - C.
Ordre d'associativitat
| Operadors | Associativitat |
|---|---|
| ^ | De dreta a esquerra |
| *, / | Esquerra a dreta |
| +, - | Esquerra a dreta |
Entenem l'associativitat a través d'un exemple.
1 + 2*3 + 30/5
Atès que en l'expressió anterior, * i / tenen la mateixa precedència, per tant aplicarem la regla d'associativitat. Com podem observar a la taula anterior que els operadors * i / tenen associativitat d'esquerra a dreta, així que escanejarem des de l'operador més esquerre. S'avaluarà primer l'operador que vingui primer. L'operador * apareix abans de l'operador / i la multiplicació es faria primer.
1+ (2*3) + (30/5)
1+6+6 = 13
Què és la notació del prefix?
Una notació de prefix és una altra forma d'expressió, però no requereix cap altra informació com la precedència i l'associativitat, mentre que una notació infixa requereix informació de precedència i associativitat. També es coneix com notació polonesa . En notació de prefix, un operador va abans dels operands. La sintaxi de la notació del prefix es mostra a continuació:
Per exemple, si l'expressió infix és 5+1, aleshores l'expressió prefix corresponent a aquesta expressió infix és +51.
Si l'expressió infixa és:
a * b + c
↓
poda a-b
*ab+c
↓
+*abc (expressió de prefix)
Considereu un altre exemple:
A + B * C
Primer escaneig: En l'expressió anterior, l'operador de multiplicació té una prioritat més alta que l'operador d'addició; la notació prefixada de B*C seria (*BC).
A + *BC
Segon escaneig: En la segona exploració, el prefix seria:
+A *BC
A l'expressió anterior, fem servir dues exploracions per convertir l'infix a l'expressió de prefix. Si l'expressió és complexa, necessitem un nombre més gran d'exploracions. Hem d'utilitzar aquest mètode que només requereix una exploració i proporciona el resultat desitjat. Si aconseguim la sortida desitjada mitjançant una exploració, l'algorisme seria eficient. Això només és possible utilitzant una pila.
Conversió d'Infix a Prefix mitjançant Stack
K + L - M * N + (O^P) * W/U/V * T + Q
Si estem convertint l'expressió d'infix a prefix, primer hem d'invertir l'expressió.
L'expressió inversa seria:
truncar i eliminar la diferència
Q + T * V/U/W * ) P^O(+ N*M - L + K
Per obtenir l'expressió de prefix, hem creat una taula que consta de tres columnes, és a dir, expressió d'entrada, pila i expressió de prefix. Quan ens trobem amb qualsevol símbol, simplement l'afegim a l'expressió del prefix. Si ens trobem amb l'operador, l'empenyem a la pila.
| Expressió d'entrada | Pila | Expressió de prefix |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| EN | +* | QTV |
| / | +*/ | QTV |
| EN | +*/ | QTVU |
| / | +*// | QTVU |
| EN | +*// | 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+-++ |
L'expressió anterior, és a dir, QTVUWPO^*//*NM*LK+-++, no és una expressió final. Hem d'invertir aquesta expressió per obtenir l'expressió del prefix.
Regles per a la conversió d'expressió infix a prefix:
- Primer, inverteix l'expressió infixa que es dóna al problema.
- Escaneja l'expressió d'esquerra a dreta.
- Sempre que arribin els operands, imprimiu-los.
- Si l'operador arriba i es troba que la pila està buida, simplement empeny l'operador a la pila.
- Si l'operador entrant té una prioritat més alta que la part SUPERIOR de la pila, premeu l'operador entrant a la pila.
- Si l'operador entrant té la mateixa prioritat amb un TOP de la pila, premeu l'operador entrant a la pila.
- Si l'operador entrant té una precedència més baixa que la part superior de la pila, apareix i imprimeix la part superior de la pila. Torneu a provar l'operador d'entrada amb la part superior de la pila i extreu l'operador de la pila fins que trobi l'operador d'una precedència inferior o de la mateixa.
- Si l'operador entrant té la mateixa precedència amb la part superior de la pila i l'operador entrant és ^, aleshores apareix la part superior de la pila fins que la condició sigui certa. Si la condició no és certa, premeu l'operador ^.
- Quan arribem al final de l'expressió, apareix i imprimeix tots els operadors des de la part superior de la pila.
- Si l'operador és ')', premeu-lo a la pila.
- Si l'operador és '(', aleshores traieu tots els operadors de la pila fins que trobi el claudàtor d'obertura a la pila.
- Si la part superior de la pila és ')', premeu l'operador a la pila.
- Al final, inverteix la sortida.
Pseudocodi de conversió d'infix a prefix
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))>