0

I have only just started working with Python and one of the exercises I got from my tutor is to convert a tuple (number of nested brackets) into decimals; I have been working on this for hours now, but I got nowhere... e.g. input = (((()))) output = 3

I started like this:

def add (x,y):
    if y == '()':
        return x
        else:
        length = len(y)
        return successor(add (x,y[1:length-1]))

could anyone give me a hint where I´ve gone wrong - PLEASE!!!!

eldarerathis
  • 35,455
  • 10
  • 90
  • 93
Curly
  • 1
  • 1
    Are you literally counting the number of brackets and dividing by two? – Katriel Dec 08 '10 at 21:25
  • What is the output for `(()())`? 2, I guess? – khachik Dec 08 '10 at 21:27
  • Yes, I guess that´s what I am supposed to do.. – Curly Dec 08 '10 at 21:31
  • thanks, that works nicely for the elements within a tuple, but that does not work for nested brackets ((())) or am I wrong?? sorry, I am really confused... – Curly Dec 08 '10 at 21:45
  • A tuple is not the same thing as the string '()' (which is the **representation of** a tuple); you should be clear about what is meant. – Karl Knechtel Dec 08 '10 at 21:48
  • '(((())))' has 4 pairs of parentheses in it, 3 of which are nested. – martineau Dec 08 '10 at 22:48
  • '(()())' has 3 pairs of parentheses, two of which are nested. but each of those is only nested 1 level deep -- so is it the depth of nesting or how many are nested (too any level)? – martineau Dec 08 '10 at 22:53

5 Answers5

1

You never change x. Presumably you want to add one to it before recursing. Also, constructs such as (()()) will trip you up.

Ignacio Vazquez-Abrams
  • 776,304
  • 153
  • 1,341
  • 1,358
  • To be fair, nested `$anything` can be nasty if you don't have a bit of parsing knowledge (CFGs, not regular languages). It trips regex fans all over the world every day ;) –  Dec 08 '10 at 21:30
  • I added now, def successor(x): return '(' + x + ')' – Curly Dec 08 '10 at 21:48
0
print len(s) / 2

Assuming you want to do this by recursion, you need to think about it a bit first. The point of recursion is to break the problem into smaller pieces which you know how to solve, and then to build up the solution for a large problem from the solutions to the smaller problems. Can you do that in this case? Yes: given a string, check that the first character is ( and the last character is ), then solve the problem for the remaining string and add one.

def depth(parens):
    # is the string empty? if so return 0
    # check that the first character is (
    # check that the last character is )
    # take off the first character and the last character
    # calculate depth(the remaining string)
    # add one and return

See if you can write that.

Katriel
  • 120,462
  • 19
  • 136
  • 170
  • still wracking my brains...I assume I have to get the length first to define the first and last character – Curly Dec 08 '10 at 22:15
  • @Curly: ohhhh... did you mean that you actually have a `tuple(tuple(tuple()))`? If so it's even easier... you don't need to check the first and last characters, just check that the tuple contains exactly one element and then recurse on that. – Katriel Dec 08 '10 at 22:37
0

Well, here is something that takes care of complex (()((()))):

def tuples(string, found=0):
  if not string: return found
  start = string.find('()')
  end = start + len('()')
  sub = string[:start] + string[end:]

  if start != 0 and end != len(string):
    return tuples(sub, found+1)
  else:
    return tuples(sub, found)

testing:

print tuples('') - 0
print tuples('()') - 0
print tuples('()()') - 0
print tuples('(()())') - 2
print tuples('(())') - 1
print tuples('(()') - 0
print tuples('( (()) (()()) ((())) )'.replace(' ', '')) - 8

I'm not sure how pythonic and fast it is though.

khachik
  • 28,112
  • 9
  • 59
  • 94
0

You can look at this ques

I had asked the same question but it was more for evaluation. In this look at the use of re to calculate inner () and then you can just increment the counter.

I hope this helps :)

Community
  • 1
  • 1
0

This is easy if you can use real tuples. They are hard to read in the Python syntax though

def f(t):
    return len(t) + sum(map(f, t)) 

print f( () )
print f( ((),()) )
print f( ((),) )
print f( (((),),((),()),(((),),)) )
John La Rooy
  • 295,403
  • 53
  • 369
  • 502