La notation polonaise inverse est inventée dans les années 1950 par l'informaticien australien Charles Leonard Hamblin, afin de programmer des calculs en utilisant le moins de mémoire possible, à une époque où la RAM coûtait très cher. Elle s'inspire de la notation proposée par le Polonais Jan Lukasiewicz en 1924, mathématicien de son état. Si nous connaissons la notation polonaise inversée c'est généralement parce que ce type de notation mathématique a été utilisé par les calculatrices de la marque Hewlett-Packard (HP), fortement représentées sur le marché durant les années 1980-2000.

La notation polonaise inversée utilise grandement la pile informatique pour la mise en place des ses calculs, afin de simuler un arbre de calcul. Le principe est relativement simple : Les opérandes sont repoussées après les symboles des calculs. Ainsi, une opération du genre 5 x (4 + 2) peut être écrite sous la forme 5 4 2 + x. Ce type de notation fait disparaître la précédence des opérations les unes par rapport aux autres et conserve la priorité des opérations. Une expression arithmétique est donc évaluée à partir d'un arbre syntaxique, en remontant des feuilles (qui sont des nombres et n'ont donc pas besoin d'être évalués), vers la racine. Les noeuds intérieurs sont des opérateurs qui sont évalués dès que leurs deux opérandes (leurs deux fils), le sont.

Code snippet

import sys

def calcul_npi(expr):
    symbols = expr.split(' ')
    calcul = []
    done = False
    for s in symbols:
        if s.isnumeric():
            calcul.append(s)
        else:
            a = int(calcul.pop())
            b = int(calcul.pop())
            op = s

            if op in ['+', '-', '*', '/']:
                if op == '+':
                    v = b + a
                elif op == '-':
                    v = b - a
                elif op == '*':
                    v = b * a
                elif op == '/':
                    v = b / a
                else:
                    print("OP Error. Quitting.")
                    sys.exit()
                calcul.append(v)
            else:
                print("Error. Quitting.")
                sys.exit()
    return(calcul)


x = calcul_npi("4 1 2 + * 3 -")
print(f"4 1 2 + * 3 -  --> {x}")

x = calcul_npi("1 2 3 4 5 6 7 8 9 10 - + / + + * - + +")
print(f"1 2 3 4 5 6 7 8 9 10 - + / + + * - + +  --> {x}")