Pseudocode verstehen und verbessern

[Susi123]

Als Beispiel dient folgender Klammerausdruck: ( ( ) ( ( ( ) ( ) ) ) )
Der Klammerausdruck ist meiner Meinung nach korrekt.

Folgender Algorithmus (Pseudocode) zur Überprüfung von Klammerausdrücken soll nicht immer korrekt arbeiten.

Kann mir jemand bei der Fehlersuche helfen? Wäre das ein Gegenbeispiel: ( ( ( )? Hier würde der Algorithmus doch "true" ausgeben, obwohl der Klammerausdruck "false" wäre. Verstehe ich das richtig?

Wie kann ich den Algorithmus korrigieren, damit er genau dann true ausgibt, wenn der Klammerausdruck korrekt ist. Mir würde es schon sprachlich helfen. Wenn aber noch jemand eine Idee hätte, wie der Pseudocode korrigiert werden könnte, wäre mir sehr geholfen.

 

[Meniskusschaden]

Wäre das ein Gegenbeispiel: ( ( ( )? Hier würde der Algorithmus doch "true" ausgeben, obwohl der Klammerausdruck "false" wäre. Verstehe ich das richtig?

Ja, das wäre ein Gegenbeispiel.

Wie kann ich den Algorithmus korrigieren, damit er genau dann true ausgibt, wenn der Klammerausdruck korrekt ist. Mir würde es schon sprachlich helfen. Wenn aber noch jemand eine Idee hätte, wie der Pseudocode korrigiert werden könnte, wäre mir sehr geholfen.

Spiele es doch mal manuell mit deinem Beispiel ((() und einem korrekten Beispiel durch: bei einer öffnenden Klammer legst du einen Zettel auf einen Stapel, bei einer schließenden nimmst du den obersten Zettel wieder hinunter. Was ist das Besondere, falls es mehr öffnende als schließende Klammern gab? Worin unterscheiden sich die beiden Beispiele zum Schluss?

 

[Susi123]

Bei mehr öffnenden als schließenden Klammern wären Zettel übrig.
Man müsste damit ergänzen, dass am Ende noch überprüft werden muss, ob die Anzahl der öffnenden Klammern der Anzahl der schließenden Klammern entspricht. Ansonsten müsste auch „false“ ausgegeben werden. Ist das korrekt?
Mathematisch gesehen müsste die Differenz aus öffnenden Klammern und schließenden Klammern 0 betragen, um auf Korrektheit schließen zu können bzw. der Quotient aus öffnenden Klammern und schließenden Klammern müsste 1 betragen.

 

[LimDul]

Bei mehr öffnenden als schließenden Klammern wären Zettel übrig.
Man müsste damit ergänzen, dass am Ende noch überprüft werden muss, ob die Anzahl der öffnenden Klammern der Anzahl der schließenden Klammern entspricht. Ansonsten müsste auch „false“ ausgegeben werden. Ist das korrekt?
Mathematisch gesehen müsste die Differenz aus öffnenden Klammern und schließenden Klammern 0 betragen, um auf Korrektheit schließen zu können bzw. der Quotient aus öffnenden Klammern und schließenden Klammern müsste 1 betragen.

Im Prinzip richtig. Und nun guck die mal den Pseudo-Code, ob der zeigt, wie man testen kann, ob "Zettel übrig" sind.

 

[MoxxiManagarm]

Mathematisch gesehen müsste die Differenz aus öffnenden Klammern und schließenden Klammern 0 betragen, um auf Korrektheit schließen zu können bzw. der Quotient aus öffnenden Klammern und schließenden Klammern müsste 1 betragen.

Aber du willst nicht rechnen, du hast nur den Stack - also keine Differenz, kein Quotient. Wie müsste dieser Stapel aussehen am Ende des Vorgangs, damit die Klammerung korrekt ist?

 

[Susi123]

Der Stapel müsste am Ende des Vorgangs leer sein. Aber wie baue ich das in den Pseudocode ein?

 

[LimDul]

if <Hier Bedingung einfügen, die definiert, dass der Stapel leer ist>)
then
  return false
else
  return true

 

[Susi123]

Danke.