theClimber

La notation polonaise inverse (NPI) (en anglais RPN pour Reverse Polish Notation), également connue sous le nom de notation post-fixée, permet de noter les formules arithmétiques sans utiliser de parenthèses. Dérivée de la notation polonaise présentée en 1920 par le mathématicien polonais Jan Łukasiewicz, elle s’en différencie par l’ordre des termes : les opérandes y sont présentés avant les opérateurs et non l’inverse.

Cette notation est en fait très proche de celle utilisée dans le calcul écrit.

Par exemple, l’expression « 3 × (4 + 7) » peut s'écrire en NPI sous la forme « 4 7 + 3 × », ou encore sous la forme « 3 4 7 + × ».

C'est dans le cadre d'un entretien en entreprise en septembre dernier, on m'a demandé en une petite heure d'écrire un programme permettant de faire ce genre d'opérations. Un peu stressant au début (car quand on a un entretien il s'agit de faire bonne impression), mais finalement ça s'est bien passé.

#!/usr/bin/python
import sys, math

operations = ['sqrt', '+', '-', '*', '/', '^']
stack = []
op_list = sys.argv[1:]

print op_list
for val in op_list:
	if val in operations:
		if val == 'sqrt':
			x = stack.pop()
			stack.append(math.sqrt(x))
		elif val == '^':
			x = stack.pop()
			y = stack.pop()
			stack.append(math.pow(y, x))
		elif val == '+':
			x = stack.pop()
			y = stack.pop()
			stack.append(y + x)
		else:
			x = stack.pop()
			y = stack.pop()
			print "operation : %s %s %s" % (y, val, x)
			stack.append(eval("%s %s %s" % (y, val, x)))
	else:
		stack.append(float(val))
		print stack

print stack

Qu'est-ce qu'une calculette RPN (http://en.wikipedia.org/wiki/Reverse_Polish_notation) ? Il s'agit d'une calculette qui récupère les arguments dans l'ordre d'une pile. C'est ce qui était implémenté initialement sur les anciennes calculettes HP pour ceux qui les ont encore connues.

C'était donc le petit script "histoire de l'informatique" de la semaine