Infix (lub infix ), prefiks (lub prefiks ) i Postfix (lub postfix ) notacje są formy pisemnej wyrażeń algebraicznych, które charakteryzują się względną pozycję podjętych przez operatorów i ich argumentów . Operator jest zapisywany przed swoimi operandami w notacji z prefiksem, między operandami w notacji z wrostkiem, a po operandach w notacji z postfiksem.
Notacja infiksowa ma sens tylko w przypadku operatorów pobierających dokładnie dwa operandy. Jest to najpowszechniejszy zapis dla operatorów binarnych w matematyce. Notacje z prefiksem i postfixem umożliwiają rezygnację z nawiasów, co prowadzi do bardziej zwartej notacji. Ale zrobić bez nawiasu przypuszcza, że znamy podpis (innymi słowy arity wszystkich operatorów) oraz że arity jest atrybutem podmiotów, które nie mogą być modyfikowane. Podpis służy do analizy wyrażeń podczas ich oceny.
Notację z przedrostkiem zaproponował w 1924 roku polski matematyk Jan Łukasiewicz , stąd też nazywana jest notacją Łukasiewicza , czyli notacją polską . Analogicznie, notacja postfixed nazywana jest odwrotną notacją polską . Te dwie notacje (z prefiksem i postfiksem) pozwalają zrezygnować z nawiasów w przypadku operatorów o ustalonej i znanej liczbie i zgodzić się na naturalną ocenę wyrażenia.
Wyrażenie, które dodaje liczby 1 i 2, jest zapisane w notacji z przedrostkiem + 1 2. W wyrażeniach z prefiksem operatory zawsze poprzedzają swoje operandy, które same mogą być nietrywialnymi wyrażeniami . Na przykład wyrażenie, które byłoby zapisane w klasycznej notacji wrostków:
(5 - 6) × 7jest zapisany w notacji z prefiksem:
× (- 5 6) 7Zauważ, że jak wiemy arity operatorów, nawiasy są konieczne i poprzedni wyrażenie można uprościć do:
× - 5 6 7Ocena iloczynu × jest aktywowana, gdy jego dwa argumenty zostały ocenione (tj. 5 - 6 i 7). Mówiąc bardziej ogólnie, ocena operatora arity n jest aktywowana po oszacowaniu jego n operandów.
Załóżmy, że mamy również funkcję arności 3 i trzech zmiennych , i . Wrostek wyrażenia należy wprowadzić z przedrostkiem, bez nawiasów . Pierwszy ma trzy argumenty, które są , i . W wyrażeniu , widzimy, że ma trzy argumenty , potem , potem . Korzystanie z baterii pozwala nawet człowiekowi analizować i oceniać te wyrażenia.
Przy obliczaniu zdań Łukasiewicz wprowadził :
na „nie” ; dla „i” ; zamiast „lub” ; za zaangażowanie ; dla równoważności .Na przykład :
odpowiada notacji wrostek odpowiada notacji wrostek . SeplenienieTe języki programowania Lisp i Scheme użyć notacji z przedrostkiem nawiasach, aby umożliwić operatorom zmiennej liczbie argumentów. Nawiasy otaczają operator i jego operandy.
W tej rodzinie języków występuje zwyczajowe wyrażenie 3 * (4 + 5 + 6) (* 3 (+ 4 5 6)).
Wyrażenie jest interpretowane poprzez sukcesywne zastępowanie wyrażenia w nawiasach wynikiem operatora zapisanego po lewej stronie, działającego na wartości operandów zapisanych po nim:
(* 3 (+ 4 5 6)) ⇒ (* 3 15) ⇒ 45.Języki programowania Forth , PostScript i RPL język z kalkulatorów HP użyć utrwalano notacji, które można zrobić bez nawiasów, podmioty posiadające stałą liczbę argumentów (dodawanie i mnożenie mają dwa operandy, odwrotna i korzeń kwadrat mają tylko jeden). Następnie zapisywane jest wyrażenie 3 * ((4 + 5) + 6) 3 4 5 add 6 add mul, natomiast zapisywane jest wyrażenie (4 + (5 + 6)) * 3 4 5 6 add add 3 mul. Kiedy interpreter napotyka operand, układa go w stos, dzięki czemu można go później zdjąć ze stosu. Kiedy napotyka operator binarny, zdejmuje dwa operandy, stosuje do nich operator i układa wynik w stos. Stos będzie więc miał kolejno następującą zawartość (znak ⇒ oddziela kolejne kroki, które następują po sobie w czasie):
(3) ⇒ (3 4) ⇒ (3 4 5) ⇒ dodaj ⇒ (3 9) ⇒ (3 9 6) ⇒ dodaj ⇒ (3 15) ⇒ mul ⇒ (45).Zapis wyrażenia 3 * (4 + 5 + 6) z prefiksem jest analogiczny do wyrażenia w języku naturalnym : „iloczyn 3 i sumy 4, 5 i 6”. Analogiem zapisu z postfixem w języku naturalnym 4 5 add 6 add 3 mulbyłoby: „weź 4 i 5 i dodaj je, weź wynik i 6 i dodaj je, a następnie weź tę sumę i pomnóż ją przez 3”.
Notacje postfixed (podobnie jak notacje wrostkowe) tworzą język formalny, którego słowa składają się z operatorów i zmiennych. Spośród wszystkich słów w tym alfabecie możemy scharakteryzować te, które odpowiadają zapisowi z prefiksem. Odbywa się to dzięki pojęciu wartościowości .