Hvad er infix-notation?
En infix-notation er en notation, hvor et udtryk er skrevet i et normalt eller normalt format. Det er en notation, hvor operatorerne ligger mellem operanderne. Eksempler på infiksnotation er A+B, A*B, A/B osv.
Som vi kan se i ovenstående eksempler, eksisterer alle operatorerne mellem operanderne, så de er infix-notationer. Derfor kan syntaksen for infiksnotation skrives som:
hvordan man konverterer streng til heltal i java
Parsing af infix-udtryk
For at analysere ethvert udtryk skal vi tage os af to ting, dvs. Operatør forrang og Associativitet . Operatørprioritet betyder enhver operatørs forrang frem for en anden operatør. For eksempel:
A + B * C → A + (B * C)
Da multiplikationsoperatoren har en højere prioritet over additionsoperatoren, vil B * C-udtrykket blive evalueret først. Resultatet af multiplikationen af B * C lægges til A.
Forrangsrækkefølge
| Operatører | Symboler |
|---|---|
| Parentes | { }, ( ), [ ] |
| Eksponentiel notation | ^ |
| Multiplikation og division | *, / |
| Addition og subtraktion | +, - |
Associativitet betyder, når operatorerne med samme forrang findes i udtrykket. For eksempel, i udtrykket, dvs. A + B - C, har '+' og '-' operatorer den samme forrang, så de evalueres ved hjælp af associativitet. Da både '+' og '-' er venstreassociative, vil de blive evalueret som (A + B) - C.
Associativitetsorden
| Operatører | Associativitet |
|---|---|
| ^ | Højre til venstre |
| *, / | Venstre til højre |
| +, - | Venstre til højre |
Lad os forstå associativiteten gennem et eksempel.
1 + 2*3 + 30/5
Da * og / i ovenstående udtryk har samme forrang, så vil vi anvende associativitetsreglen. Som vi kan observere i ovenstående tabel, at * og / operatorer har venstre til højre associativitet, så vil vi scanne fra operatoren længst til venstre. Den operatør, der kommer først, vil blive evalueret først. Operatoren * vises foran /-operatoren, og multiplikation udføres først.
1+ (2*3) + (30/5)
1+6+6 = 13
Hvad er præfiksnotation?
En præfiksnotation er en anden udtryksform, men den kræver ikke anden information såsom forrang og associativitet, hvorimod en infiksnotation kræver information om forrang og associativitet. Det er også kendt som polsk notation . I præfiksnotation kommer en operator før operanderne. Syntaksen for præfiksnotation er angivet nedenfor:
For eksempel, hvis infiksudtrykket er 5+1, så er præfiksudtrykket, der svarer til dette infiksudtryk, +51.
Hvis infix-udtrykket er:
shreya ghoshal
a * b + c
↓
*ab+c
↓
+*abc (præfiksudtryk)
Overvej et andet eksempel:
A + B * C
Første scanning: I ovenstående udtryk har multiplikationsoperatoren en højere forrang end additionsoperatoren; præfiksnotationen for B*C ville være (*BC).
A + *BC
Anden scanning: I den anden scanning ville præfikset være:
+A *BC
forskel mellem array og arraylist
I ovenstående udtryk bruger vi to scanninger til at konvertere infix til præfiksudtryk. Hvis udtrykket er komplekst, kræver vi et større antal scanninger. Vi skal bruge den metode, der kun kræver én scanning og giver det ønskede resultat. Hvis vi opnår det ønskede output gennem én scanning, ville algoritmen være effektiv. Dette er kun muligt ved at bruge en stak.
ræv eller ulv
Konvertering af infix til præfiks ved hjælp af stak
K + L - M * N + (O^P) * W/U/V * T + Q
Hvis vi konverterer udtrykket fra infix til præfiks, skal vi først vende udtrykket om.
Det omvendte udtryk ville være:
Q + T * V/U/W * ) P^O(+ N*M - L + K
For at få præfiksudtrykket har vi lavet en tabel, der består af tre kolonner, dvs. inputudtryk, stak og præfiksudtryk. Når vi støder på et symbol, tilføjer vi det blot til præfiksudtrykket. Hvis vi støder på operatøren, skubber vi den ind i stakken.
| Input udtryk | Stak | Præfiksudtryk |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| I | +* | QTV |
| / | +*/ | QTV |
| I | +*/ | QTVU |
| / | +*// | QTVU |
| I | +*// | 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+-++ |
Ovenstående udtryk, dvs. QTVUWPO^*//*NM*LK+-++, er ikke et endeligt udtryk. Vi skal vende dette udtryk for at få præfiksudtrykket.
Regler for konvertering af infix til præfiksudtryk:
- Vend først infix-udtrykket, der er givet i problemet.
- Scan udtrykket fra venstre mod højre.
- Når operanderne ankommer, skal du udskrive dem.
- Hvis operatøren ankommer, og stakken viser sig at være tom, skal du blot skubbe operatøren ind i stakken.
- Hvis den indkommende operatør har højere forrang end toppen af stakken, skal du skubbe den indgående operatør ind i stakken.
- Hvis den indkommende operatør har samme forrang med en TOP af stakken, skal du skubbe den indgående operatør ind i stakken.
- Hvis den indgående operatør har lavere forrang end toppen af stakken, pop og udskriv toppen af stakken. Test den indkommende operatør mod toppen af stakken igen, og træk operatøren ud af stakken, indtil den finder operatøren med en lavere prioritet eller samme prioritet.
- Hvis den indgående operator har samme forrang med toppen af stakken, og den indgående operator er ^, så pop toppen af stakken, indtil betingelsen er sand. Hvis betingelsen ikke er sand, skal du trykke på operatoren ^.
- Når vi når slutningen af udtrykket, pop og udskriv alle operatorerne fra toppen af stakken.
- Hvis operatøren er ')', så skub den ind i stakken.
- Hvis operatøren er '(', så pop alle operatørerne fra stakken, indtil den finder ) åbningsbeslag i stakken.
- Hvis toppen af stakken er ')', skal du skubbe operatøren på stakken.
- Til sidst skal du vende outputtet.
Pseudokode for konvertering af infix til præfiks
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))>