Zanim zrozumiemy konwersję z notacji infiksowej na notację postfiksową, powinniśmy poznać osobno notację infiksową i postfiksową.

Infiks i postfiks to wyrażenia. Wyrażenie składa się ze stałych, zmiennych i symboli. Symbole mogą być operatorami lub nawiasami. Wszystkie te komponenty muszą być ułożone zgodnie z zestawem reguł, aby wszystkie te wyrażenia mogły być oceniane przy użyciu zestawu reguł.

macierz w języku c

Przykładowe wyrażenia to:

5 + 6

A - B

(P*5)

Wszystkie powyższe wyrażenia mają wspólną strukturę, tzn. pomiędzy dwoma operandami mamy operator. Operand to obiekt lub wartość, na której ma zostać wykonana operacja. W powyższych wyrażeniach 5, 6 to operandy, a „+”, „-” i „*” to operatory.

Co to jest notacja infiksowa?

Kiedy operator jest wpisany pomiędzy operandami, nazywa się to notacja infiksowa . Operand nie musi być zawsze stałą lub zmienną; może to być również samo wyrażenie.

Na przykład,

(p + q) * (r + s)

W powyższym wyrażeniu oba wyrażenia operatora mnożenia są operandami, tj. (p + q) , I (r + s) są operandami.

W powyższym wyrażeniu występują trzy operatory. Operandy pierwszego operatora plus to p i q, operandy drugiego operatora plus to r i s. Podczas wykonywania operacji na wyrażeniu, musimy przestrzegać pewnego zestawu reguł, aby ocenić wynik. w powyżej, operacja dodawania zostanie przeprowadzona na dwóch wyrażeniach, tj. p+q i r+s, a następnie zostanie wykonana operacja mnożenia.

Poniżej podano składnię notacji infiksowej:

Jeśli w wyrażeniu występuje tylko jeden operator, nie wymagamy stosowania żadnej reguły. Na przykład 5 + 2; w tym wyrażeniu można wykonać operację dodawania pomiędzy dwoma operandami (5 i 2), a wynikiem operacji będzie 7.

Jeśli w wyrażeniu znajduje się wiele operatorów, należy zastosować się do pewnej reguły, aby obliczyć wyrażenie.

Jeśli wyrażenie to:

4+6*2

Jeśli operator plus zostanie oceniony jako pierwszy, wyrażenie będzie wyglądać następująco:

10 * 2 = 20

Jeśli operator mnożenia zostanie obliczony jako pierwszy, wyrażenie będzie wyglądać następująco:

4 + 12 = 16

Powyższy problem można rozwiązać stosując zasady pierwszeństwa operatorów. W wyrażeniu algebraicznym kolejność operatorów podana jest w poniższej tabeli:

Pierwszeństwo mają nawiasy; następnie pierwszeństwo mają wykładniki. W przypadku operatorów wielokrotnych wykładników operacja będzie wykonywana od prawej do lewej.

częściowa pochodna lateksu

Na przykład:

2^2^3 = 2^8

= 256

Po obliczeniu operatorów wykładnika, mnożenia i dzielenia. Jeżeli w wyrażeniu występują obydwa operatory, wówczas operacja zostanie wykonana od lewej do prawej.

Następną preferencją jest dodawanie i odejmowanie. Jeżeli w wyrażeniu dostępne są obydwa operatory, to przechodzimy od lewej do prawej.

Operatory, które mają taki sam priorytet, nazywane są skojarzenie operatorów . Jeśli przejdziemy od lewej do prawej, wówczas nazywa się to lewicowym skojarzeniem. Jeśli przejdziemy od prawej do lewej, wówczas nazywa się to prawicowym skojarzeniem.

Problem z notacją infiksową

Aby ocenić wyrażenie wrostkowe, powinniśmy wiedzieć o pierwszeństwo operatora reguły, a jeśli operatory mają ten sam priorytet, to powinniśmy postępować zgodnie z skojarzenie zasady. Użycie nawiasów jest bardzo ważne w notacji infiksowej, aby kontrolować kolejność wykonywania operacji. Nawiasy poprawiają czytelność wyrażenia. Wyrażenie wrostkowe jest najpowszechniejszym sposobem zapisywania wyrażeń, ale nie jest łatwo analizować i oceniać wyrażenie wrostkowe bez dwuznaczności. Zatem matematycy i logicy przestudiowali ten problem i odkryli dwa inne sposoby zapisywania wyrażeń, którymi są przedrostek i postfiks. Obydwa wyrażenia nie wymagają nawiasów i można je analizować bez dwuznaczności. Nie wymaga reguł pierwszeństwa operatorów i skojarzeń.

