# Wohlgeformte Klammern



## Hero (5. Nov 2011)

Hallo Leute,

Ich hab angefangen Java zu lernen und ich hab in Internet eine schöne Aufgabe gefunden, nämlich:
Ich soll Klammern auf wohlgeformt überprüfen. Gemeint ist ob die Klammern in richtiger Reihenfolge sind

Bsp von einer Wohlgeformten Klammer-Kombination:

```
{ ( [ ] ) }
```

Bsp von einer Nicht-Wohlgeformten Klammer-Kombination

```
{ ( [ ) ] }
```

Ich hab mir überlegt gehabt jede Klammer eine Zahl zu geben > []=1,-1 < und dann die Zahlen zu addieren: 1+(-1)=0 

Die Frage ist jetzt wie man einen Char eine Zahl zu teilen kann bzw. ist es überhaupt möglich dann so eine Rechenoperation durch zu führen?


----------



## HoaX (5. Nov 2011)

Mit Zahlen addieren wirst du nicht weit kommen. Aber um dich in die richtige Richtung zu stupsen: verwende einen Stack


----------



## Hero (5. Nov 2011)

Hallo,
Danke erstmal für die Schnelle Antwort.
Ich hab mir die Funktion von Stack durchgelesen und Beispiele angeguckt aber ich versteh jetzt nicht wie man den String "{ ( [ ] ) }" bzw. "{ ( [ ) ] }" auf Korrektheit überprüfen kann.


----------



## langhaar! (5. Nov 2011)

Wenn du eine offene Klammer findest, packst du sie auf den Stack.
Wenn du eine geschlossene Klammer findest, siehst du dir die letze offene Klammer an; diese musst du im Stack gespeichert haben.
Sind die Klammern verschieden, so hast du einen Klammerfehler gefunden.
Sind die Klammern gleich, nimmst du die offene Klammer vom Stack.
Auf deinem Stack sind somit nur offene Klammern und deine obige Frage stellt sich gar nicht,

EDIT:
Wenn dein Klammerprogramm z.B. die KLammergültigkeit von Java-Code erkennen soll, so musst du noch Kommentare berücksichtigen; dort sind die Klammern zu ignorieren.


----------



## Hero (6. Nov 2011)

Also ich bin jetzt soweit, dass das Programm alle offenen Klammern in den Stack packt aber ich weiß jetzt nicht wie z.B.:"{" und "}" vergleichen soll. Es sind doch eigentlich zwei unterschiedliche Zeichen.


----------



## Marco13 (6. Nov 2011)

Wie packst du die auf den Stack? Als String oder als Character? Poste mal den aktuellen Stand


----------



## Hero (6. Nov 2011)

Ich vergleiche die die Klammern als char (charAt) aber muss sie als String in den Stack packen als Char ging das nicht.


```
public class wohlKlammern 
{
		static void check (String str, Stack stack) {
		
			while(true){
				try {
					for(int i=0;i<str.length();i++){
						if(str.charAt(i)=='}' ^ str.charAt(i)==')' ^ str.charAt(i)==']'){
							System.out.println(stack.pop());
						}
					}
		         } catch (EmptyStackException e) {
		            break;
		         }
			}
			
		}

		public static void main(String[] args) {
			
			BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
			System.out.println("Bitte geben Sie einen Klammerausdruck ein:");
			
				try {
					String strg= input.readLine();
					
					Stack<String> s=new Stack<String>();
					for(int i=0;i<strg.length();i++){
						
						if(strg.charAt(i)=='{' ^ strg.charAt(i)=='(' ^ strg.charAt(i)=='['){
							
							s.push(strg.substring(i,i+1));
							
						}
					}
					
					check(strg,s);
					return;
					
				} catch (IOException e) {
					System.out.println(System.err);
					
					e.printStackTrace();
				}			
		}
	}
```


----------



## Marco13 (6. Nov 2011)

In Worten: Du musst alle ÖFFNENDEN Klammern auf den Stack pushen, und immer, wenn du eine SCHLIESSENDE Klammer findest, schauen, ob oben auf dem Stack die dazu passende (!) offene Klammer liegt, und wenn ja, dann diese Offene Klammer wegnehmen...


----------



## Hero (6. Nov 2011)

