TechCodeview

Kas ir infiksa apzīmējums?

Infiksa apzīmējums ir apzīmējums, kurā izteiksme ir rakstīta parastā vai parastā formātā. Tas ir apzīmējums, kurā operatori atrodas starp operandiem. Infiksa apzīmējumu piemēri ir A+B, A*B, A/B utt.

Kā redzams iepriekš minētajos piemēros, visi operatori pastāv starp operandiem, tāpēc tie ir infiksa apzīmējumi. Tāpēc infiksa apzīmējuma sintaksi var uzrakstīt šādi:

Infix izteiksmju parsēšana

Lai parsētu jebkuru izteiksmi, mums ir jārūpējas par divām lietām, t.i., Operatora prioritāte un Asociativitāte . Operatora prioritāte ir jebkura operatora prioritāte pār citu operatoru. Piemēram:

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

Tā kā reizināšanas operatoram ir augstāka prioritāte pār saskaitīšanas operatoru, B * C izteiksme tiks novērtēta vispirms. B * C reizināšanas rezultāts tiek pievienots A.

Prioritātes secība

Asociativitāte nozīmē, kad izteiksmē pastāv operatori ar vienādu prioritāti. Piemēram, izteiksmē, t.i., A + B - C, operatoriem '+' un '-' ir vienāda prioritāte, tāpēc tie tiek novērtēti ar asociativitātes palīdzību. Tā kā gan '+', gan '-' ir asociatīvi kreisi, tie tiks novērtēti kā (A + B) - C.

Asociatīvā secība

Sapratīsim asociativitāti, izmantojot piemēru.

1 + 2*3 + 30/5

Tā kā iepriekš minētajā izteiksmē * un / ir vienāda prioritāte, mēs piemērosim asociativitātes noteikumu. Iepriekš redzamajā tabulā redzams, ka * un / operatoriem ir asociativitāte no kreisās puses uz labo, tāpēc mēs skenēsim no vistālāk kreisā operatora. Vispirms tiks novērtēts operators, kurš būs pirmais. Pirms operatora / parādās operators *, un vispirms tiks veikta reizināšana.

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

1+6+6 = 13

Kas ir prefiksa apzīmējums?

Prefiksa apzīmējums ir vēl viens izteiksmes veids, taču tam nav nepieciešama cita informācija, piemēram, prioritāte un asociativitāte, savukārt infiksa apzīmējumam ir nepieciešama informācija par prioritāti un asociativitāti. Tas ir pazīstams arī kā poļu apzīmējums . Prefiksa apzīmējumā operators ir pirms operandi. Prefiksa apzīmējuma sintakse ir norādīta tālāk:

diskete

Piemēram, ja infiksa izteiksme ir 5+1, tad šai infiksa izteiksmei atbilstošā prefiksa izteiksme ir +51.

Ja infiksa izteiksme ir:

a * b + c

↓

*ab+c

↓

+*abc (prefiksa izteiksme)

Apsveriet citu piemēru:

A+B*C

Pirmā skenēšana: Iepriekš minētajā izteiksmē reizināšanas operatoram ir augstāka prioritāte nekā saskaitīšanas operatoram; B*C prefiksa apzīmējums būtu (*BC).

A + *BC

Otrā skenēšana: Otrajā skenēšanas reizē prefikss būtu:

kat timpf svars

+A *BC

Iepriekš minētajā izteiksmē mēs izmantojam divus skenējumus, lai pārveidotu infiksu par prefiksa izteiksmi. Ja izteiksme ir sarežģīta, mums ir nepieciešams lielāks skenēšanas skaits. Mums ir jāizmanto šī metode, kas prasa tikai vienu skenēšanu un nodrošina vēlamo rezultātu. Ja mēs sasniegtu vēlamo rezultātu ar vienu skenēšanu, tad algoritms būtu efektīvs. Tas ir iespējams, tikai izmantojot kaudzi.

Infix konvertēšana uz prefiksu, izmantojot Stack

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

Ja mēs pārvēršam izteiksmi no infiksa uz prefiksu, mums vispirms ir jāapgriež izteiksme.

Apgrieztā izteiksme būtu šāda:

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

Lai iegūtu prefiksa izteiksmi, esam izveidojuši tabulu, kas sastāv no trim kolonnām, t.i., ievades izteiksmes, steka un prefiksa izteiksmes. Kad mēs sastopam kādu simbolu, mēs to vienkārši pievienojam prefiksa izteiksmei. Ja mēs saskaramies ar operatoru, mēs to iestumsim kaudzē.

Iepriekš minētā izteiksme, t.i., QTVUWPO^*//*NM*LK+-++, nav galīgā izteiksme. Mums ir jāapgriež šī izteiksme, lai iegūtu prefiksa izteiksmi.

Noteikumi infiksa pārvēršanai prefiksa izteiksmē:

• Vispirms apgrieziet uzdevumā norādīto infiksa izteiksmi.
• Skenējiet izteiksmi no kreisās uz labo pusi.
• Ikreiz, kad pienāk operandi, izdrukājiet tos.
• Ja operators ierodas un tiek konstatēts, ka kaudze ir tukša, vienkārši iespiediet operatoru kaudzē.
• Ja ienākošajam operatoram ir augstāka prioritāte nekā steka AUGŠĀ, iebīdiet ienākošo operatoru kaudzē.
• Ja ienākošajam operatoram ir tāda pati prioritāte ar steka AUGŠU, iespiediet ienākošo operatoru kaudzē.
• Ja ienākošajam operatoram ir zemāka prioritāte nekā kaudzes AUGŠĀ, izspiediet un izdrukājiet kaudzes augšdaļu. Vēlreiz pārbaudiet ienākošo operatoru pret kaudzes augšdaļu un izceliet operatoru no kaudzes, līdz tas atrod operatoru ar zemāku prioritāti vai tādu pašu prioritāti.
• Ja ienākošajam operatoram ir tāda pati prioritāte kā steka augšdaļai un ienākošais operators ir ^, tad paceliet steka augšdaļu, līdz nosacījums ir patiess. Ja nosacījums nav patiess, nospiediet operatoru ^.
• Kad sasniedzam izteiksmes beigas, izspiediet un izdrukājiet visus operatorus no kaudzes augšdaļas.
• Ja operators ir “)”, ievietojiet to kaudzē.
• Ja operators ir '(', tad ievietojiet visus operatorus no steka, līdz tiek atrasts ) atvēršanas iekava stekā.
• Ja kaudzes augšdaļa ir ')', uzspiediet operatoru uz kaudzes.
• Beigās apgrieziet izvadi.

Pseidokods infiksa pārvēršanai 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))>