Skip to content

Instantly share code, notes, and snippets.

@quad
Last active Aug 12, 2020
Embed
What would you like to do?
OPERATORS = "+-"
def simplify_parens(expr):
"""
Remove all unnecessary parenthesis for a simple algebra-like string. It maintains the brackets, so any operator can be swapped for any other and the resulting expression will have the same results before and after parenthesis reduction.
>>> simplify_parens('a')
'a'
>>> simplify_parens('a + b')
'a + b'
>>> simplify_parens('a + b - c')
'a + (b - c)'
>>> simplify_parens('(a + ((b + c)))')
'a + (b + c)'
>>> simplify_parens('(((a + b)) + c)')
'(a + b) + c'
>>> simplify_parens('(((((a + b) + ((c + z)))) + (((d))))) + ((b))')
'(((a + b) + (c + z)) + d) + b'
"""
rv = postfix_to_infix(infix_to_postfix(expr))
if rv.startswith("(") and rv.endswith(")"):
return rv[1:-1]
else:
return rv
def infix_to_postfix(expr):
stack = []
for c in expr:
if c.isalnum():
yield c
elif c == ")":
yield from reversed(stack)
stack = []
elif c in OPERATORS:
stack.append(c)
yield from reversed(stack)
def postfix_to_infix(expr):
stack = []
for c in expr:
if c.isalnum():
stack.append(c)
elif c in OPERATORS:
a, b = stack.pop(), stack.pop()
stack.append(f"({b} {c} {a})")
return stack.pop()
def oneshot_parens(expr):
"""
Remove all unnecessary parenthesis for a simple algebra-like string. It maintains the brackets, so any operator can be swapped for any other and the resulting expression will have the same results before and after parenthesis reduction.
>>> oneshot_parens('a')
'a'
>>> oneshot_parens('a + b')
'a + b'
>>> oneshot_parens('a + b - c')
'a + (b - c)'
>>> oneshot_parens('(a + ((b + c)))')
'a + (b + c)'
>>> oneshot_parens('(((a + b)) + c)')
'(a + b) + c'
>>> oneshot_parens('(((((a + b) + ((c + z)))) + (((d))))) + ((b))')
'(((a + b) + (c + z)) + d) + b'
"""
ip_stack = []
pi_stack = []
for c in expr:
if c.isalnum():
pi_stack.append(c)
elif c in OPERATORS:
ip_stack.append(c)
elif c == ")":
while ip_stack:
o = ip_stack.pop()
a, b = pi_stack.pop(), pi_stack.pop()
pi_stack.append(f"({b} {o} {a})")
while ip_stack:
o = ip_stack.pop()
a, b = pi_stack.pop(), pi_stack.pop()
pi_stack.append(f"({b} {o} {a})")
rv = pi_stack.pop()
if rv.startswith("(") and rv.endswith(")"):
return rv[1:-1]
else:
return rv
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment