As notações infix (ou infix ), prefix (ou prefix ) e postfix (ou postfix ) são formas de escrita de expressões algébricas que se distinguem pela posição relativa assumida pelos operadores e seus operandos . Um operador é escrito antes de seus operandos em notação pré-fixada, entre seus operandos em notação pré-fixada e depois de seus operandos em notação pós-fixada.
A notação infixa só faz sentido para operadores que usam exatamente dois operandos. Esta é a notação mais comum para operadores binários em matemática. As notações prefixadas e pós-fixadas permitem dispensar os parênteses, resultando em uma notação mais compacta. Mas dispensar parênteses supõe que conheçamos a assinatura (em outras palavras, a aridade de todos os operadores) e que essa aridade é um atributo dos operadores que não pode ser modificável. A assinatura é usada para analisar expressões durante sua avaliação.
A notação prefixada foi proposta em 1924 pelo matemático polonês Jan Łukasiewicz , razão pela qual também é chamada de notação Łukasiewicz , ou notação polonesa . Por analogia, a notação pós-fixada é chamada de notação polonesa reversa . Essas duas notações (prefixadas e pós-fixadas) permitem dispensar os parênteses no caso de operadores de aridade fixa e conhecida e concordam com uma avaliação natural da expressão.
A expressão que adiciona os números 1 e 2 é escrita, em notação prefixada, + 1 2. Em expressões prefixadas, os operadores sempre precedem seus operandos, que podem ser expressões não triviais. Por exemplo, a expressão que seria escrita em notação de infixo clássico:
(5 - 6) × 7é escrito em notação prefixada:
× (- 5 6) 7Observe que, como sabemos a aridade dos operadores, os parênteses são desnecessários e a expressão anterior pode ser simplificada para:
× - 5 6 7A avaliação do produto × é ativada quando seus dois operandos forem avaliados (a saber, 5 - 6 e 7). De modo mais geral, a avaliação de um operador de aridade n é ativada após seus n operandos terem sido avaliados.
Suponha que também tenhamos uma função de aridade 3 e três variáveis , e . A expressão infixo deve ser inserida com o prefixo, sem parênteses . O primeiro tem três argumentos que são , e . Na expressão , vemos que tem três argumentos , então , então . Usar uma bateria permite que até mesmo um ser humano analise e avalie essas expressões.
Ao calcular proposições , Łukasiewicz introduziu :
para o "não" ; para o "e" ; para o "ou" ; para envolvimento ; para equivalência .Por exemplo :
corresponde à notação infixa corresponde à notação infixada . LispAs linguagens de programação Lisp e Scheme usam uma notação prefixada com parênteses, para permitir operadores com um número variável de operandos. Os parênteses envolvem um operador e seus operandos.
A expressão usual 3 * (4 + 5 + 6) é observada nesta família de línguas (* 3 (+ 4 5 6)).
A expressão é interpretada substituindo sucessivamente uma expressão entre parênteses pelo resultado do operador escrito à esquerda agindo sobre os valores dos operandos escritos depois dela:
(* 3 (+ 4 5 6)) ⇒ (* 3 15) ⇒ 45.As linguagens de programação Forth , PostScript e a linguagem RPL das calculadoras HP utilizam uma notação pós-fixada que dispensa parênteses, operadores com número fixo de operandos (adição e multiplicação possuem dois operandos, o reverso e a raiz quadrada possuem apenas um). A expressão 3 * ((4 + 5) + 6) é então escrita 3 4 5 add 6 add mul, enquanto a expressão (4 + (5 + 6)) * 3 é escrita 4 5 6 add add 3 mul. Quando o interpretador encontra um operando, ele o empilha em uma pilha, para que possa ser desempilhado da pilha posteriormente. Ao encontrar um operador binário, ele exibe dois operandos, aplica o operador a eles e empilha o resultado. A pilha terá, portanto, sucessivamente o seguinte conteúdo (o sinal ⇒ separa as etapas que se sucedem no tempo):
(3) ⇒ (3 4) ⇒ (3 4 5) ⇒ adicionar ⇒ (3 9) ⇒ (3 9 6) ⇒ adicionar ⇒ (3 15) ⇒ mul ⇒ (45).A notação prefixada da expressão 3 * (4 + 5 + 6) é análoga à expressão da linguagem natural : "o produto de 3 e a soma de 4, 5 e 6". O análogo da linguagem natural da notação pós-fixada 4 5 add 6 add 3 mulseria: "pegue 4 e 5 e some-os, pegue o resultado e 6 e some-os então pegue essa soma e multiplique-a por 3".
Notações pós-fixadas (como notações infixadas) formam uma linguagem formal cujas palavras são compostas de operadores e variáveis. Podemos caracterizar entre todas as palavras deste alfabeto aquelas que correspondem a uma notação prefixada. Isso é feito graças à noção de valência .