-4

Anyone have any idea how to write a function that balances parentheses using recursion?

I was thinking of counting the number of times each outer or inner parenthesis pops up in a string, but then it would miss cases like this "()())()(" or this ")(".

My instructor had examples of recursion that solved factorials and calculated numbers of the fibonacci sequence, but she never really went over solving other types of problems.

jonyc
  • 41
  • 1
  • 1
  • 2
  • what do you want to accomplish? – Roman Pekar Aug 02 '13 at 02:55
  • I just don't understand how to solve this problem. For recursive functions there has to be a condition that exits the program. I don't know what that is for this case. – jonyc Aug 02 '13 at 02:58
  • I just didn't get what's your problem exactly? I see you input, what is desired output? – Roman Pekar Aug 02 '13 at 02:59
  • 2
    Hint: when you find an open paren, call find_match. When find_match finds an open paren, call find_match. when find_match finds a close paren, return. If find_match finds the end of string, there's an open paren without a close paren. If the top find_match returns and a close paren is found later in the string, there's an unmatched close paren. – Codie CodeMonkey Aug 02 '13 at 03:00
  • A string is typed in for example, something like this "(()()())()(())" and it tells whether it's balanced or not. – jonyc Aug 02 '13 at 03:01
  • 2
    I understand that you're new to the site and need help with your homework. But please google the problem first, or at least pay attention to the suggested posts on the side when you write your question. [Your classmate (I think) has already asked a similar question](http://stackoverflow.com/q/18006806/198633) to which s/he got [an answer he was happy with](http://stackoverflow.com/a/18006897/198633). PS: you forgot to mention that your assignment requires you to do this in python3 – inspectorG4dget Aug 02 '13 at 03:02
  • Think of a stack that can record depth. It's not just the numbers of (s and )s. Think of the context associated with a balanced string. – Jiminion Aug 02 '13 at 03:05
  • I agree with @Jim. You should look into using a stack as your data structure. – squiguy Aug 02 '13 at 03:09
  • @squiguy: for only one type of open and close symbol, you can get away with using only an `int`, which has the advantage of taking less space – inspectorG4dget Aug 02 '13 at 03:14
  • I'm pretty sure that isn't my classmate. Your solution returns the number of mismatched parentheses, the function that I'm trying to write has to say whether it's balanced or not. – jonyc Aug 02 '13 at 03:23
  • Also, it doesn't work correctly. – jonyc Aug 02 '13 at 03:35
  • You can very easily negative boolify the return value to turn it into what you need. Also, if you found something wrong with my implementation on the other question, you might consider leaving a comment on it, to catch my attention – inspectorG4dget Aug 02 '13 at 04:21
  • Yeah, I realized that after i posted and I can't leave a comment on your post. It shouldn't work for this input ")(" or any type of nested parentheses that contains a closed parenthesis before an open one. – jonyc Aug 02 '13 at 04:26
  • 1
    [Possible duplicate of Turning iteration into recursion](http://stackoverflow.com/questions/18006806/turning-iteration-into-recursion#comment26333652_18006806) – Sylwester Aug 02 '13 at 11:35

2 Answers2

6
def balanced(s, i=0, cnt=0):
    if i == len(s): return cnt == 0
    if cnt < 0: return False
    if s[i] == "(": return  balanced(s, i + 1, cnt + 1)
    elif s[i] == ")": return  balanced(s, i + 1, cnt - 1)
    return balanced(s, i + 1, cnt)

for s in ["()", "(()", "(())", "()()", ")("]:
    print "{}: {}".format(s, balanced(s))

(): True
((): False
(()): True
()(): True
)(: False
Roman Pekar
  • 107,110
  • 28
  • 195
  • 197
0

The way a recursive method to find closing parens would work is something like this

def findClose(chars):
    while len(chars) != 0:
        if chars[0] == ")":
            return True
        elif chars[0] == "(":
            findClose(chars[1:])

    return False       #base case

You would then just call findClose(chars) if you saw an open paren This is not complete, this is a method you can use to recursively find closing parens

Stephan
  • 16,509
  • 7
  • 35
  • 61