Parentheses

#!/usr/bin/env python

import unittest

class Stack(list):
    def push(self, item):
        self.append(item)
    def isEmpty(self):
        return not self
    def peek(self):
        return self[-1] if self else None

def find_matching_brackets(str):
    matching = {}
    s = Stack()
    for i, c in enumerate(str):
        if c == '(':
            s.push(i)
        elif c == ')':
            oi = s.pop()
            matching[oi] = i
    return matching

def simplify(string):
    high_priority = ['*', '/']
    low_priority = ['+', '-']
    string = "".join(string.split())
    matching = find_matching_brackets(string)
    redundant = {}
    for i, c in enumerate(string):
        if c == "(":
            # go with exceptions, inheriting str is tedious
            try:
                left = string[i-1]
            except IndexError:
                left = None
            try:
                right = string[matching[i]+1]
            except IndexError:
                right = None
            if not left and not right:
                # for the outer brackets
                redundant[i] = matching[i]
            else:
                needs_brackets = False
                # iterate through the elements inside brackets
                # and find operators with low priority
                substring = string[i+1:matching[i]]
                j = 0
                while j < len(substring):
                    if substring[j] == '(':
                        # skip elements enclosed with brackets
                        j = matching[i+j+1] - i
                    else:
                        if substring[j] in low_priority and (left in high_priority or right in high_priority or left == '-'):
                                needs_brackets = True
                                break;
                        j += 1
                if not needs_brackets:
                    redundant[i] = matching[i]
    out = list(string)
    for k, v in redundant.items():
        out[k] = out[v] = ''
    return "".join(out)

class Test(unittest.TestCase):
    def test_simplify(self):
        self.assertEqual(simplify("1*(2+(3*(4+5)))"), "1*(2+3*(4+5))")
        self.assertEqual(simplify("2 + (3 / -5)"), "2+3/-5")
        self.assertEqual(simplify("x+(y+z)+(t+(v+w))"), "x+y+z+t+v+w")
        self.assertEqual(simplify("(((x))+((y)+z+(f+n))+((t+(v*w))))"), "x+y+z+f+n+t+v*w")
        self.assertEqual(simplify("1*(2*(3+4))"), "1*2*(3+4)")
        self.assertEqual(simplify("1*(2*(3*(4+5)))"), "1*2*3*(4+5)")
        self.assertEqual(simplify("1*(2*((3+4)+5))"), "1*2*(3+4+5)")
        self.assertEqual(simplify("1*(2*((3+4)*5))"), "1*2*(3+4)*5")
        self.assertEqual(simplify("1*(2*3)+(4)*(5)"), "1*2*3+4*5")
        self.assertEqual(simplify("1*((2*3)+(4))*(5)"), "1*(2*3+4)*5")
        self.assertEqual(simplify("1-(1+1)"), "1-(1+1)")
        self.assertEqual(simplify("1-(1*1)"), "1-1*1")
        self.assertEqual(simplify("1+(1-1)"), "1+1-1")
        self.assertEqual(simplify("1/(1*1)"), "1/1*1")
        self.assertEqual(simplify("1*(1*1)"), "1*1*1")
        self.assertEqual(simplify("1*(1*1)"), "1*1*1")
        self.assertEqual(simplify("1+(-1-(1+1))"), "1+-1-(1+1)")

if __name__ == '__main__':
    unittest.main()