TechCodeview

Какво е инфикс нотация?

Инфиксната нотация е нотация, в която изразът е написан в обичаен или нормален формат. Това е нотация, в която операторите се намират между операндите. Примерите за инфиксна нотация са A+B, A*B, A/B и т.н.

Както можем да видим в горните примери, всички оператори съществуват между операндите, така че те са инфиксни означения. Следователно синтаксисът на инфиксната нотация може да бъде написан като:

Разбор на Infix изрази

За да анализираме всеки израз, трябва да се погрижим за две неща, т.е. Приоритет на оператора и Асоциативност . Приоритет на оператор означава приоритет на всеки оператор пред друг оператор. Например:

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

Тъй като операторът за умножение има по-висок приоритет пред оператора за събиране, така че изразът B * C ще бъде оценен първи. Резултатът от умножението на B * C се добавя към A.

Ред на предимство

Асоциативност означава, че в израза съществуват оператори с еднакъв приоритет. Например в израза, т.е. A + B - C, операторите '+' и '-' имат еднакъв приоритет, така че се оценяват с помощта на асоциативност. Тъй като и '+', и '-' са ляво-асоциативни, те ще бъдат оценени като (A + B) - C.

Ред на асоциативност

Нека разберем асоциативността чрез пример.

java балонно сортиране

1 + 2*3 + 30/5

Тъй като в горния израз * и / имат еднакъв приоритет, ще приложим правилото за асоциативност. Както можем да видим в горната таблица, че операторите * и / имат асоциативност отляво надясно, така че ще сканираме от най-левия оператор. Операторът, който дойде първи, ще бъде оценен първи. Операторът * се появява преди оператора / и умножението ще се извърши първо.

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

1+6+6 = 13

пример за OS с отворен код е

Какво е префиксна нотация?

Префиксната нотация е друга форма на изразяване, но не изисква друга информация като приоритет и асоциативност, докато инфиксната нотация изисква информация за приоритет и асоциативност. Известен е още като полска нотация . В префиксната нотация операторът стои преди операндите. Синтаксисът на нотацията на префикса е даден по-долу:

Например, ако инфиксният израз е 5+1, тогава префиксният израз, съответстващ на този инфиксен израз, е +51.

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

a * b + c

↓

*ab+c

css удебелен

↓

+*abc (префиксен израз)

Помислете за друг пример:

A + B * C

Първо сканиране: В горния израз операторът за умножение има по-висок приоритет от оператора за събиране; префиксната нотация на B*C би била (*BC).

A + *BC

Второ сканиране: При второто сканиране префиксът ще бъде:

+A *BC

В горния израз използваме две сканирания, за да преобразуваме инфикс в префиксен израз. Ако изразът е сложен, тогава се нуждаем от по-голям брой сканирания. Трябва да използваме този метод, който изисква само едно сканиране и дава желания резултат. Ако постигнем желания резултат чрез едно сканиране, тогава алгоритъмът ще бъде ефективен. Това е възможно само чрез използване на стек.

Преобразуване на Infix в Prefix с помощта на Stack

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

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

Обратният израз би бил:

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

За да получим префиксния израз, създадохме таблица, която се състои от три колони, т.е. входен израз, стек и префиксен израз. Когато срещнем някакъв символ, ние просто го добавяме към префиксния израз. Ако срещнем оператора, ще го избутаме в стека.

блокирани контакти

Горният израз, т.е. QTVUWPO^*//*NM*LK+-++, не е окончателен израз. Трябва да обърнем този израз, за ​​да получим префиксния израз.

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

• Първо, обърнете инфикс израза, даден в проблема.
• Сканирайте израза отляво надясно.
• Всеки път, когато операндите пристигнат, отпечатайте ги.
• Ако операторът пристигне и се установи, че стекът е празен, просто натиснете оператора в стека.
• Ако входящият оператор има по-висок приоритет от ГОРНАТА част на стека, натиснете входящия оператор в стека.
• Ако входящият оператор има същия приоритет с TOP на стека, натиснете входящия оператор в стека.
• Ако входящият оператор има по-нисък приоритет от ГОРНАТА част на стека, извадете и отпечатайте горната част на стека. Тествайте отново входящия оператор спрямо горната част на стека и извадете оператора от стека, докато намери оператора с по-нисък или същия приоритет.
• Ако входящият оператор има същия приоритет като горната част на стека и входящият оператор е ^, тогава извадете горната част на стека, докато условието стане вярно. Ако условието не е вярно, натиснете оператора ^.
• Когато стигнем до края на израза, изскачаме и отпечатваме всички оператори от горната част на стека.
• Ако операторът е ')', тогава го избутайте в стека.
• Ако операторът е '(', тогава извадете всички оператори от стека, докато открие ) отваряща скоба в стека.
• Ако горната част на стека е ')', натиснете оператора върху стека.
• В края обърнете изхода.

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

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