Ce este notația infixă?
O notație infixă este o notație în care o expresie este scrisă într-un format obișnuit sau normal. Este o notație în care operatorii se află între operanzi. Exemplele de notație infixă sunt A+B, A*B, A/B etc.
conversie java șir în int
După cum putem vedea în exemplele de mai sus, toți operatorii există între operanzi, deci sunt notații infixe. Prin urmare, sintaxa notației infixe poate fi scrisă ca:
Analizarea expresiilor Infix
Pentru a analiza orice expresie, trebuie să avem grijă de două lucruri, și anume, Prioritatea operatorului și Asociativitatea . Prioritatea operatorului înseamnă precedența oricărui operator față de alt operator. De exemplu:
A + B * C → A + (B * C)
Deoarece operatorul de înmulțire are o prioritate mai mare față de operatorul de adunare, expresia B * C va fi evaluată mai întâi. Rezultatul înmulțirii lui B * C se adaugă la A.
Ordinea de prioritate
| Operatori | Simboluri |
|---|---|
| Paranteze | { }, ( ), [ ] |
| Notă exponențială | ^ |
| Înmulțirea și împărțirea | *, / |
| Adunare si scadere | +, - |
Asociativitatea înseamnă atunci când operatorii cu aceeași precedență există în expresie. De exemplu, în expresia, adică, A + B - C, operatorii „+” și „-” au aceeași prioritate, deci sunt evaluați cu ajutorul asociativității. Deoarece atât „+” cât și „-” sunt asociative la stânga, ele ar fi evaluate ca (A + B) - C.
Ordinea asociativității
| Operatori | Asociativitatea |
|---|---|
| ^ | De la dreapta la stanga |
| *, / | De la stânga la dreapta |
| +, - | De la stânga la dreapta |
Să înțelegem asociativitatea printr-un exemplu.
1 + 2*3 + 30/5
Deoarece în expresia de mai sus, * și / au aceeași prioritate, deci vom aplica regula asociativității. După cum putem observa în tabelul de mai sus că operatorii * și / au asociativitate de la stânga la dreapta, așa că vom scana de la operatorul din stânga. Operatorul care vine primul va fi evaluat primul. Operatorul * apare înaintea operatorului /, iar înmulțirea ar fi făcută mai întâi.
1+ (2*3) + (30/5)
1+6+6 = 13
Ce este notația de prefix?
O notație de prefix este o altă formă de expresie, dar nu necesită alte informații, cum ar fi precedența și asociativitatea, în timp ce o notație infixă necesită informații de precedență și asociativitate. Este cunoscut și ca notație poloneză . În notația cu prefix, un operator vine înaintea operanzilor. Sintaxa notării prefixului este dată mai jos:
De exemplu, dacă expresia infixă este 5+1, atunci expresia prefix corespunzătoare acestei expresii infix este +51.
Dacă expresia infixă este:
a * b + c
↓
*ab+c
↓
conversia obiectului în șir
+*abc (expresie prefix)
Luați în considerare un alt exemplu:
A + B * C
Prima scanare: În expresia de mai sus, operatorul de înmulțire are o prioritate mai mare decât operatorul de adunare; notația de prefix a lui B*C ar fi (*BC).
A + *BC
A doua scanare: În a doua scanare, prefixul ar fi:
+A *BC
În expresia de mai sus, folosim două scanări pentru a converti expresia infix în prefix. Dacă expresia este complexă, atunci avem nevoie de un număr mai mare de scanări. Trebuie să folosim acea metodă care necesită o singură scanare și oferă rezultatul dorit. Dacă obținem rezultatul dorit printr-o singură scanare, atunci algoritmul ar fi eficient. Acest lucru este posibil doar prin utilizarea unei stive.
Conversia Infix la Prefix folosind Stack
K + L - M * N + (O^P) * W/U/V * T + Q
Dacă convertim expresia din infix în prefix, trebuie mai întâi să inversăm expresia.
Expresia inversă ar fi:
Q + T * V/U/W * ) P^O(+ N*M - L + K
Pentru a obține expresia de prefix, am creat un tabel care constă din trei coloane, adică expresie de intrare, stivă și expresie de prefix. Când întâlnim orice simbol, pur și simplu îl adăugăm în expresia prefixului. Dacă întâlnim operatorul, îl vom împinge în stivă.
| Expresia de intrare | Grămadă | Expresie de prefix |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| ÎN | +* | QTV |
| / | +*/ | QTV |
| ÎN | +*/ | QTVU |
| / | +*// | QTVU |
| ÎN | +*// | 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+-++ |
Expresia de mai sus, adică QTVUWPO^*//*NM*LK+-++, nu este o expresie finală. Trebuie să inversăm această expresie pentru a obține expresia prefix.
Reguli pentru conversia expresiei infix în prefix:
c++ int la șir
- Mai întâi, inversează expresia infixă dată în problemă.
- Scanați expresia de la stânga la dreapta.
- Ori de câte ori sosesc operanzii, tipăriți-i.
- Dacă sosește operatorul și se constată că stiva este goală, atunci pur și simplu împingeți operatorul în stivă.
- Dacă operatorul de intrare are o prioritate mai mare decât partea de sus a stivei, împingeți operatorul de intrare în stivă.
- Dacă operatorul de intrare are aceeași prioritate cu un TOP al stivei, împingeți operatorul de intrare în stivă.
- Dacă operatorul de intrare are o prioritate mai mică decât partea de sus a stivei, pop și tipăriți partea de sus a stivei. Testați din nou operatorul de intrare pe partea de sus a stivei și scoateți operatorul din stivă până când găsește operatorul cu o prioritate inferioară sau cu aceeași prioritate.
- Dacă operatorul de intrare are aceeași prioritate cu partea de sus a stivei și operatorul de intrare este ^, atunci deschideți partea de sus a stivei până când condiția este adevărată. Dacă condiția nu este adevărată, apăsați operatorul ^.
- Când ajungem la sfârșitul expresiei, pop și tipăriți toți operatorii din partea de sus a stivei.
- Dacă operatorul este „)”, atunci împingeți-l în stivă.
- Dacă operatorul este „(”, atunci scoateți toți operatorii din stivă până când găsește ) paranteză de deschidere în stivă.
- Dacă partea de sus a stivei este „)”, împingeți operatorul pe stivă.
- La sfârșit, inversați ieșirea.
Pseudocod de conversie infix în 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))>