Also wenn ich eine Klammer-Kombination eingeben wie "{ ( [ ] ) }", werden "{ ( [" auf dem Stack gepusht, die Frage die ich mir schon die ganze Zeit stelle ist sage ich dem Programm, das "[" und "]" zusammen passen.


----------



## bygones (6. Nov 2011)

dieses "mapping" musst du im programm haben, d.h. dein programm weiss, dass wenn "]" kommt es nach "[" schauen muss, zb ueber eine Map

```
Map<String,String> klammern = new HashMap<String,String>();
klammern.put("]","[");
klammern.put(")","(");
klammern.put("}","{");
```


----------



## langhaar! (6. Nov 2011)

Hast du die Aufgabe wirklich im Internet gefunden oder ist es vielleicht doch eine Übungs/Hausaufgabe?

Ist letzteres der Fall, dann sollst du vermutlich eine rekursive Lösung erarbeiten und keinen Stack verwenden.


----------



## Landei (6. Nov 2011)

Eine Variante ohne Stack:


```
public class Bracket {
    private final char closing;
    private final Bracket parent;

    public Bracket(char closing, Bracket parent) {
        this.closing = closing;
        this.parent = parent;
    }

    public Bracket add(char c) {
        if (c == closing) {
            return parent;
        }
        switch (c) {
            case '(': return new Bracket(')', this);
            case '[': return new Bracket(']', this);
            case '{': return new Bracket('}', this);
            default: return null;
        }
    }

    public static boolean process(String s){
        final Bracket start = new Bracket('X',null);
        Bracket current = start;
        for(int i = 0; i< s.length(); i++) {
            current = current.add(s.charAt(i));
            if(current == null) {
                return false;
            }
        }
        return (current == start);
    }

    public static void main(String[] args) {
        //ein paar Tests
        System.out.println(process("([]{})"));
        System.out.println(process("([]{}"));
        System.out.println(process("([{]})"));
    }
}
```


----------



## langhaar! (6. Nov 2011)

Landei hat gesagt.:


> Eine Variante ohne Stack:



Deine Klasse Bracket bildet eine Liste, bei der jeweils das oberste Element weggenommen oder hinzugefügt wird. Das IST ein Stack.


----------



## Landei (6. Nov 2011)

Ja, aber keine vorgefertigte Stack-Klasse.


----------



## HoaX (6. Nov 2011)

Da finde ich das aber einfacher zu lesen und verstehen:

```
import java.util.Stack;

public class Klammern {

	static void parse(char[] s) throws Exception {
		Stack<Integer> klammern = new Stack<Integer>();
		
		for(int i=0; i<s.length; i++) {
			switch(s[i]) {
			case '{': klammern.push((int)'}'); break;
			case '[': klammern.push((int)']'); break;
			case '(': klammern.push((int)')'); break;
			default:
				if (s[i] != klammern.pop())
					throw new Exception("Falsche Klammer!");
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		String s = "([{]})";
		parse(s.toCharArray());
		System.out.println("ok");
	}
	
}
```


----------



## langhaar! (6. Nov 2011)

@Landei
Schon klar, aber wenn du sagst, du hast eine Lösung ohne Stack, dann gehe ich davon aus, dass du konzeptionell etwas ganz anderes gemacht hast (z.B. Rekursion) und nicht, dass du einen Stack unter anderem Namen implementierst.

Da wir jetzt schon zwei Lösungen haben, werd ich morgen mal zum Vergleich die rekursive Variante ergänzen.


----------



## Marco13 (6. Nov 2011)

... die auch einen Stack verwendet, der aber von Java selbst gemanagt wird


----------



## langhaar! (6. Nov 2011)

Zugegebenermassen ja...


----------



## Landei (6. Nov 2011)

OK, für alle Nörgler hier noch eine "wirklich" stackfreie Lösung:


```
public static boolean process(String s) {
        if (s.isEmpty()) return true;
        int index = s.indexOf("()");
        if (index == -1) index = s.indexOf("[]");
        if (index == -1) index = s.indexOf("{}");
        if(index == -1) return false;
        String s1 = s.substring(0, index);
        String s2 = s.substring(index + 2,s.length());
        return process(s1 + s2);
    }
```


