Informasjonene om infiks (eller infiks ), prefiks (eller prefiks ) og postfiks (eller postfiks ) er former for skriving av algebraiske uttrykk som kjennetegnes av den relative posisjonen operatørene og deres operander tar . En operatør skrives før operandene i prefiksnotasjon, mellom operandene i infiksert notasjon, og etter operandene i postfiksert notasjon.
Infiks-notasjonen er bare fornuftig for operatører som tar nøyaktig to operander. Dette er den vanligste notasjonen for binære operatører i matematikk. De prefiksede og postfixerte notasjonene gjør det mulig å dispensere med parenteser, noe som fører til en mer kompakt notasjon. Men å gjøre uten parentes antar at vi kjenner signaturen (med andre ord ariteten til alle operatørene) og at denne ariteten er et attributt til operatørene som ikke kan modifiseres. Signaturen brukes til å analysere uttrykk under evalueringen.
Den prefikse notasjonen ble foreslått i 1924 av den polske matematikeren Jan Łukasiewicz , og det er derfor den også kalles calledukasiewicz- notasjon , eller polsk notasjon . Analogt kalles den postfixerte notasjonen omvendt polsk notasjon . Disse to notasjonene (prefiks og postfixed) gjør det mulig å dispensere med parenteser når det gjelder operatører av fast og kjent arity og godtar en naturlig vurdering av uttrykket.
Uttrykket som legger til tallene 1 og 2 er skrevet, i prefiksnotasjon, + 1 2. I prefiksuttrykk går operatørene alltid foran operandene sine som selv kan være ikke-trivielle uttrykk . For eksempel uttrykket som ville bli skrevet i klassisk infiksnotasjon:
(5 - 6) × 7er skrevet i prefiksnotasjon:
× (- 5 6) 7Legg merke til at som kjent arity av operatorer, er parenteser unødvendige, og det forrige uttrykket kan forenkles til:
× - 5 6 7Evalueringen av produktet × aktiveres når de to operandene har blitt evaluert (dvs. 5-6 og 7). Mer generelt aktiveres evalueringen av en operatør av arity n etter at dens n operander er evaluert.
Anta at vi også har en funksjon av arity 3 og tre variabler , og . Uttrykket infiks legges inn fra prefikset, uten parentes . Den første har tre argumenter som er , og . I uttrykket ser vi at har tre argumenter , da , da . Ved å bruke et batteri kan selv et menneske analysere og evaluere disse uttrykkene.
Ved beregning av proposisjoner introduserte Łukasiewicz :
for "nei" ; for "og" ; for "eller" ; for involvering ; for ekvivalens .For eksempel :
tilsvarer infiks-notasjonen tilsvarer infiks-notasjonen . LispDe programmeringsspråk Lisp og Scheme bruker en notasjon prefiks parentes, for å tillate operatører med et variabelt antall operander. Parenteser omgir en operatør og dens operander.
Det vanlige uttrykket 3 * (4 + 5 + 6) er notert i denne språkfamilien (* 3 (+ 4 5 6)).
Uttrykket tolkes ved å erstatte et uttrykk i parentes suksessivt med resultatet av operatøren som er skrevet til venstre og virker på verdiene til operandene skrevet etter det:
(* 3 (+ 4 5 6)) ⇒ (* 3 15) ⇒ 45.Programmeringsspråkene Forth , PostScript og RPL- språket til HP-kalkulatorer bruker en postfiksert notasjon som kan klare seg uten parenteser, operatørene har et fast antall operander (tillegg og multiplikasjon har to operander, det motsatte og rotfeltet har bare en). Uttrykket 3 * ((4 + 5) + 6) skrives deretter 3 4 5 add 6 add mul, mens uttrykket (4 + (5 + 6)) * 3 skrives 4 5 6 add add 3 mul. Når tolk møter en operand, stabler den den i en bunke, slik at den kan fjernes fra bunken senere. Når den møter en binær operator, spretter den to operander, bruker operatøren på dem og stabler resultatet. Stakken vil derfor suksessivt ha følgende innhold (⇒-tegnet skiller trinnene som følger hverandre i tide):
(3) ⇒ (3 4) ⇒ (3 4 5) ⇒ tilsett ⇒ (3 9) ⇒ (3 9 6) ⇒ tilsett ⇒ (3 15) ⇒ mul ⇒ (45).Den prefikse notasjonen av uttrykket 3 * (4 + 5 + 6) er analog med det naturlige språkuttrykket : "produktet av 3 og summen av 4, 5 og 6". Den naturlige språkanalogen til den postfixerte notasjonen 4 5 add 6 add 3 mulville være: "ta 4 og 5 og legg dem til, ta resultatet og 6 og legg dem sammen, og ta deretter denne summen og multipliser den med 3".
Postfixerte notasjoner (som infixed notations) danner et formelt språk hvis ord består av operatorer og variabler. Vi kan karakterisere blant alle ordene i dette alfabetet de som tilsvarer en prefiksnotasjon. Dette gjøres takket være forestillingen om valens .