Wohlgeformte Klammern

[Hero]

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]

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

 

[Hero]

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!]

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]

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]

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

 

[Hero]

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]

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]

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]

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!]

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]

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!]

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]

Ja, aber keine vorgefertigte Stack-Klasse.

 

[HoaX]

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!]

@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]

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

 

[langhaar!]

Zugegebenermassen ja...

 

[Landei]

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]

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]

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]

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

 

[Landei]

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]

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]

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]

@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]

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" ...