Cmexpr tle

[savados]

spoj.pl/problems/CMEXPR/

Can anyone provide me with some "heavy" test cases? I tried 3 cases on my machine (# is randomly chosen operator):

1. Flat: (a#b)#...#(a#b), 1000 pairs.
2. Nested (((...#a)#a)#a), 1000 a's.
3. One more nested (b#(b#(b#...#a)#a)#a), 1000 a's and b's.

Average results are about [0.25, 0.5, 0.5] seconds and I didn't used psyco. I also found a solution http://www.spoj.pl/forum/viewtopic.php?f=20&t=265&p=910&hilit=CMEXPR, which is said to be accepted. I tried it with my test cases and got [1.5, 1.4, 2.9].

So what's wrong with my solution? There are some test cases where it's inefficient? Or it isn't "psyco-friendly" or something?

The code:

#!/usr/bin/env python
import psyco
psyco.full()
import gc
gc.disable()
def solve(line):
    def need_to_remove(token):
        next_sign = token.get('next_sign')
        if next_sign in ['*', '/']:
            if ('-' in token['contents']) or ('+' in token['contents']):
                return False
        if token['sign'] == '+':
            return True
        elif token['sign'] == '-':
            if ('-' not in token['contents']) and ('+' not in token['contents']):
                return True
        elif token['sign'] == '*':
            if ('-' not in token['contents']) and ('+' not in token['contents']):
                return True
        elif token['sign'] == '/':
            if ('-' not in token['contents']) and ('+' not in token['contents']) and ('/' not in token['contents']) and ('*' not in token['contents']):
                return True
        return False
    from collections import defaultdict

result = list(line)
prev_char = ''
tokens = {}
next_token_id = (0, 0)
cur_token_id = (-1, 0)
tokens[cur_token_id] = dict(remove=False, contents='')
max_id_for_depth = defaultdict(lambda: 0)
for pos, char in enumerate(line):
    if char == '(':
        tokens[next_token_id] = dict(remove=False, start_pos=pos, contents='')
        tokens[next_token_id]['parent'] = cur_token_id
        cur_token_id = next_token_id
        max_id_for_depth[cur_token_id[0]] += 1
        next_token_id = tuple([cur_token_id[0] + 1, max_id_for_depth[cur_token_id[0]] + 1])
        if prev_char in ['', '+', '(']:
            sign = '+'
        else:
            sign = prev_char
        tokens[cur_token_id]['sign'] = sign
    elif char == ')':
        tokens[cur_token_id]['end_pos'] = pos
        try:
            tokens[cur_token_id]['next_sign'] = line[pos + 1]
        except IndexError:
            pass
        if need_to_remove(tokens[cur_token_id]):
            result[tokens[cur_token_id]['end_pos']] = '~'
            result[tokens[cur_token_id]['start_pos']] = '~'
        cur_token_id = tokens[cur_token_id]['parent']
        tokens[cur_token_id]['contents'] += '@'
    else:
        tokens[cur_token_id]['contents'] += char
    prev_char = char

return (''.join(x for x in result if x != '~')).strip()
def main():
    from sys import stdin
    import itertools
    num = int(stdin.readline())
    print '\n'.join(solve(x()) for x in itertools.repeat(stdin.readline, num))
main()