Co to jest notacja infiksowa?
Notacja wrostkowa to notacja, w której wyrażenie jest zapisane w zwykłym lub normalnym formacie. Jest to zapis, w którym operatory znajdują się pomiędzy operandami. Przykładami notacji infiksowej są A+B, A*B, A/B itd.
Jak widać w powyższych przykładach, wszystkie operatory występują pomiędzy operandami, są więc notacjami infiksowymi. Dlatego składnię notacji infiksowej można zapisać jako:
Analizowanie wyrażeń Infix
Aby przeanalizować dowolne wyrażenie, musimy zadbać o dwie rzeczy, tj. Pierwszeństwo operatora I Łączność . Pierwszeństwo operatora oznacza pierwszeństwo dowolnego operatora przed innym operatorem. Na przykład:
A + B * C → A + (B * C)
Ponieważ operator mnożenia ma wyższy priorytet niż operator dodawania, dlatego wyrażenie B*C zostanie ocenione jako pierwsze. Wynik mnożenia B * C jest dodawany do A.
Kolejność pierwszeństwa
| Operatorzy | Symbolika |
|---|---|
| Nawias | { }, ( ), [ ] |
| Notacja wykładnicza | ^ |
| Mnożenie i dzielenie | *, / |
| Dodawanie i odejmowanie | +, - |
Łączność oznacza, że w wyrażeniu istnieją operatory o tym samym priorytecie. Przykładowo w wyrażeniu A + B - C operatory '+' i '-' mają ten sam priorytet, dlatego są oceniane za pomocą asocjatywności. Ponieważ zarówno „+”, jak i „-” są lewostronnie skojarzone, zostaną one ocenione jako (A + B) - C.
Porządek skojarzeń
| Operatorzy | Łączność |
|---|---|
| ^ | Od prawej do lewej |
| *, / | Od lewej do prawej |
| +, - | Od lewej do prawej |
Przyjrzyjmy się skojarzeniom na przykładzie.
pętla Java
1 + 2*3 + 30/5
Ponieważ w powyższym wyrażeniu * i / mają ten sam priorytet, zastosujemy więc regułę skojarzenia. Jak możemy zaobserwować w powyższej tabeli, operatory * i / mają łączność od lewej do prawej, dlatego będziemy skanować od operatora położonego skrajnie po lewej stronie. Operator, który zajmie pierwsze miejsce, zostanie oceniony jako pierwszy. Operator * pojawia się przed operatorem / i mnożenie zostanie wykonane jako pierwsze.
1+ (2*3) + (30/5)
1+6+6 = 13
Co to jest notacja przedrostkowa?
Notacja przedrostkowa jest inną formą wyrażenia, ale nie wymaga innych informacji, takich jak pierwszeństwo i powiązanie, podczas gdy notacja wrostkowa wymaga informacji o pierwszeństwie i powiązaniu. Znany jest również jako notacja polska . W notacji przedrostkowej operator występuje przed operandami. Poniżej podano składnię zapisu przedrostkowego:
Na przykład, jeśli wyrażenie wrostkowe ma wartość 5+1, wówczas wyrażenie przedrostkowe odpowiadające temu wyrażeniu wrostkowemu wynosi +51.
dlaczego interfejs znacznika w Javie
Jeśli wyrażenie wrostkowe to:
a * b + c
↓
*ab+c
↓
+*abc (wyrażenie przedrostkowe)
Rozważ inny przykład:
A + B * C
Pierwszy skan: W powyższym wyrażeniu operator mnożenia ma wyższy priorytet niż operator dodawania; zapis przedrostkowy B*C będzie miał postać (*BC).
A + *BC
producent Linuksa
Drugi skan: Podczas drugiego skanowania prefiks będzie wyglądał następująco:
+A *BC
W powyższym wyrażeniu używamy dwóch skanów do konwersji wyrażenia infiksowego na wyrażenie przedrostkowe. Jeśli wyrażenie jest złożone, wówczas potrzebujemy większej liczby skanów. Musimy zastosować tę metodę, która wymaga tylko jednego skanowania i zapewnia pożądany efekt. Jeśli w jednym skanie osiągniemy pożądany wynik, algorytm będzie skuteczny. Jest to możliwe tylko przy użyciu stosu.
Konwersja infiksu na prefiks za pomocą stosu
K + L - M * N + (O^P) * W/U/V * T + Q
Jeśli konwertujemy wyrażenie z infiksu na przedrostek, musimy najpierw odwrócić wyrażenie.
Wyrażenie odwrotne wyglądałoby następująco:
Q + T * V/U/W * ) P^O(+ N*M - L + K
Aby uzyskać wyrażenie przedrostkowe, stworzyliśmy tabelę składającą się z trzech kolumn, tj. wyrażenia wejściowego, stosu i wyrażenia przedrostkowego. Kiedy napotykamy dowolny symbol, po prostu dodajemy go do wyrażenia przedrostkowego. Jeśli spotkamy operatora, wepchniemy go na stos.
| Wyrażenie wejściowe | Stos | Wyrażenie przedrostkowe |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| W | +* | QTV |
| / | +*/ | QTV |
| W | +*/ | QTVU |
| / | +*// | QTVU |
| W | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| P | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| O | +*//*)^ | QTVUWPO |
| ( | +*//* | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| N | ++ | QTVUWPO^*//*N |
| * | +*** | QTVUWPO^*//*N |
| M | +*** | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| L | ++- | QTVUWPO^*//*NM*L |
| + | +-+ | QTVUWPO^*//*NM*L |
| K | +-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK+-++ |
Powyższe wyrażenie, tj. QTVUWPO^*//*NM*LK+-++, nie jest wyrażeniem ostatecznym. Musimy odwrócić to wyrażenie, aby uzyskać wyrażenie przedrostkowe.
Reguły konwersji wyrażenia infiksowego na wyrażenie przedrostkowe:
- Najpierw odwróć wyrażenie wrostkowe podane w zadaniu.
- Zeskanuj wyrażenie od lewej do prawej.
- Gdy tylko pojawią się operandy, wydrukuj je.
- Jeśli operator przybędzie i okaże się, że stos jest pusty, po prostu wepchnij operatora na stos.
- Jeśli operator przychodzący ma wyższy priorytet niż GÓRA stosu, wepchnij operatora przychodzącego na stos.
- Jeśli operator przychodzący ma taki sam priorytet z GÓRĄ stosu, wepchnij operatora przychodzącego na stos.
- Jeśli operator przychodzący ma niższy priorytet niż GÓRA stosu, kliknij i wydrukuj górę stosu. Przetestuj ponownie operator przychodzący na górze stosu i usuń go ze stosu, aż znajdzie operator o niższym lub takim samym priorytecie.
- Jeśli operator przychodzący ma taki sam priorytet jak szczyt stosu, a operator przychodzący to ^, wówczas przesuwaj wierzchołek stosu, aż warunek zostanie spełniony. Jeśli warunek nie jest spełniony, naciśnij operator ^.
- Kiedy dojdziemy do końca wyrażenia, wyskocz i wypisz wszystkie operatory z góry stosu.
- Jeśli operatorem jest „)”, włóż go na stos.
- Jeśli operatorem jest '(', usuń wszystkie operatory ze stosu, aż znajdzie ) nawias otwierający na stosie.
- Jeśli szczyt stosu to „)”, wciśnij operatora na stosie.
- Na koniec odwróć wyjście.
Pseudokod konwersji infiksu na przedrostek
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))>