Tiefe erste Analyse Python

Question

Dieses Programm dauert, Adjazenzmatrix als Eingabe.

def DFS(matrix): 
stack = [1] 

dimen=len(matrix) 

rslt = [1] 

while stack: 
    current=matrix[stack[-1]-1] 
    for j in range(len(current)): 

      if current[j]==1 : 
       a=False 
       if (j+1 not in stack) and (j+1 not in rslt): 
        stack.append(j+1) 
        rslt.append(j+1) 
        a= True 
        break 
      if j+1== len(current): 
       current.append("farigh") 

    if len(matrix[stack[-1]-1]) == dimen and a == True : 
     b=0 
     current2= matrix[stack[-1]-1] 

     for e in range(len(current2)): 
      if current2[e]==1: 
       b=b+1 
     if b==1: 
      stack.pop() 
      current2.append("Hogya") 
      #print("appended") 

    if current[-1]=="farigh": 
     stack.pop() 


    print(stack,"stack") 
    print(rslt,"rslt") 

Funktioniert es so, wie es sollte. Ich gebe nichts von dieser Funktion zurück, da sie sich noch in der Testphase befindet.

Answer 1

Ihr Code überprüft im Grunde, dass es die gleiche Anzahl von öffnenden und schließenden Klammern gibt. Sie könnten so etwas wie geschrieben:

if x[0]!=")" and x[len(x)-1]!="(": 
    n_op = sum(c == '(' for c in input_string) 
    n_cl = sum(c == ')' for c in input_string) 

    if n_op==n_cl: 
     print("True") 

#  # This code is redundant, it only clears the lists 
#  for i in range(len(op)): 
#   op.pop() 
#   cl.pop() 

     print("okkay hai boss") 
    else: 
     print("False") 

aber Ihr Code würde wie ())(() mit einem String scheitern, wo Sie eine weitere Klammer schließen werden, dass Sie öffnen. Sie behandeln diesen Fall in Ihrer ersten Bedingung, indem Sie sicherstellen, dass das erste Zeichen keine schließende Klammer ist, aber es ist nicht genug.

Ein weiterer Punkt ist, dass Sie davon ausgehen, dass alles, was nicht () ist. Ich kenne Ihre Bedürfnisse nicht genau, aber es wäre sicherer zu überprüfen (nur für den Fall).

Stattdessen könnten Sie den folgenden Code verwenden:

pending = 0 
for c in x: 
    # opening parentheses increase the count 
    if c == '(': 
     pending += 1 
    # closing parentheses decrease the count 
    elif c == ')': 
     pending -= 1 
    # if the count becomes negative, abort 
    if pending < 0: 
     break 

# at the end of the loop a positive number means too many opening parentheses 
# a negative value means that at some point there were too many closing parentheses 
# and a zero means all is ok 
if pending == 0: 
    print('True') 
else: 
    print('False')