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 , 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())

cc-by-nc | code (python) | codechef | spoj

<<< Project Euler : solution au problème 18, en Python (2009-02-26) | The Geek Cred (2009-02-25) >>>