constt
BAN USERdef isvalid(s):
"""Check if the expression given in string 's' is a valid arithmetic
expression.
Eg: (())()) - Invalid expression, (()()) - Valid expression
>>> isvalid('(())())')
False
>>> isvalid('(()())')
True
"""
if not s:
return 0
ps = [] # stack of parentheses
for c in s:
if c in '()':
if ps and ps[-1] == '(' and c == ')':
ps.pop()
else:
ps.append(c)
return len(ps) == 0
if __name__ == '__main__':
import doctest
doctest.testmod()
def minpar(s):
"""Given a string s of parentheses (ex: '(()'), return the minimum number of
parentheses that need to be inserted to make it into a well formed
(balanced) string. Time complexity O(n).
>>> minpar('')
0
>>> minpar(')')
1
>>> minpar('(((s)')
2
>>> minpar(')a(b(c)(')
3
>>> minpar(')a)b)c)')
4
"""
if not s:
return 0
ps = [] # stack of parentheses
for c in s:
if c in '()':
if ps and ps[-1] == '(' and c == ')':
ps.pop()
else:
ps.append(c)
return len(ps)
if __name__ == '__main__':
import doctest
doctest.testmod()
def rmsubrange(rs):
"""Given an array of 'array ranges' (rs), return an optimized array by
deleting subarrays. Time complexity O(n*log(n)).
NOTE: Array range (2,6) represents (2,3,4,5,6)
>>> rmsubrange([(2, 6), (3, 5), (20, 21), (7, 21)])
[(2, 6), (7, 21)]
>>> rmsubrange([(10, 13), (1, 8), (2, 6), (15, 18), (12, 18)])
[(1, 8), (10, 13), (12, 18)]
"""
if not rs or len(rs) == 1:
return rs
rs.sort(key=lambda x: x[0])
rs_opt = []
for i in range(len(rs) - 1):
if rs[i]:
if not (rs[i][0] >= rs[i+1][0] and rs[i][1] <= rs[i+1][1]):
rs_opt.append(rs[i])
if rs[i+1][1] < rs[i][1]:
rs[i+1] = None
return rs_opt
if __name__ == '__main__':
import doctest
doctest.testmod()
- constt October 24, 2015