Notação polonesa reversa

Notação polonesa reversa (RPN), também conhecida como notação Łukasiewicz reversa, notação pós-fixada polonesa ou simplesmente notação pós-fixada, é uma notação matemática na qual os operadores seguem seus operandos, em contraste com o prefixo ou a notação polonesa (PN), na qual os operadores precedem seus operandos. A notação não precisa de parênteses desde que cada operador tenha um número fixo de operandos.

O termo notação pós-fixada descreve o esquema geral em matemática e ciências da computação, enquanto o termo notação polonesa reversa normalmente se refere especificamente à notação usada para inserir cálculos em hardware ou calculadoras de software, que muitas vezes têm efeitos colaterais e implicações adicionais, dependendo da implementação real. A descrição "Polonês" refere-se à nacionalidade do lógico Jan Łukasiewicz, que inventou a notação polonesa em 1924.

O primeiro computador a usar notação pós-fixada, embora tenha permanecido essencialmente desconhecido fora da Alemanha, foi o Z3 de Konrad Zuse em 1941, bem como seu Z4 em 1945. O esquema polonês reverso foi novamente proposto em 1954 por Arthur Burks, Don Warren e Jesse Wright e foi reinventado de forma independente por Friedrich L. Bauer e Edsger W. Dijkstra no início dos anos 1960 para reduzir o acesso à memória do computador e usar a pilha para avaliar expressões. Os algoritmos e a notação deste esquema foram estendidos pelo filósofo e cientista da computação australiano Charles L. Hamblin em meados da década de 1950.

Durante as décadas de 1970 e 1980, a Hewlett-Packard usou RPN em todas as suas calculadoras de mesa e portáteis, e continuou a usá-lo em alguns modelos até a década de 2020. Na ciência da computação, a notação polonesa reversa é usada em linguagens de programação orientadas a pilha, como Forth, STOIC, PostScript, RPL e Joy.

Explicação

Na notação polonesa reversa, os operadores seguem seus operandos. Por exemplo, para somar 3 e 4, a expressão é 3 4 + em vez de 3 + 4. A expressão 3 − 4 + 5 em notação convencional é 3 4 − 5 + em notação polonesa reversa: 4 é primeiro subtraído de 3, então 5 é adicionado a ele.

O conceito de uma pilha, uma construção último a entrar/primeiro a sair, é parte integrante da avaliação da esquerda para a direita do RPN. No exemplo 3 4 −, primeiro o 3 é colocado na pilha, depois o 4; o 4 está agora em cima e o 3 abaixo dele. O operador de subtração remove os dois primeiros itens da pilha, executa 3 − 4 e coloca o resultado de −1 na pilha.

A terminologia comum é que os itens adicionados são colocados na pilha e os itens removidos são removidos.

A vantagem da notação polonesa reversa é que ela elimina a necessidade de ordem de operações e parênteses exigidos pela notação infixa e pode ser avaliada linearmente, da esquerda para a direita. Por exemplo, a expressão infixa (3 × 4) + (5 × 6) torna-se 3 4 × 5 6 × + em notação polonesa reversa.

Implicações práticas

A notação polonesa reversa foi comparada à forma como alguém tinha que resolver problemas com uma régua de cálculo.

Em testes de comparação da notação polonesa reversa com a notação algébrica, descobriu-se que o polonês reverso leva a cálculos mais rápidos, por dois motivos. A primeira razão é que as calculadoras polonesas reversas não precisam que as expressões sejam colocadas entre parênteses, portanto, menos operações precisam ser inseridas para realizar cálculos típicos. Além disso, os usuários de calculadoras reversas polonesas cometeram menos erros do que outros tipos de calculadoras. Pesquisas posteriores esclareceram que o aumento da velocidade da notação polonesa reversa pode ser atribuído ao menor número de pressionamentos de tecla necessários para inserir essa notação, e não a uma menor carga cognitiva de seus usuários. No entanto, evidências anedóticas sugerem que a notação polonesa reversa é mais difícil para usuários que aprenderam anteriormente a notação algébrica.

Convertendo da notação infixa

Edsger W. Dijkstra inventou o algoritmo de pátio de manobras para converter expressões infixas em expressões pós-fixadas (notação polonesa reversa), assim chamado porque sua operação se assemelha à de um pátio de manobras ferroviárias.

Existem outras maneiras de produzir expressões pós-fixadas a partir de expressões infixas. A maioria dos analisadores de precedência de operador podem ser modificados para produzir expressões pós-fixadas; em particular, uma vez construída uma árvore sintática abstrata, a expressão pós-fixada correspondente é dada por um simples percurso pós-ordem dessa árvore.

Implementações

Calculadoras de hardware

História antiga

O primeiro computador a implementar uma forma de notação polonesa reversa (mas sem o nome), foi o Z3 de Konrad Zuse, que ele começou a construir em 1938 e demonstrou publicamente em 12 de maio de 1941. Em modo de diálogo, permitia operadores para inserir dois operandos seguidos pela operação desejada. Foi destruído em 21 de dezembro de 1943 em um bombardeio. Com a ajuda de Zuse, uma primeira réplica foi construída em 1961. O Z4 1945 também adicionou uma pilha.

Outros primeiros computadores a implementar arquiteturas que permitiam a notação polonesa reversa foram a máquina KDF9 da English Electric Company, que foi anunciada em 1960 e disponível comercialmente em 1963, e o Burroughs B5000, anunciado em 1961 e também entregue em 1963:

Presumivelmente, os designers do KDF9 extraíram ideias do GEORGE (General Order Generator) de Hamblin, um sistema de programação de autocódigo escrito para um computador DEUCE instalado na Universidade de Sydney, Austrália, em 1957.

Um dos designers do B5000, Robert S. Barton, escreveu mais tarde que desenvolveu a notação polonesa reversa independentemente de Hamblin em algum momento de 1958, depois de ler um livro de 1954 sobre lógica simbólica de Irving Copi, onde encontrou uma referência à notação polonesa., o que o fez ler também as obras de Jan Łukasiewicz, e antes de conhecer a obra de Hamblin.

Friden introduziu a notação polonesa reversa no mercado de calculadoras de mesa com a EC-130, projetada por Robert "Bob" Appleby Ragen, suportando uma pilha de quatro níveis em junho de 1963. O sucessor EC-132 adicionou uma função de raiz quadrada em abril de 1965. Por volta de 1966, a calculadora Monroe Epic também suportava um esquema de entrada sem nome semelhante a RPN.

Hewlett-Packard

