Optimization quirks

[TFK1]

While trying to CMEXPR (#10), I have code #1, which finished in just under 10 seconds and was accepted. But, it is ugly, and surely more efficient implementations of my approach exist. Then I have code #2, which is code #1 improved, but it doesn't offer any performance boost.

The problem is that in the second example I tried doing optimizations, which involved (mostly) creating a hash rule-table (instead of checking the parentheses' environment over and over again...). I expected it to run faster, but it didn't. But, shouldn't the hash table approach be faster, since less computations are involved? Is the hash(some_tuple)-into-a-dictionary technique worth it?

Code #1

import psyco
psyco.full()
OPERATIONS = "+-*/"
def getOpProperty(exp, i1, i2):
    property = 'n' # for "No property"
    prnths = 0
    while i1 < i2:
        # Ugly loop
        t = exp[i1]
        if t in OPERATIONS and not prnths:
            if t == '-':
                return '-'
            elif t == '+':
                property = '+'
            elif property == 'n':
                property = '*'
        elif t == '(':
            prnths += 1
        elif t == ')':
            prnths -= 1
        i1 += 1
    return property
def cleanParentheses(exp):
    open_prnths = [] # The stack of open parentheses' indices
    i = 0
exp_len = len(exp)
while i < exp_len:
    token = exp[i]
    if token == '(':
        open_prnths.append(i)
    elif token == ')':
        # Now the interesting stuff begins
        prnths_start = open_prnths.pop()
        # Set the pre and post parentheses operations
        # 'n' marks a "not defined" operation, i.e., no operation at all
        try:
            left_op = exp[prnths_start - 1]
        except IndexError:
            left_op = 'n'
        try:
            right_op = exp[i+1]
        except IndexError:
            right_op = 'n'
        # Get the internal property
        inside = getOpProperty(exp, prnths_start+1, i)
        # Start the checking
        if inside == 'n' or \ 
           ((inside == '*' and left_op != '/') or \
            ((left_op !=  '*' and left_op != '-' and left_op != '/') and \
             (right_op != '*' and right_op != '/'))):
            #  A horrible, ugly rule set
            del exp[i]
            del exp[prnths_start]
            exp_len -= 2
            i -= 2
    i += 1

return exp
if __name__ == "__main__":
    for i in xrange(int(raw_input())):
        print "".join(cleanParentheses(list(raw_input())))

Code #2

import psyco
psyco.full()
OPERATIONS = "+-*/"
RULES = {}
# Compute the rules - a hash rule table, basically
for c1 in "(+-*/":
    for c2 in "n*+-":
        for c3 in ")+-*/":
            hash_value = hash((c1, c2, c3))
            if c2 == 'n' or \
               ((c2 == '*' and c1 != '/') or \
                ((c1 !=  '*' and c1 != '-' and c1 != '/') and \
                 (c3 != '*' and c3 != '/'))):
                RULES[hash_value] = True
            else:
                RULES[hash_value] = False
def getOpProperty(exp, i1, i2):
    prop_add = prop_mul = False
    prnths = 0
    while i1 < i2:
        # Go through the section, checking its operations
        t = exp[i1]
        if t == '(':
            # Run fast over this section until we get to its end
            prnths += 1
            while prnths:
                i1 += 1
                t = exp[i1]
                if t == '(':
                    prnths += 1
                elif t == ')':
                    prnths -= 1
        elif t in OPERATIONS:
            # What kind of operation is it?
            if t == '-':
                return '-'
            elif t == '+':
                prop_add = True
            else:
                prop_mul = True       
        i1 += 1
    if prop_add:
    return '+'
elif prop_mul:
    return '*'
else:
    return 'n'
def cleanParentheses(exp):
    open_prnths = [] # A stack of the indices of the open parentheses
    i = 1 # We add one due to padding
exp_len = len(exp) + 1 # We add one due to padding

# Pad the exp with  '+'s (neutral operations) so we'll be guaranteed that
# every parentheses will not give an IndexError on left_op and right_op
# retrieval
exp.insert(0,'+')
exp.append('+')
pop = open_prnths.pop

while i < exp_len:
    token = exp[i]
    if token == '(':
        open_prnths.append(i)
    elif token == ')':
        # Now the interesting stuff begins
        prnths_start = pop()
        if RULES[hash((exp[prnths_start - 1],
                       getOpProperty(exp, prnths_start+1, i),
                       exp[i+1]))]:
            # Delete the parentheses
            del exp[i]
            del exp[prnths_start]
            exp_len -= 2
            i -= 2
    i += 1

# Strip the padding before returning
del exp[exp_len]
del exp[0]
    
return exp
if __name__ == "__main__":
    for i in xrange(int(raw_input())):
        print "".join(cleanParentheses(list(raw_input())))