Conversor de notação polonesa

A notação polonesa é uma forma de escrever expressões matemáticas e lógicas sem depender da posição habitual dos operadores entre os valores. Na notação infixa comum, o operador aparece entre seus operandos, como em A + B. A notação prefixa o coloca primeiro, formando + A B; a pós-fixa o coloca no final, formando A B +. A forma prefixa costuma ser chamada de notação polonesa, e a pós-fixa, de notação polonesa reversa ou RPN. Como a ordem do operador e dos operandos é inequívoca, essas expressões geralmente dispensam parênteses. Este conversor faz quatro transformações comuns: infixa para prefixa, infixa para pós-fixa, prefixa para infixa e pós-fixa para infixa. Na entrada infixa, reconhece identificadores, números decimais, parênteses e operadores de adição, subtração, multiplicação, divisão e potência. Aplica as regras padrão de precedência: potências primeiro, depois multiplicações e divisões, por fim adições e subtrações. Parênteses podem alterar a ordem. A potência é associativa à direita, portanto a ^ b ^ c significa a ^ (b ^ c). As conversões a partir da notação infixa usam o algoritmo shunting-yard para ordenar os tokens por precedência. Uma pilha guarda temporariamente os operadores enquanto os valores vão direto para a saída. A saída prefixa é então montada a partir da sequência pós-fixa gerada. As conversões de prefixa ou pós-fixa para infixa usam uma pilha de expressões parciais. Ao encontrar um operador, os dois operandos correspondentes são retirados, combinados, envolvidos em parênteses e devolvidos à pilha. O último item é a expressão infixa completa. Os espaços importam na entrada prefixa e pós-fixa porque identificam cada operando e operador. Escreva * + A B C em vez de *+ABC. Expressões infixas podem ter ou não espaços, pois parênteses e caracteres de operadores separam os tokens. O conversor preserva nomes de variáveis e valores numéricos, mas acrescenta espaços e parênteses para facilitar a conferência. A conversão de notação é útil no estudo de árvores de expressão, análise sintática de compiladores, máquinas de pilha, calculadoras e estruturas de dados. Expressões pós-fixas podem ser avaliadas da esquerda para a direita com uma pilha simples, enquanto as prefixas podem ser processadas de forma semelhante da direita para a esquerda. Converter uma fórmula infixa conhecida torna a precedência explícita e ajuda a conferir exercícios de análise de expressões.