Använda sig av en Stack för att kolla att parenteser är korrekt utsatta

Parenteserna är (), [] och {}.

Programmet ska printa True för nedanstående rader:

print(check_parentheses("()"))
print(check_parentheses("(()())"))
print(not check_parentheses("(()))")) # Unbalanced
print(not check_parentheses("((())")) # Unbalanced

print(check_parentheses("({})"))
print(not check_parentheses("({)}")) # Bad nesting
print(check_parentheses("({} [()] ({}))"))
print(not check_parentheses("({} [() ({)})")) # Unbalanced and bad nesting

Jag har skrivit följande rader:

def check_parentheses(string):
open_parentheses = "{(["
closed_parentheses = "})]"
stack1 = Stack()
for char in string:
if char in open_parentheses:
stack1.push(char)
for char in string:
if char in closed_parentheses and stack1.get_size() > 0:
stack1.pop()
elif char in closed_parentheses and stack1.get_size() == 1:
c: char = stack1.pop()
if c != ")":
return False
elif char in closed_parentheses and stack1.get_size() == 0:
return False

if(stack1.is_empty()):
return True
else:
return False

Med denna programkod får jag True för alla rader förutom den sjätte. Jag försökte ordna detta genom att skriva:

elif char in closed_parentheses and stack1.get_size() == 1:
c: char = stack1.pop()
if c != ")":
return False

Men detta fungerar inte. Ser inte riktigt vad jag begår för misstag, eller hur jag ska gå tillväga för att lösa detta.

Använd knappen för programkod för att formatera texten så den blir läsbar. Det är knappen {;}
Om du inte kan redigera frågan, gör ett svar med koden korrekt formaterad.

Om du använder "Infoga programmeringskod" så blir det läsbart.

När du hittar en closed_parentheses så måste den matcha med den översta i stacken. Om den inte gör det är det fel.

def check_parentheses(string):
open_parentheses = "{(["
closed_parentheses = "})]"
stack1 = Stack()
for char in string:
if char in open_parentheses:
stack1.push(char)
for char in string:
if char in closed_parentheses and stack1.get_size() > 0:
stack1.pop()
elif char in closed_parentheses and stack1.get_size() == 1:
c: char = stack1.pop()
if c != ")":
return False
elif char in closed_parentheses and stack1.get_size() == 0:
return False

if(stack1.is_empty()):
return True
else:
return False

Blev det bättre nu?

Kemibiologi1999 skrev:

def check_parentheses(string):
open_parentheses = "{(["
closed_parentheses = "})]"
stack1 = Stack()
for char in string:
if char in open_parentheses:
stack1.push(char)
for char in string:
if char in closed_parentheses and stack1.get_size() > 0:
stack1.pop()
elif char in closed_parentheses and stack1.get_size() == 1:
c: char = stack1.pop()
if c != ")":
return False
elif char in closed_parentheses and stack1.get_size() == 0:
return False

if(stack1.is_empty()):
return True
else:
return False

Blev det bättre nu?

Lite, men indenteringen är ju helt fel.

Det är en bit kvar men några kommentarer:

Det räcker inte att kontrollera att det ligger en öppnande parentes på stacken när du ser en stängande, det ska vara rätt stängande. Till exempel kräver "{" att den stängande är "}", de måste matcha parvis.
Men kan vara bra att först få allt att funka för bara vanliga parenteser, alltså "(" och ")" och sen lägga till de andra.

En annan sak: Om du gör så här:

if char in closed_parentheses and stack1.get_size() > 0:
stack1.pop()

så tappar du bort vilken parantes som låg på stacken och som du ska kontrollera mot, du spar inte värdet från pop().

def check_parentheses(string):
    open_parentheses = "{(["
    closed_parentheses = "})]"
    stack_for_open_parentheses = Stack()
    stack_for_closed_parentheses = Stack()
    for char in string:
        if char in open_parentheses:
            stack_for_open_parentheses.push(char)

    reversed_string = string[::-1]
    for char in reversed_string:
        if char in closed_parentheses:
            stack_for_closed_parentheses.push(char)
    x = True

    if stack_for_closed_parentheses.get_size() != stack_for_open_parentheses.get_size():
        x = False

Jag har nu skrivit om programkoden till detta. Detta är första gången jag använder Stacks, så funderar över om det finns något sätt att knyta fast det värdet som man "pop" till en variabel. Tänker att jag då kan undersöka om dessa passar med varandra.

Var kommer den här Stack() ifrån egentligen?

Det går annars bara att använda en vanlig lista i Python för en stack. Du behöver bara append(värde) och pop().

v = stack1.pop()

så bör du kunna skriva för ett värde du använt pop() på.

Hur tänker du med att ha två stackar? Den fina med en stack är att toppen alltid innehåller "kompisen" till den som ska kontrolleras.

Svara

Visa senaste svar