De infixede (eller infix ), prefixede (eller prefix ) og postfixede (eller postfixede ) notationer er former for skrivning af algebraiske udtryk, der er kendetegnet ved den relative position, som operatørerne og deres operander indtager . En operatør skrives før sine operander i præfikset notation, mellem dens operander i infixed notation og efter dens operander i postfixed notation.
Infix-notationen giver kun mening for operatører, der tager nøjagtigt to operander. Dette er den mest almindelige notation for binære operatører i matematik. De præfikset og postfixerede notationer gør det muligt at undlade parenteser, hvilket fører til en mere kompakt notation. Men for at gøre uden parentes forudsætter, at vi kender signaturen (med andre ord den arity af alle operatører), og at denne arity er en egenskab ved de operatører, som ikke kan være modificerbare. Signaturen bruges til at analysere udtryk under deres evaluering.
Den forudgående notation blev foreslået i 1924 af den polske matematiker Jan Łukasiewicz , hvorfor det også kaldes Łukasiewicz notation eller polsk notation . Analogt kaldes den postfixerede notation omvendt polsk notation . Disse to notationer (præfiks og postfixed) gør det muligt at undlade parenteser i tilfælde af operatører af fast og kendt aritet og accepterer en naturlig vurdering af udtrykket.
Udtrykket, der tilføjer tallene 1 og 2, skrives i præfiksnotation, + 1 2. I præfikserede udtryk går operatorerne altid foran deres operander, som selv kan være ikke-trivielle udtryk . For eksempel det udtryk, der ville blive skrevet i klassisk infix-notation:
(5 - 6) × 7er skrevet i præfiksnotation:
× (- 5 6) 7Bemærk, at som vi kender operatorernes aritet , er parenteser unødvendige, og det tidligere udtryk kan forenkles til:
× - 5 6 7Evalueringen af produktet × aktiveres, når dets to operander er blevet evalueret (dvs. 5-6 og 7). Mere generelt aktiveres evalueringen af en operatør af arity n, efter at dens n operander er blevet evalueret.
Antag, at vi også har en funktion af arity 3 og tre variabler , og . Udtrykket infix indtastes fra præfikset uden parentes . Den første har tre argumenter, som er , og . I udtrykket ser vi, at der har tre argumenter , så derefter . Brug af et batteri giver selv et menneske mulighed for at analysere og evaluere disse udtryk.
Ved beregning af propositioner introducerede Łukasiewicz :
for "nej" ; for "og" ; for "eller" ; for involvering ; for ækvivalens .For eksempel :
svarer til infix-notationen svarer til den infixede notation . LispDe programmeringssprog Lisp og Scheme bruge en notation præfikset parenteser, at give operatører med et variabelt antal operander. Parenteser omgiver en operatør og dens operander.
Det sædvanlige udtryk 3 * (4 + 5 + 6) er noteret i denne sprogfamilie (* 3 (+ 4 5 6)).
Udtrykket fortolkes ved successivt at erstatte et udtryk i parentes med resultatet af operatøren skrevet til venstre, der handler på værdierne for operanderne skrevet efter det:
(* 3 (+ 4 5 6)) ⇒ (* 3 15) ⇒ 45.Programmeringssprogene Forth , PostScript og RPL- sproget i HP-regnemaskiner bruger en postfixeret notation, der kan dispensere med parenteser, operatører har et fast antal operander (tilføjelse og multiplikation har to operander, det omvendte og rodfeltet har kun en). Udtrykket 3 * ((4 + 5) + 6) skrives derefter 3 4 5 add 6 add mul, mens udtrykket (4 + (5 + 6)) * 3 skrives 4 5 6 add add 3 mul. Når tolken støder på en operand, stabler den den i en stak, så den senere kan stables fra stakken. Når den møder en binær operator, popper den to operander, anvender operatøren på dem og stabler resultatet. Stakken vil derfor successivt have følgende indhold (⇒-tegnet adskiller de successive trin i tiden):
(3) ⇒ (3 4) ⇒ (3 4 5) ⇒ tilføj ⇒ (3 9) ⇒ (3 9 6) ⇒ tilføj ⇒ (3 15) ⇒ mul ⇒ (45).Den forudgående notation af udtrykket 3 * (4 + 5 + 6) er analog med det naturlige sproglige udtryk : "produktet af 3 og summen af 4, 5 og 6". Den naturlige sproganalog af den postfixede notation 4 5 add 6 add 3 mulville være: "tag 4 og 5 og tilføj dem sammen, tag resultatet og 6 og læg dem sammen, tag derefter denne sum og gang den med 3".
Postfixerede notationer (som infixed notations) danner et formelt sprog, hvis ord består af operatorer og variabler. Vi kan karakterisere dem blandt alle ordene i dette alfabet, der svarer til en præfiksnotation. Dette gøres takket være forestillingen om valens .