Що таке інфіксна нотація?
Інфіксна нотація — це нотація, у якій вираз записується у звичайному чи нормальному форматі. Це нотація, в якій оператори знаходяться між операндами. Прикладами інфіксної нотації є A+B, A*B, A/B тощо.
Як ми можемо бачити в наведених вище прикладах, усі оператори існують між операндами, тому вони є інфіксними позначеннями. Тому синтаксис інфіксної нотації можна записати так:
Розбір інфіксних виразів
Щоб розібрати будь-який вираз, нам потрібно подбати про дві речі, тобто Пріоритет оператора і Асоціативність . Пріоритет оператора означає пріоритет будь-якого оператора над іншим оператором. Наприклад:
A + B * C → A + (B * C)
c++ int до рядка
Оскільки оператор множення має вищий пріоритет над оператором додавання, тому вираз B * C буде обчислено першим. Результат множення B * C додається до A.
Порядок пріоритету
| Оператори | Символи |
|---|---|
| Дужка | { }, ( ), [ ] |
| Експоненціальний запис | ^ |
| Множення і ділення | *, / |
| Додавання і віднімання | +, - |
Асоціативність означає, що у виразі існують оператори з однаковим пріоритетом. Наприклад, у виразі, тобто A + B - C, оператори «+» і «-» мають однаковий пріоритет, тому вони оцінюються за допомогою асоціативності. Оскільки і '+', і '-' є лівоасоціативними, вони будуть оцінені як (A + B) - C.
Порядок асоціативності
| Оператори | Асоціативність |
|---|---|
| ^ | Справа наліво |
| *, / | Зліва направо |
| +, - | Зліва направо |
Давайте розберемося в асоціативності на прикладі.
1 + 2*3 + 30/5
Оскільки у наведеному вище виразі * і / мають однаковий пріоритет, ми застосуємо правило асоціативності. Як ми можемо помітити в наведеній вище таблиці, оператори * та / мають асоціативність зліва направо, тому ми будемо сканувати з крайнього лівого оператора. Оператор, який прийде першим, буде оцінений першим. Оператор * з’являється перед оператором /, і множення буде виконано першим.
1+ (2*3) + (30/5)
1+6+6 = 13
Що таке префіксальна нотація?
Префіксна нотація є іншою формою вираження, але вона не вимагає іншої інформації, такої як пріоритет і асоціативність, тоді як інфіксна нотація вимагає інформації про пріоритет і асоціативність. Він також відомий як польська нотація . У префіксній нотації оператор стоїть перед операндами. Синтаксис нотації префіксів наведено нижче:
Наприклад, якщо інфіксний вираз дорівнює 5+1, то префіксний вираз, що відповідає цьому інфіксному виразу, дорівнює +51.
Якщо інфіксний вираз:
a * b + c
↓
java в об’єкт json
*ab+c
↓
+*abc (префіксний вираз)
Розглянемо інший приклад:
aes проти des
A + B * C
Перше сканування: У наведеному вище виразі оператор множення має вищий пріоритет, ніж оператор додавання; префіксальна нотація B*C буде (*BC).
A + *BC
Друге сканування: У другому скануванні префікс буде таким:
+A *BC
У наведеному вище виразі ми використовуємо два сканування, щоб перетворити інфіксний вираз у префіксний. Якщо вираз складний, то потрібна більша кількість сканувань. Нам потрібно використовувати той метод, який вимагає лише одного сканування та забезпечує бажаний результат. Якщо ми досягнемо бажаного результату за одне сканування, тоді алгоритм буде ефективним. Це можливо лише за допомогою стека.
Перетворення інфікса на префікс за допомогою стека
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 |
| Т | + | 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))>