Os engenheiros da Hewlett-Packard projetaram a calculadora de mesa 9100A em 1968 com notação polonesa reversa com apenas três níveis de pilha com registros funcionais X ("teclado"), Y ("acumular") e registro de armazenamento visível Z ("temporário& #34;), uma variante da notação polonesa reversa mais tarde referida como RPN de três níveis. Esta calculadora popularizou a notação polonesa reversa entre as comunidades científicas e de engenharia. A HP-35, a primeira calculadora científica portátil do mundo, introduziu o clássico RPN de quatro níveis com seu conjunto de regras específico da chamada pilha operacional (memória) (mais tarde também chamada de pilha de memória automática) em 1972. Neste esquema, a chave Enter ↑ duplica os valores em Y em certas condições (elevação automática de pilha com desativação temporária de elevação de pilha), e o registro superior T ("top") obtém duplicado em drops (cópia superior no pop também conhecido como repetição no nível da pilha superior) para facilitar alguns cálculos e economizar pressionamentos de tecla. A HP usava a notação polonesa reversa em todas as calculadoras portáteis que vendia, fossem científicas, financeiras ou programáveis, até lançar a calculadora para máquina de somar HP-10 em 1977. Nessa época, a HP era o fabricante líder de calculadoras para profissionais, incluindo engenheiros e contadores.

Calculadoras posteriores com telas LCD do início da década de 1980, como HP-10C, HP-11C, HP-15C, HP-16C e a calculadora financeira HP-12C, também usavam notação polonesa reversa. Em 1988, a Hewlett-Packard introduziu uma calculadora comercial, a HP-19B, sem notação polonesa reversa, mas seu sucessor de 1990, a HP-19BII, deu aos usuários a opção de usar novamente a notação polonesa algébrica ou reversa.

Por volta de 1987, a HP lançou o RPL, um sucessor orientado a objetos da notação polonesa reversa. Ele se desvia da notação polonesa reversa clássica ao usar uma pilha dinâmica limitada apenas pela quantidade de memória disponível (em vez de três ou quatro níveis fixos) e que pode conter todos os tipos de objetos de dados (incluindo símbolos, strings, listas, matrizes, gráficos, programas, etc.) em vez de apenas números. O sistema exibiria uma mensagem de erro ao ficar sem memória, em vez de apenas descartar valores da pilha no estouro, como acontece com pilhas de tamanho fixo. Também mudou o comportamento da pilha para não duplicar mais o registro superior em quedas (já que em uma pilha ilimitada não há mais um registro superior) e o comportamento do Enter ↑ para que não duplique mais valores em Y, o que às vezes causa confusão entre usuários não familiarizados com as propriedades específicas da pilha de memória automática. De 1990 a 2003, a HP fabricou a série HP-48 de calculadoras gráficas RPL e, em 2006, lançou a HP 50g.

A partir de 2011, a Hewlett-Packard oferecia os modelos de calculadora 12C, 12C Platinum, 17bII+, 20b, 30b, 33s, 35s, 48gII (RPL) e 50g (RPL) que suportam notação polonesa reversa. Embora as calculadoras que emulam modelos clássicos continuem a oferecer suporte à notação polonesa reversa clássica, os novos modelos de notação polonesa reversa apresentam uma variante da notação polonesa reversa, onde Enter ↑ se comporta como em RPL. Esta última variante às vezes é conhecida como RPN de entrada. Em 2013, o HP Prime introduziu um 128 níveis forma de entrada RPN chamada RPN avançado. Como acontece com outras pilhas de tamanho fixo, ele apenas elimina valores da pilha no estouro. No final de 2017, a lista de modelos ativos com suporte à notação polonesa reversa incluía apenas 12C, 12C Platinum, 17bii+, 35s e Prime. Em 1º de novembro de 2021, Moravia Consulting spol. s r.o. (para todos os mercados, exceto as Américas) e Royal Consumer Information Products, Inc. (para as Américas) tornaram-se os licenciados da HP Development Company, L.P. para continuar o desenvolvimento, produção, distribuição, marketing e suporte de calculadoras da marca HP. Em julho de 2023, apenas o 12C, o 12C Platinum, o recém-lançado HP 15C Collector's Edition e o Prime permanecem modelos ativos com suporte para RPN.

Radiônica Sinclair

In Britain, Clive Sinclair 's Sinclair Scientific (1974) and Scientific Programmable (1975) models used reverse Polish notation.

Comodoro

Em 1974, a Commodore produziu o Minuteman *6 (MM6) sem uma tecla enter e o Minuteman *6X (MM6X) com uma tecla enter , ambas implementando uma forma de RPN de dois níveis. O RPN SR4921 veio com uma variante de RPN de quatro níveis com níveis de pilha chamados X, Y, Z e W (em vez de T) e um Ent Tecla (para "entrada"). Em contraste com a implementação da notação polonesa reversa da Hewlett-Packard, W preenchido com 0 em vez de seu conteúdo ser duplicado nas quedas da pilha.

Prinztronic

Prinz e Prinztronic eram nomes comerciais de marca própria da rede de varejo de lojas de produtos eletrônicos e fotográficos britânica Dixons, mais tarde rebatizada como lojas Currys Digital, e tornaram-se parte da DSG. Internacional. Uma variedade de modelos de calculadoras foram vendidos na década de 1970 sob a marca Prinztronic, todos fabricados para eles por outras empresas.

Entre eles estava a Calculadora Científica Programável PROGRAM, que apresentava notação polonesa reversa.

Kit de saúde

O computador de navegação de aeronaves Heathkit OC-1401/OCW-1401 usou RPN de cinco níveis em 1978.

União Soviética

As calculadoras programáveis soviéticas (modelos MK-52, MK-61, B3-34 e modelos anteriores B3-21) usavam notação polonesa reversa tanto para o modo automático quanto para a programação. As calculadoras russas modernas MK-161 e MK-152, projetadas e fabricadas em Novosibirsk desde 2007 e oferecidas pela Semico, são compatíveis com versões anteriores. Sua arquitetura estendida também é baseada na notação polonesa reversa.

Outros

• Uma pilha de sete níveis foi implementada na calculadora científica MITS 7400C em 1972
• Calculadoras vírgulas
• SwissMicros (originalmente como RPN-Calc) calculadoras desde 2011
• Algumas calculadoras APF também podem usar RPN

Calculadoras baseadas em hardware desenvolvidas pela comunidade

Uma pilha de oito níveis foi sugerida por John A. Ball em 1978.

As calculadoras desenvolvidas pela comunidade WP 34S (2011), WP 31S (2014) e WP 34C (2015), que são baseadas na plataforma de hardware HP 20b/HP 30b, suportam notação polonesa reversa clássica no estilo Hewlett-Packard comutável com uma pilha de quatro ou oito níveis.

Além do suporte opcional para uma pilha de oito níveis, os novos derivados WP 43S baseados em DM42 da SwissMicros, bem como os derivados WP 43C (2019) /C43 (2022) /C47 (2023) suportam tipos de dados para objetos de pilha (números reais, inteiros infinitos, inteiros finitos, números complexos, strings, matrizes, datas e horas). Os últimos três modelos também podem ser alternados entre o comportamento clássico e RPN de entrada do Enter ↑, um recurso frequentemente solicitado pela comunidade. Eles também suportam um modo de números significativos raramente visto, que já estava disponível como uma opção de tempo de compilação para o WP 34S e WP 31S.

Desde 2021, o simulador HP-42S Free42 versão 3 (também conhecido como Plus42 versão 1) pode ser habilitado para suportar uma pilha RPN dinâmica limitada apenas pela quantidade de memória disponível, em vez da pilha clássica de 4 níveis. Este recurso foi incorporado como uma função selecionável no DM42 desde o firmware DMCP-3.21 /DM42-3.18.

Calculadoras de software

Calculadoras de software:

• Calculadora Mac OS X
• Vários aplicativos Apple iPhone, por exemplo, "reversa calculadora de notação de polonês"
• Vários aplicativos Android, por exemplo, "RealCalc"
• Vários aplicativos móveis do Windows 10, por exemplo, "RPN9"
• Programa de calculadora do sistema Unix dc
• Emacs lisp biblioteca pacote calc
• Xorg calculadora (xcalc)
• ARPCalc, uma poderosa calculadora científica / engenharia RPN para Windows, Linux e Android que também tem uma versão baseada em web-browser
• grpn calculadora científica / engenharia usando o kit de ferramentas GIMP (GTK+)
• F-Correlatives in Multi Valor itens de dicionário
• RRDtool, um software de tabulação e grafos amplamente utilizado
• grdmath, um programa para operações algébricas em grades NetCDF, parte da suíte Genérico Mapping Tools (GMT)
• galculador, uma calculadora de desktop GTK
• Mouseless Stack-Calculator calculadora científica / engenharia, incluindo números complexos
• rpCalc, uma calculadora de notação reversa simples escrita em Python para Linux e MS Windows e publicada sob a licença GNU GPLv2
• orpie, calculadora RPN para o terminal para números reais ou complexos ou matrizes
• Qalculate!, uma calculadora de desktop multiplataforma poderosa e versátil

Linguagens de programação

As implementações existentes que usam a notação polonesa reversa incluem:

• Linguagens de programação orientadas para pilhas como:
  • Forth
  • STOIC
  • Factor
  • PostScript page description language
  • BibTex
  • Diverte-te.
  • Alegria.
  • IPTSCRAE
  • Lotus 1-2-3 e Lotus Symphony fórmulas
  • RPL (aka Reverse Polish Language), uma linguagem de programação para o PET do Commodore em torno de 1979/1981
  • RPL (aka Reverse Polish Lisp), uma linguagem de programação para calculadoras Hewlett-Packard entre 1984 e 2015
  • RPNL (Reverse Polish Notation Language)
• Bibliotecas de classe
  • TRURL, uma biblioteca de classe para a construção de calculadoras RPN em Object Pascal