Wyrażenie postfiksowe

Wyrażenie postfiksowe to wyrażenie, w którym operator jest zapisywany po operandach. Na przykład wyrażenie przyrostkowe w notacji infiksowej ( 2+3) można zapisać jako 23+.

Oto kilka kluczowych punktów dotyczących wyrażenia postfiksowego:

• W wyrażeniu postfiksowym operacje są wykonywane w kolejności, w jakiej zostały zapisane, od lewej do prawej.
• Nie wymaga stosowania nawiasów.
• Nie musimy stosować reguł pierwszeństwa operatorów i reguł skojarzeń.

Algorytm obliczania wyrażenia przyrostkowego

• Skanuj wyrażenie od lewej do prawej, aż napotkamy dowolny operator.
• Wykonaj operację
• Zastąp wyrażenie obliczoną wartością.
• Powtarzaj kroki od 1 do 3, aż nie będzie już więcej operatorów.

Rozumiemy powyższy algorytm na przykładzie.

Wyrażenie wrostkowe: 2 + 3 * 4

Skanowanie zaczniemy od lewej części wyrażenia. Operator mnożenia to operator, który pojawia się jako pierwszy podczas skanowania od lewej do prawej. Teraz wyrażenie wyglądałoby tak:

Zmienna zmienna Java

Wyrażenie = 2 + 34*

= 2 + 12

Ponownie będziemy skanować od lewej do prawej, a wyrażenie będzie wyglądać:

Wyrażenie = 2 12 +

= 14

Ocena wyrażenia przyrostkowego przy użyciu stosu.

• Zeskanuj wyrażenie od lewej do prawej.
• Jeżeli w wyrażeniu napotkamy jakiś operand, to umieszczamy go na stosie.
• Kiedy w wyrażeniu napotkamy dowolny operator, usuwamy odpowiednie operandy ze stosu.
• Kiedy zakończymy skanowanie wyrażenia, ostateczna wartość pozostanie na stosie.

Przyjrzyjmy się ocenie wyrażenia postfiksowego przy użyciu stosu.

10 procent z 60

Przykład 1: Wyrażenie postfiksowe: 2 3 4 * +

Wynikiem powyższego wyrażenia jest 14.

Przykład 2: Wyrażenie postfiksowe: 3 4 * 2 5 * +

Wynikiem powyższego wyrażenia jest 22.

Algorytm obliczania wyrażenia przyrostkowego

1. Przeczytaj znak
2. Jeśli znak jest cyfrą, przekonwertuj go na int i włóż liczbę całkowitą na stos.
3. Jeśli znak jest operatorem,
   • Zrzuć elementy ze stosu dwukrotnie, uzyskując dwa operandy.
   • Wykonaj operację
   • Włóż wynik do stosu.

Konwersja infiksu na postfiks

Tutaj użyjemy struktury danych stosu do konwersji wyrażenia infiksowego na wyrażenie przedrostkowe. Ilekroć napotkamy operatora, wpychamy go na stos. Jeśli napotkamy operand, dołączamy go do wyrażenia.

Reguły konwersji wyrażenia infix na postfix

1. Wydrukuj operand, gdy tylko się pojawią.
2. Jeśli stos jest pusty lub zawiera lewy nawias na górze, wciśnij operator przychodzący na stos.
3. Jeśli przychodzącym symbolem jest „(”, włóż go na stos.
4. Jeśli przychodzącym symbolem jest „)”, rozłóż stos i wypisz operatory, aż znajdziesz lewy nawias.
5. Jeśli nadchodzący symbol ma wyższy priorytet niż wierzch stosu, włóż go na stos.
6. Jeśli nadchodzący symbol ma niższy priorytet niż wierzch stosu, wyskocz i wydrukuj wierzch stosu. Następnie przetestuj operatora przychodzącego na nowym wierzchołku stosu.
7. Jeśli operator przychodzący ma taki sam priorytet jak na górze stosu, użyj reguł skojarzenia. Jeśli skojarzenie jest od lewej do prawej, następnie pop i wydrukuj górę stosu, a następnie naciśnij operator przychodzący. Jeśli skojarzenie przebiega od prawej do lewej, naciśnij operatora przychodzącego.
8. Na końcu wyrażenia wypisz i wypisz wszystkie operatory stosu.

Rozumiemy na przykładzie.

Wyrażenie wrostkowe: K + L - M*N + (O^P) * W/U/V * T + Q

Końcowe wyrażenie przyrostkowe wyrażenia wrostkowego (K + L - M*N + (O^P) * W/U/V * T + Q) to KL+MN*-OP^W*U/V/T*+Q+ .