Überprüfen Sie, ob jede geschweifte Klammer innerhalb eines Ausdrucks eine passende schließende Klammer hat.

Question

Ich habe ein Problem festgestellt, bei dem ich bewerten muss, ob jede in einem mathematischen Ausdruck verwendete Klammer eine passende schließende Klammer hat.

Zum Beispiel:

• Valid Ausdruck: [(a+b)+b]
• Nicht gültige Ausdruck: [(a+b}+b]

Unten ist mein Code:

str1 = input() 
matches = {'(':')','[':']','{':'}'} 
open = ['(','[','{'] 
close = [')',']','}'] 
track = [] 
negative = 0 
for c in str1: 
    if c in open: 
     track.append(c) 
    elif c in close: 
     if c != matches[track[-1]]: 
      negative = 1 
      break 
     else: 
      del track[-1] 
if negative == 1: 
    print ("False") 
else: 
    print ("True") 

Gibt es eine bessere Art und Weise zu tun, wie zum Beispiel mit regulären Ausdrücken? Ist mein Code gut genug oder kann er optimiert werden?

Answer 1

Je nachdem, was Sie mit Ihrem Ausdruck tun möchten, können Sie einfach LL Parser oder Shunting-Yard algorithm codieren. Sie sind die zwei häufigsten Lösungen für diese Art von Problem (das "Parsing" -Problem).

Answer 2

wäre ein Stapel arbeiten:

def validate(_str): 
    braces = set("[](){}") 
    opening = set("[({") 
    closing = {"]":"[", ")":"(", "}":"{"} 
    stack = list() 

    for _char in _str: 
     if _char in opening: 
      stack.append(_char) 
     elif _char in closing: 
      if closing[_char] == stack[-1]: 
       stack.pop() 
      else: 
       return False 
    return True 

print("Should be False:",validate("(a+b}+b")) 
print("Should be True:",validate("(a+b)+b")) 
print("Should be True:",validate("(a+[b-c+{d+e}])+b")) 
print("Should be False:",validate("(a+]b-c+{d+e}])+b"))