Какво е инфикс нотация?
Инфиксната нотация е нотация, в която изразът е написан в обичаен или нормален формат. Това е нотация, в която операторите се намират между операндите. Примерите за инфиксна нотация са 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
За да получим префиксния израз, създадохме таблица, която се състои от три колони, т.е. входен израз, стек и префиксен израз. Когато срещнем някакъв символ, ние просто го добавяме към префиксния израз. Ако срещнем оператора, ще го избутаме в стека.
блокирани контакти
| Входен израз | Стек | Префиксен израз |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| IN | +* | QTV |
| / | +*/ | QTV |
| IN | +*/ | QTVU |
| / | +*// | QTVU |
| IN | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| П | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| О | +*//*)^ | QTVUWPO |
| ( | +*//* | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| н | ++ | QTVUWPO^*//*N |
| * | +++ | QTVUWPO^*//*N |
| М | +++ | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| Л | ++- | QTVUWPO^*//*NM*L |
| + | +-+ | QTVUWPO^*//*NM*L |
| К | +-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK+-++ |
Горният израз, т.е. QTVUWPO^*//*NM*LK+-++, не е окончателен израз. Трябва да обърнем този израз, за да получим префиксния израз.
Правила за преобразуване на инфикс в префикс израз:
- Първо, обърнете инфикс израза, даден в проблема.
- Сканирайте израза отляво надясно.
- Всеки път, когато операндите пристигнат, отпечатайте ги.
- Ако операторът пристигне и се установи, че стекът е празен, просто натиснете оператора в стека.
- Ако входящият оператор има по-висок приоритет от ГОРНАТА част на стека, натиснете входящия оператор в стека.
- Ако входящият оператор има същия приоритет с TOP на стека, натиснете входящия оператор в стека.
- Ако входящият оператор има по-нисък приоритет от ГОРНАТА част на стека, извадете и отпечатайте горната част на стека. Тествайте отново входящия оператор спрямо горната част на стека и извадете оператора от стека, докато намери оператора с по-нисък или същия приоритет.
- Ако входящият оператор има същия приоритет като горната част на стека и входящият оператор е ^, тогава извадете горната част на стека, докато условието стане вярно. Ако условието не е вярно, натиснете оператора ^.
- Когато стигнем до края на израза, изскачаме и отпечатваме всички оператори от горната част на стека.
- Ако операторът е ')', тогава го избутайте в стека.
- Ако операторът е '(', тогава извадете всички оператори от стека, докато открие ) отваряща скоба в стека.
- Ако горната част на стека е ')', натиснете оператора върху стека.
- В края обърнете изхода.
Псевдокод на преобразуване на инфикс в префикс
Function InfixtoPrefix( stack, infix) infix = reverse(infix) loop i = 0 to infix.length if infix[i] is operand → prefix+= infix[i] else if infix[i] is '(' → stack.push(infix[i]) else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found else if infix[i] is an operator(+, -, *, /, ^) → if the stack is empty then push infix[i] on the top of the stack. Else → If precedence(infix[i] > precedence(stack.top)) → Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) && infix[i] == '^') → Pop and print the top values of the stack till the condition is true → Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) → 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))>