Hva er infiksnotasjon?

En infiksnotasjon er en notasjon der et uttrykk er skrevet i et vanlig eller normalt format. Det er en notasjon der operatorene ligger mellom operandene. Eksemplene på infiksnotasjon er A+B, A*B, A/B, etc.

Som vi kan se i eksemplene ovenfor, eksisterer alle operatorene mellom operandene, så de er infiksnotasjoner. Derfor kan syntaksen for infiksnotasjon skrives som:

hvordan konvertere streng til heltall i java

Parsing av infiksuttrykk

For å analysere ethvert uttrykk, må vi ta vare på to ting, dvs. Operatør forrang og Assosiativitet . Operatørprioritet betyr enhver operatørs forrang fremfor en annen operatør. For eksempel:

A + B * C → A + (B * C)

Siden multiplikasjonsoperatoren har en høyere prioritet over addisjonsoperatoren, vil B * C-uttrykk bli evaluert først. Resultatet av multiplikasjonen av B * C legges til A.

Forrangsrekkefølge

Associativitet betyr når operatorene med samme forrang eksisterer i uttrykket. For eksempel, i uttrykket, dvs. A + B - C, har '+' og '-' operatorer samme prioritet, så de blir evaluert ved hjelp av assosiativitet. Siden både '+' og '-' er venstreassosiative, vil de bli evaluert som (A + B) - C.

Assosiativitetsrekkefølge

La oss forstå assosiativiteten gjennom et eksempel.

1 + 2*3 + 30/5

Siden i uttrykket ovenfor har * og / samme prioritet, så vi vil bruke assosiativitetsregelen. Som vi kan observere i tabellen ovenfor at * og / operatører har venstre til høyre assosiativitet, så vi vil skanne fra operatøren lengst til venstre. Operatøren som kommer først vil bli evaluert først. Operatoren * vises foran /-operatoren, og multiplikasjon vil bli gjort først.

1+ (2*3) + (30/5)

1+6+6 = 13

Hva er prefiksnotasjon?

En prefiksnotasjon er en annen form for uttrykk, men den krever ikke annen informasjon som forrang og assosiativitet, mens en infiksnotasjon krever informasjon om forrang og assosiativitet. Det er også kjent som polsk notasjon . I prefiksnotasjon kommer en operator foran operandene. Syntaksen for prefiksnotasjon er gitt nedenfor:

For eksempel, hvis infiksuttrykket er 5+1, så er prefiksuttrykket som tilsvarer dette infiksuttrykket +51.

Hvis infiksuttrykket er:

hvordan oppfant skolen

a * b + c

↓

*ab+c

↓

+*abc (prefiksuttrykk)

Tenk på et annet eksempel:

A + B * C

Første Skann: I uttrykket ovenfor har multiplikasjonsoperatoren høyere prioritet enn addisjonsoperatoren; prefiksnotasjonen til B*C vil være (*BC).

A + *BC

Andre skanning: I den andre skanningen vil prefikset være:

+A *BC

forskjellen mellom array og arraylist

I uttrykket ovenfor bruker vi to skanninger for å konvertere infiks til prefiksuttrykk. Hvis uttrykket er komplekst, krever vi et større antall skanninger. Vi må bruke den metoden som krever bare én skanning, og gir ønsket resultat. Hvis vi oppnår ønsket utgang gjennom én skanning, vil algoritmen være effektiv. Dette er kun mulig ved å bruke en stabel.

rev eller ulv

Konvertering av Infix til Prefiks ved hjelp av Stack

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

Hvis vi konverterer uttrykket fra infiks til prefiks, må vi først reversere uttrykket.

Det omvendte uttrykket vil være:

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

For å få prefiksuttrykket har vi laget en tabell som består av tre kolonner, dvs. input-uttrykk, stack og prefiksuttrykk. Når vi møter et symbol, legger vi det ganske enkelt til prefiksuttrykket. Hvis vi møter operatøren, skyver vi den inn i stabelen.

Uttrykket ovenfor, dvs. QTVUWPO^*//*NM*LK+-++, er ikke et endelig uttrykk. Vi må reversere dette uttrykket for å få prefiksuttrykket.

Regler for konvertering av infiks til prefiksuttrykk:

• Reverser først infiksuttrykket gitt i problemet.
• Skann uttrykket fra venstre til høyre.
• Når operandene kommer, skriv dem ut.
• Hvis operatøren ankommer og stabelen viser seg å være tom, er det bare å skyve operatøren inn i stabelen.
• Hvis den innkommende operatøren har høyere prioritet enn TOPPEN av stabelen, skyv den innkommende operatøren inn i stabelen.
• Hvis den innkommende operatøren har samme prioritet med en TOPP av stabelen, skyv den innkommende operatøren inn i stabelen.
• Hvis den innkommende operatøren har lavere prioritet enn TOPPEN av stabelen, sprett og skriv ut toppen av stabelen. Test den innkommende operatøren mot toppen av stabelen igjen og trekk operatøren fra stabelen til den finner operatøren med lavere eller samme prioritet.
• Hvis den innkommende operatoren har samme prioritet med toppen av stabelen og den innkommende operatoren er ^, så sprett toppen av stabelen til betingelsen er sann. Hvis betingelsen ikke er sann, trykker du på ^-operatoren.
• Når vi kommer til slutten av uttrykket, spretter og skriver ut alle operatorene fra toppen av stabelen.
• Hvis operatøren er ')', skyv den inn i stabelen.
• Hvis operatøren er '(', skyver du alle operatørene fra stabelen til den finner ) åpningsbraketten i stabelen.
• Hvis toppen av stabelen er ')', skyv operatøren på stabelen.
• På slutten reverserer du utgangen.

Pseudokode for konvertering av infiks til prefiks

 Function InfixtoPrefix( stack, infix) infix = reverse(infix) loop i = 0 to infix.length if infix[i] is operand &#x2192; prefix+= infix[i] else if infix[i] is &apos;(&apos; &#x2192; stack.push(infix[i]) else if infix[i] is &apos;)&apos; &#x2192; pop and print the values of stack till the symbol &apos;)&apos; is not found else if infix[i] is an operator(+, -, *, /, ^) &#x2192; if the stack is empty then push infix[i] on the top of the stack. Else &#x2192; If precedence(infix[i] &gt; precedence(stack.top)) &#x2192; Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) &amp;&amp; infix[i] == &apos;^&apos;) &#x2192; Pop and print the top values of the stack till the condition is true &#x2192; Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) &#x2192; 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))>