将迭代转化为递归

2022-01-24 00:00:00 python python-3.x 递归 iteration

问题描述

我想检查用户输入的string是否有均衡数量的(和)的

I want to check if the string user entered has a balanced amount of ( and )'s

例如.()( 不平衡(()) 平衡

def check(string):

        counter=0
        string=string.replace(" ","")

        if string[0] is "(":

           for x in string:
                if x is "(":
                        counter=counter+1
                elif x is ")":
                        counter=counter-1

           if counter1 is 0:
                print("Balanced")
           else:
                print("Unbalanced")
        else:
                print ("Unbalanced")

所以这行得通，但是我如何通过递归解决这个问题?我试图思考每次递归调用它时如何使变量减小，一旦它为0，stop.s

so this works, but how do I solve this problem with recursion? I am trying to think how I can make a variable decrease each time i call it recursively and once it's 0, stop.s

解决方案

算法的直接等效转换如下所示:

A direct, equivalent conversion of the algorithm would look like this:

def check(string, counter=0):
  if not string:
    return "Balanced" if counter == 0 else "Unbalanced"
  elif counter < 0:
    return "Unbalanced"
  elif string[0] == "(":
    return check(string[1:], counter+1)
  elif string[0] == ")":
    return check(string[1:], counter-1)
  else:
    return check(string[1:], counter)

像这样使用它:

check("(())")
=> "Balanced"

check(")(")
=> "Unbalanced"

请注意，由于 elif counter <，上述算法考虑了右括号出现在 相应的左括号之前的情况.0 条件 - 因此修复了原始代码中存在的问题.

Notice that the above algorithm takes into account cases where the closing parenthesis appears before the corresponding opening parenthesis, thanks to the elif counter < 0 condition - hence fixing a problem that was present in the original code.

相关文章