26/02/2009
CodeChef/SPOJ: solution au problème "ONP", en Python
Pour changer un peu des considérations mathématiques qui sous-tendent les problèmes de Project Euler, je m'attaque à ceux qui sont proposés chez Sphere Online Judge, dont certains sont repris tels quels chez CodeChef (la système de vérification de CodeChef est celui de SPOJ).
Je vous épargne le "TEST", intitulé "Life, the Universe and Everything", qui est un écho jusqu'à atteindre le sacro-saint quarante-deux.
Par contre "ONP", ou "Transform the Expression", énoncé ici et là, est un peu plus intéressant puisqu'il s'agit de transformer une expression arithmétique en notation infixe en la même expression mais en notation postfixe.
Mon programme est une implémentation du Shunting Yard Algorithm, du vénérable Edsger Dijkstra.
#! /usr/bin/env python
# 2009/02/26 - spoj0004.py
# Solution au Probleme 4 de SPOJ
# http://www.spoj.pl/problems/ONP/
# Jean Karim Bockstael - jkb@jkbockstael.be
operators = { '+' : 0,
'-' : 0,
'*' : 1,
'/' : 1,
'^' : 2, }
def infixtorpn(infixexp):
rpnexp = ""
opstack = []
for i in range(0, (len(infixexp) - 1)):
token = infixexp[i]
# Operands
if token >= 'a' and token <= 'z':
rpnexp = rpnexp + token
continue
# Operators
if token in operators:
while len(opstack) > 0 and \
opstack[-1] in operators and \
operators[opstack[-1]] > operators[token]:
rpnexp = rpnexp + opstack.pop()
opstack.append(token)
continue
# Parenthesis
if token == '(':
opstack.append(token)
continue
if token == ')':
while opstack[-1] != '(':
rpnexp = rpnexp + opstack.pop()
opstack.pop()
continue
# Pop remaining operators into output
while len(opstack) > 0 and opstack[-1] != '(':
rpnexp = rpnexp + opstack.pop()
return rpnexp
# Number of test cases
testcases = input()
# Process each testcase
for testcase in range(0, testcases):
print infixtorpn(raw_input())