TechCodeview

Vad är infix notation?

En infixnotation är en notation där ett uttryck skrivs i ett vanligt eller normalt format. Det är en notation där operatorerna ligger mellan operanderna. Exemplen på infixnotation är A+B, A*B, A/B, etc.

Som vi kan se i exemplen ovan finns alla operatorer mellan operanderna, så de är infixnotationer. Därför kan syntaxen för infixnotation skrivas som:

Analysera infix-uttryck

För att kunna analysera ett uttryck måste vi ta hand om två saker, dvs. Operatörsföreträde och Associativitet . Operatörsföreträde betyder företräde för en operatör framför en annan operatör. Till exempel:

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

Eftersom multiplikationsoperatorn har högre företräde framför additionsoperatorn så kommer B * C-uttrycket att utvärderas först. Resultatet av multiplikationen av B * C läggs till A.

Företrädesordning

Associativitet betyder när operatorerna med samma prioritet finns i uttrycket. Till exempel, i uttrycket, dvs. A + B - C, har '+' och '-' operatorer samma prioritet, så de utvärderas med hjälp av associativitet. Eftersom både '+' och '-' är vänsterassociativa, skulle de utvärderas som (A + B) - C.

Associativitetsordning

Låt oss förstå associativiteten genom ett exempel.

1 + 2*3 + 30/5

Eftersom * och / i uttrycket ovan har samma företräde, så kommer vi att tillämpa associativitetsregeln. Som vi kan observera i tabellen ovan att * och / operatorer har vänster till höger associativitet, så kommer vi att skanna från operatorn längst till vänster. Den operatör som kommer först kommer att utvärderas först. Operatorn * visas före operatorn /, och multiplikation skulle göras först.

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

1+6+6 = 13

Vad är prefixnotation?

En prefixnotation är en annan form av uttryck men den kräver inte annan information som prioritet och associativitet, medan en infixnotation kräver information om prioritet och associativitet. Det är också känt som polsk notation . I prefixnotation kommer en operator före operanderna. Syntaxen för prefixnotation ges nedan:

Till exempel, om infixuttrycket är 5+1, så är prefixuttrycket som motsvarar detta infixuttryck +51.

Om infixuttrycket är:

a * b + c

↓

*ab+c

↓

+*abc (prefixuttryck)

Tänk på ett annat exempel:

A + B * C

Första genomsökningen: I uttrycket ovan har multiplikationsoperatorn en högre prioritet än additionsoperatorn; prefixnotationen för B*C skulle vara (*BC).

java-tecken till int

A + *BC

Andra skanningen: I den andra skanningen skulle prefixet vara:

+A *BC

I uttrycket ovan använder vi två skanningar för att konvertera infix till prefixuttryck. Om uttrycket är komplext kräver vi ett större antal skanningar. Vi måste använda den metoden som bara kräver en genomsökning och ger önskat resultat. Om vi ​​uppnår önskad utdata genom en skanning, så skulle algoritmen vara effektiv. Detta är endast möjligt genom att använda en stack.

Konvertering av Infix till Prefix med Stack

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

Om vi ​​konverterar uttrycket från infix till prefix, måste vi först vända på uttrycket.

Det omvända uttrycket skulle vara:

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

För att få prefixuttrycket har vi skapat en tabell som består av tre kolumner, det vill säga inmatningsuttryck, stack och prefixuttryck. När vi stöter på någon symbol lägger vi helt enkelt till den i prefixuttrycket. Om vi ​​stöter på operatören kommer vi att trycka in den i traven.

Ovanstående uttryck, dvs QTVUWPO^*//*NM*LK+-++, är inte ett slutgiltigt uttryck. Vi måste vända detta uttryck för att få prefixuttrycket.

Regler för konvertering av infix till prefixuttryck:

• Vänd först om infix-uttrycket som ges i problemet.
• Skanna uttrycket från vänster till höger.
• Skriv ut dem närhelst operanderna kommer.
• Om operatören kommer och stapeln visar sig vara tom, tryck helt enkelt in operatören i traven.
• Om den inkommande operatören har högre prioritet än toppen av stapeln, tryck in den inkommande operatören i stapeln.
• Om den inkommande operatören har samma företräde med en TOPP i stacken, tryck in den inkommande operatören i stacken.
• Om den inkommande operatören har lägre prioritet än toppen av stapeln, poppar och skriv ut toppen av stapeln. Testa den inkommande operatören mot toppen av stapeln igen och skjut operatören från stapeln tills den hittar operatören med lägre prioritet eller samma prioritet.
• Om den inkommande operatorn har samma prioritet som toppen av stacken och den inkommande operatorn är ^, skjut upp toppen av stacken tills villkoret är sant. Om villkoret inte är sant, tryck på ^-operatorn.
• När vi når slutet av uttrycket, poppar och skriver ut alla operatorer från toppen av stapeln.
• Om operatören är ')', tryck sedan in den i stapeln.
• Om operatören är '(', skjut sedan alla operatörer från stacken tills den hittar ) öppningsfästet i stacken.
• Om toppen av stapeln är ')', tryck operatören på stapeln.
• I slutet, vänd utmatningen.

Pseudokod för konvertering av infix till prefix

 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))>