----------



## tfa (6. Nov 2011)

Und für die Supernörgler eine echt _wirklich_ stackfreie Lösung:

```
public static boolean process(String s) {
	while (!s.isEmpty()) {
        String s2=s;
		s2 = s2.replaceAll("\\(\\)", "");
		s2 = s2.replaceAll("\\[\\]", "");
		s2 = s2.replaceAll("\\{\\}", "");
		if (s.equals(s2)) {
			return false;
		}
		s = s2;
	}
	return true;
}
```


----------



## Marco13 (6. Nov 2011)

Mal nebenbei: Ich weiß nicht, ob es "klug" ist, davon auszugehen, dass der ganze String immer NUR aus Klammern besteht.... ???:L Aber wenn's nur eine Uni-Aufgabe ist, kann das ja sogar sein


----------



## Hero (6. Nov 2011)

Also ich hab die Aufgabe auf einer Uni Seite gefunden aber mir fällt nicht mehr ein welche es war.


----------



## Landei (7. Nov 2011)

Marco13 hat gesagt.:


> Mal nebenbei: Ich weiß nicht, ob es "klug" ist, davon auszugehen, dass der ganze String immer NUR aus Klammern besteht.... ???:L Aber wenn's nur eine Uni-Aufgabe ist, kann das ja sogar sein



Na ja, man kann auch alles andere per RegEx rauswerfen. Und wenn das auch ausgewertet werden soll, steckt man ja schon mitten in "richtigem" Lexer-Parser-Geraffel.


----------



## Marco13 (7. Nov 2011)

Naja... kompliziertes Lexer/Parser "Geraffel" braucht man nur, wenn man noch verschiedene Arten von
/* Kommentaren
// Wie z.B. diesem */
verstehen will, ansonsten ist es 

```
for (i=0 bis length) {
    if charAt(i) ist KlammerAuf { push(k); }
    else if charAt(i) ist KlammerZu { prüfeUndPoppe(); }
}
```
Zugegeben, auch nicht praxisnah, aber doch praxisnäher als zu versuchen, Quellcode mit RegEx zu bearbeiten


----------



## Gossi (7. Nov 2011)

Oder sowas ^^


```
import java.util.ArrayList;
import java.util.List;

public class BracketResolve {

	List<String> openBrackets = new ArrayList<String>();

	public boolean inputIsOk(final String input) {
		for (char c : input.toCharArray()) {
			if (c == 40) {
				openBrackets.add("(");
			}
			if (c == 91) {
				openBrackets.add("[");
			}
			if (c == 123) {
				openBrackets.add("{");
			}
			if (c == 41) {
				if (openBrackets.get(openBrackets.size() - 1).toCharArray()[0] == (c - 1)) {
					openBrackets.remove(openBrackets.size() - 1);
				} else {
					return false;
				}
			}
			if (c == 93) {
				if (openBrackets.get(openBrackets.size() - 1).toCharArray()[0] == (c - 2)) {
					openBrackets.remove(openBrackets.size() - 1);
				} else {
					return false;
				}
			}
			if (c == 125) {
				if (openBrackets.get(openBrackets.size() - 1).toCharArray()[0] == (c - 2)) {
					openBrackets.remove(openBrackets.size() - 1);
				} else {
					return false;
				}
			}
		}
		return true;
	}

	public boolean inputIsOk(final List<String> input) {
		String complet = "";
		for (String string : input) {
			complet = complet + string;
		}
		return inputIsOk(complet);

	}

	public boolean inputIsOk(final char[] input) {
		String complet = input.toString();
		return inputIsOk(complet);
	}

}
```

Die Klasse hab ich am Anfang der Ausbildung mal geschrieben....


----------



## HoaX (7. Nov 2011)

@gossy: Ein Char mit einem Zahlenwert zu vergleichen ist böse, da braucht man ja ne Ascii-Tabelle neben sich um zu wissen wann da was passieren soll.


----------



## Marco13 (7. Nov 2011)

Ich gehe davon aus, dass das als "mahnendes Beispiel" gedacht war, im Sinne von: "Es ist mir zwar jetzt ein bißchen peinlich, aber Die Klasse hab ich am Anfang der Ausbildung mal geschrieben" ...


----------

