logo

Претворите инфиксну нотацију у префикс

Шта је инфиксна нотација?

Инфиксна нотација је нотација у којој је израз написан у уобичајеном или нормалном формату. То је нотација у којој се оператори налазе између операнада. Примери инфиксне нотације су А+Б, А*Б, А/Б, итд.

Као што видимо у горњим примерима, сви оператори постоје између операнада, тако да су инфиксне нотације. Дакле, синтакса инфиксне нотације се може написати као:

Парсинг инфикс израза

Да бисмо рашчланили било који израз, морамо да водимо рачуна о две ствари, тј. Приоритет оператера и Асоцијативност . Приоритет оператора значи предност било ког оператора над другим оператором. На пример:

име посебних знакова

А + Б * Ц → А + (Б * Ц)

Како оператор множења има већи приоритет у односу на оператор сабирања, тако ће се Б * Ц израз прво проценити. Резултат множења Б * Ц се додаје А.

Редослед приоритета

Оператери Симболи
Заграда { }, ( ), [ ]
Експоненцијална нотација ^
Множење и дељење *, /
Сабирање и одузимање +, -

Асоцијативност значи када у изразу постоје оператори са истим приоритетом. На пример, у изразу, тј. А + Б - Ц, оператори '+' и '-' имају исти приоритет, па се процењују уз помоћ асоцијативности. Пошто су и '+' и '-' лево-асоцијативни, они би се оценили као (А + Б) - Ц.

Поредак асоцијативности

Оператери Асоцијативност
^ Десна на лево
*, / С лева надесно
+, - С лева надесно

Хајде да разумемо асоцијативност кроз пример.

1 + 2*3 + 30/5

Пошто у горњем изразу * и / имају исти приоритет, па ћемо применити правило асоцијативности. Као што можемо приметити у горњој табели да * и / оператори имају асоцијативност с лева на десно, тако ћемо скенирати од крајњег левог оператора. Оператер који дође први ће бити процењен први. Оператор * се појављује пре / оператора, а множење би било прво.

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

1+6+6 = 13

Шта је префикс нотација?

Префиксна нотација је други облик изражавања, али не захтева друге информације као што су приоритет и асоцијативност, док инфиксна нотација захтева информације о приоритету и асоцијативности. Такође је познато као пољска нотација . У префиксној нотацији, оператор долази испред операнда. Синтакса префиксне нотације је дата у наставку:

На пример, ако је инфиксни израз 5+1, онда је префиксни израз који одговара овом инфиксном изразу +51.

Ако је инфиксни израз:

а * б + ц

*аб+ц

+*абц (префикс израз)

Размотрите још један пример:

А + Б * Ц

Прво скенирање: У горњем изразу, оператор множења има већи приоритет од оператора сабирања; нотација префикса Б*Ц би била (*БЦ).

А + *БЦ

Друго скенирање: У другом скенирању, префикс би био:

+А *БЦ

У горњем изразу користимо два скенирања да конвертујемо инфиксни у префиксни израз. Ако је израз сложен, онда нам је потребан већи број скенирања. Морамо да користимо ону методу која захтева само једно скенирање, а даје жељени резултат. Ако постигнемо жељени резултат једним скенирањем, онда би алгоритам био ефикасан. Ово је могуће само коришћењем стека.

Конверзија инфикса у префикс помоћу стека

К + Л - М * Н + (О^П) * В/У/В * Т + К

Ако конвертујемо израз из инфикса у префикс, прво морамо да обрнемо израз.

Обрнути израз би био:

К + Т * В/У/В * ) П^О(+ Н*М - Л + К

Да бисмо добили израз префикса, направили смо табелу која се састоји од три колоне, тј. улазног израза, стека и израза префикса. Када наиђемо на било који симбол, једноставно га додамо у израз префикса. Ако наиђемо на оператера, гурнућемо га у стек.

Улазни израз Гомила Префиксни израз
П П
+ + П
Т + КТ
* +* КТ
ИН +* КТВ
/ +*/ КТВ
ИН +*/ КТВУ
/ +*// КТВУ
ИН +*// КТВУВ
* +*//* КТВУВ
) +*//*) КТВУВ
П +*//*) КТВУВП
^ +*//*)^ КТВУВП
О +*//*)^ КТВУВПО
( +*//* КТВУВПО^
+ ++ КТВУВПО^*//*
Н ++ КТВУВПО^*//*Н
* +** КТВУВПО^*//*Н
М +** КТВУВПО^*//*НМ
- ++- КТВУВПО^*//*НМ*
Л ++- КТВУВПО^*//*НМ*Л
+ +-+ КТВУВПО^*//*НМ*Л
К +-+ КТВУВПО^*//*НМ*ЛК
КТВУВПО^*//*НМ*ЛК+-++

Горњи израз, тј. КТВУВПО^*//*НМ*ЛК+-++, није коначни израз. Морамо да обрнемо овај израз да бисмо добили израз префикса.

Правила за конверзију инфиксног у префикс израза:

формат јава стринг
  • Прво, обрните инфиксни израз дат у задатку.
  • Скенирај израз с лева на десно.
  • Кад год операнди стигну, одштампајте их.
  • Ако оператер стигне и открије се да је стек празан, једноставно гурните оператора у стек.
  • Ако долазни оператор има већи приоритет од ВРХА стека, гурните долазног оператора у стек.
  • Ако долазни оператер има исти приоритет са ТОП стека, гурните долазног оператора у стек.
  • Ако долазни оператор има мањи приоритет од ВРХА стека, искочите и одштампајте врх стека. Поново тестирајте долазни оператор на врху стека и избаците оператора из стека док не пронађе оператор нижег или истог приоритета.
  • Ако долазни оператор има исти приоритет са врхом стека, а долазни оператор је ^, онда искочите врх стека док услов не буде истинит. Ако услов није тачан, притисните оператор ^.
  • Када дођемо до краја израза, искочите и одштампајте све операторе са врха стека.
  • Ако је оператор ')', онда га гурните у стек.
  • Ако је оператор '(', онда извуците све операторе из стека док не пронађе ) отворну заграду у стеку.
  • Ако је врх стека ')', гурните оператор на стек.
  • На крају обрните излаз.

Псеудокод конверзије инфикса у префикс

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