Re: finding indices in a sequence of parentheses
tiissa wrote:
Steven Bethard wrote:
(2) Does anyone see an easier/clearer/simpler[1] way of doing this?
I'd personnally extract the parenthesis then zip the lists of indices.
In short:
def indices(mylist):
... lopen=reduce(list.__add__, [[i]*s.count('(') for i,s in
enumerate(mylist)],[])
... lclose=reduce(list.__add__, [[i]*s.count(')') for i,s in
enumerate(mylist)],[])
... return zip(lopen,lclose)
...
indices(lst)
[(2, 2), (4, 7), (6, 7), (8, 9), (8, 10)]
Before returning, you can check if the lists have same size and if the
'(' has lower or equal index than ')' in each of these couples. If not
you can raise the appropriate exception.
Disclaimer: not tested further than example above (but confident).
Not tested but confident should be an oxymoron for a programmer. Some
examples:
lst: ['(', '(', ')', ')']
hettinger [(1, 2), (0, 3)]
bethard [(1, 2), (0, 3)]
tiissa [(0, 2), (1, 3)] oops (or am I just spoilt by the XML spec?)
lst: ['(', ')(', ')']
hettinger [(0, 1), (1, 2)]
bethard [(1, 1), (0, 2)] oops
tiissa [(0, 1), (1, 2)]
So far Raymond's solution is my favourite...
Peter
--
http://mail.python.org/mailman/listinfo/python-list
Re: finding indices in a sequence of parentheses
Peter Otten wrote: tiissa wrote: Disclaimer: not tested further than example above (but confident). Not tested but confident should be an oxymoron for a programmer. Not tested but confident is an oxymoron for mathemtaticians. Programmers know better than that, they leave bugs in their code to have more work to do. ;) OTOH, you're right. Matching parentheses cannot be done without a stack, that should have rung a bell. -- http://mail.python.org/mailman/listinfo/python-list
Re: finding indices in a sequence of parentheses
tiissa wrote: Not tested but confident is an oxymoron for mathemtaticians. I think no amount of testing will give these strange people confidence. Proof is the magic word here. Peter -- http://mail.python.org/mailman/listinfo/python-list
Re: finding indices in a sequence of parentheses
Peter Otten wrote: I think no amount of testing will give these strange people confidence. Proof is the magic word here. Some would maybe be satisfied if your tests cover the whole set of input. When that's possible, that may be useless. But that's not a matter to bother them with. ;) (And of course, you just don't tell them how you generated their output with the same program.) -- http://mail.python.org/mailman/listinfo/python-list
Re: finding indices in a sequence of parentheses
Raymond Hettinger wrote:
[Steven Bethard]
I have a list of strings that looks something like:
lst = ['0', '0', '(*)', 'O', '(*', '*', '(*', '*))', '((*', '*)', '*)']
. . .
I want the indices:
(2, 2), (4, 7), (6, 7), (8, 9) and (8, 10)
opener_stack = []
for i, elem in enumerate(lst):
for c in elem:
if c == '(':
opener_stack.append(i)
elif c == ')':
print opener_stack.pop(), i
Thanks Raymond, this is definitely an elegant solution. It was also easy
to add all the error checking I needed into this one. For the curious,
my final solution looks something like:
def indices(lst):
stack = []
for i, elem in enumerate(lst):
for c in elem:
if c == '(':
stack.append(i)
elif c == ')' and not stack:
raise Exception(') at %i without (' % i)
elif c == ')':
yield stack.pop(), i
elif c == 'O' and stack:
raise Exception('O at %i after ( at %i' %
(i, stack[-1]))
elif c == '*' and not stack:
raise Exception('* at %i without (' % i)
if stack:
raise Exception('( at %r without )' % stack)
Thanks again!
STeVe
--
http://mail.python.org/mailman/listinfo/python-list
Re: finding indices in a sequence of parentheses
Steven Bethard wrote:
(2) Does anyone see an easier/clearer/simpler[1] way of doing this?
I'd personnally extract the parenthesis then zip the lists of indices.
In short:
def indices(mylist):
... lopen=reduce(list.__add__, [[i]*s.count('(') for i,s in
enumerate(mylist)],[])
... lclose=reduce(list.__add__, [[i]*s.count(')') for i,s in
enumerate(mylist)],[])
... return zip(lopen,lclose)
...
indices(lst)
[(2, 2), (4, 7), (6, 7), (8, 9), (8, 10)]
Before returning, you can check if the lists have same size and if the
'(' has lower or equal index than ')' in each of these couples. If not
you can raise the appropriate exception.
Disclaimer: not tested further than example above (but confident).
--
http://mail.python.org/mailman/listinfo/python-list
Re: finding indices in a sequence of parentheses
tiissa wrote:
I'd personnally extract the parenthesis then zip the lists of indices.
In short:
def indices(mylist):
... lopen=reduce(list.__add__, [[i]*s.count('(') for i,s in
enumerate(mylist)],[])
... lclose=reduce(list.__add__, [[i]*s.count(')') for i,s in
enumerate(mylist)],[])
... return zip(lopen,lclose)
...
indices(lst)
[(2, 2), (4, 7), (6, 7), (8, 9), (8, 10)]
Thanks, that's a good idea. In case anyone else is reading this thread,
and had to mentally unwrap the reduce expressions, I believe they could
be written as:
lopen = [x for i, s in enumerate(lst) for x in [i]*s.count('(')]
lclose = [x for i, s in enumerate(lst) for x in [i]*s.count(')')]
or maybe:
lopen = [i for i, s in enumerate(lst) for _ in xrange(s.count('('))]
lclose = [i for i, s in enumerate(lst) for _ in xrange(s.count(')'))]
Sorry, I have an irrational fear of reduce. ;)
STeVe
--
http://mail.python.org/mailman/listinfo/python-list
Re: finding indices in a sequence of parentheses
[Steven Bethard]
I have a list of strings that looks something like:
lst = ['0', '0', '(*)', 'O', '(*', '*', '(*', '*))', '((*', '*)', '*)']
. . .
I want the indices:
(2, 2), (4, 7), (6, 7), (8, 9) and (8, 10)
opener_stack = []
for i, elem in enumerate(lst):
for c in elem:
if c == '(':
opener_stack.append(i)
elif c == ')':
print opener_stack.pop(), i
To see something like this in production code, look at
Tools/scripts/texcheck.py
Raymond Hettinger
--
http://mail.python.org/mailman/listinfo/python-list
