Regulärer Ausdruck zum Entfernen verschachtelter Klammern

Question

Ich habe versucht, einen regulären Ausdruck in Java zu schreiben, um alles in den unten stehenden Klammern zu entfernen, während alles andere beibehalten wird. Beachten Sie, dass die Klammern verschachtelt sein können, und ich glaube, das ist der Grund, warum mein Muster scheitert. Kann mir jemand helfen? Unten habe ich es versucht:

    String testData =
            "1. d4 Nf6 2. c4 g6 3. Nc3 Bg7 4. e4 d6 5. Nf3 O-O 6. Be2 e5 7. dxe5 dxe5 8. Qxd8 Rxd8 9. Bg5 Nbd7 10. O-C3 {Diagramm [#]} " +
            "Rf8 (10... Re8 11. Nb5 (11. Nd5)) (10... h6 11. Bxf6 Bxf6 12. Nd5) 11. Nd5 c6 (11... Nxe4 12. Nxc7 Rb8 13. Be3 b6 ) 12. Ne7+ Kh8 13. " +
            "Nxc8 Raxc8 14. Bxf6 (14. Be3) 14... Nxf6 15. Nd2 (15. Bd3) 15... Bh6 16. f3 Nd7 17. Kc2 Bxd2 (17... Rdd8 18. b4) 18. Rxd2 Nc5 19. b4 Ne6 20. Rd7 b5 " +
            "(20... Rdd8 21. Rxb7 Nd4+ 22. Kd3) 21. Rxa7 Nd4+ 22. Kd3 Rdd8 23. Ke3 Nc2+ 24. Kf2 Rd2 25. Rd1 Rfd8 26. Rxd2 {Diagramm [#]} (26. cxb5 cxb5 " +
            "27. Rc7 Rxd1 28. Bxd1 Rd2+ 29. Kg3 Ne1 30. Bb3 f6 31. Rf7 Nxg2 32. Rf8+ Kg7 33. Rf7+ Kh6 34. Rf6 Nf4 35. Kh4 (35. Rxf4 exf4+ 36. Kxf4 Rxh2) 35... " +
            "Rxh2+ 36. Kg4 Rg2+ 37. Kh4 Nd3 38. a3 Rh2+ 39. Kg4 Rh1 40. Rc6 {Diagramm [#]}) 26. Rxd 27. Kf1 Nd4 28. cxb5 cxb5 29. a4 (29. Rd7 Rxa2 30. Bd3 Ra3 31. " +
            "Be2 Ra1+ 32. Kf2 Ra2 ) (29. Bxb5 Nxb5) 29. Rxe2 (29... bxa4 30. Bc4) 30. axb5 Rb2 31. b6 Rxb4 32. b7 Kg  ";

    testData = testData.replaceAll(Pattern.quote("{") + ".*" + Pattern.quote("}"), "")
                    .replaceAll(Pattern.quote("(") + ".*" + Pattern.quote(")"), "")
                    .replaceAll(Pattern.quote("$") + "[0-9]+", "");

    System.out.println(testData);

aber das gibt aus:

1. d4 Nf6 2. c4 g6 3. Nc3 Bg7 4. e4 d6 5. Nf3 O-O 6. Be2 e5 7. dxe5 dxe5 8. Qxd8 Rxd8 9. Bg5 Nbd7 10. O-C3 Rf8 ) 11. Nd5 c6 12. Ne7+ Kh8 13. Nxc8 Raxc8 14. Bxf6 14... Nxf6 15. Nd2 15... Bh6 16. f3 Nd7 17. Kc2 Bxd2 18. Rxd2 Nc5 19. b4 Ne6 20. Rd7 b5 21. Rxa7 Nd4+ 22. Kd3 Rdd8 23. Ke3 Nc2+ 24. Kf2 Rd2 25. Rd1 Rfd8 26. Rxd2 35... Rxh2+ 36. Kg4 Rg2+ 37. Kh4 Nd3 38. a3 Rh2+ 39. Kg4 Rh1 40. Rc6 ) 26... Rxd2 27. Kf1 Nd4 28. cxb5 cxb5 29. a4 29... Rxe2 30. axb5 Rb2 31. b6 Rxb4 32. b7 Kg

was offensichtlich falsch ist, weil es Klammern enthält.

Die korrekte Antwort wäre:

1. d4 Nf6 2. c4 g6 3. Nc3 Bg7 4. e4 d6 5. Nf3 O-O 6. Be2 e5 7. dxe5 dxe5 8. Qxd8 Rxd8 9. Bg5 Nbd7 10. O-C3 Rf8 11. Nd5 c6 12. Ne7+ Kh8 13. Nxc8 Raxc8 14. Bxf6 14... Nxf6 15. Nd2 15.. Bh6 16. f3 Nd7 17. Kc2 Bxd2 18. Rxd2 Nc5 19. b4 Ne6 20. Rd7 b5 21. Rxa7 Nd4+ 22. Kd3 Rdd8 23. Ke3 Nc2+ 24. Kf2 Rds 25. Rd1 Rds 26. Rwhatholicvd 26. Rvd 27. Kvh 28. cxb5 cv

Answer 1

```html

Hier keine Regex verwenden. Wie Sie aus Ihrem Beispiel sehen können, würde etwas wie \\(.*?)\\) versuchen, das minimale Match zwischen dem ersten gefundenen ( und dem nächsten ) zu finden, sodass im Fall von Daten wie

a (b (c d) e) f

wird das Regex \(.*?\) übereinstimmen

a (b (c d) e) f
  ^^^^^^^^

und wird den Teil e) nicht übereinstimmend lassen.

Sie könnten wahrscheinlich ein Regex für diese Aufgabe schreiben, da einige Regex-Flavors Rekursion unterstützen, aber leider unterstützt der in Java verwendete Regex-Parser dies nicht.

Also können Sie einfach Ihren eigenen einfachen Parser schreiben, um die verschachtelte Klammer zu entfernen, wie
<sub>(Ich gehe davon aus, dass der Text gut formatiert ist, sodass es keine Dinge wie <code>({)})</code> oder ungepaarte Klammern gibt)</sub>

String data = "1. d4 Nf6 2. c4 g6 3. Nc3 Bg7 4. e4 d6 5. Nf3 O-O 6. Be2 e5 7. dxe5 dxe5 8. Qxd8 Rxd8 9. Bg5 Nbd7 10. O�C Rf8 (10... Re8 11. Nb5 (11. Nd5)) (10... h6 11. Bxf6 Bxf6 12. Nd5) 11. Nd5 c6 (11... Nxe4 12. Nxc7 Rb8 13. Be3 b6 ) 12. Ne7+ Kh8 13. "
        + "Nxc8 Raxc8 14. Bxf6 (14. Be3) 14... Nxf6 15. Nd2 (15. Bd3) 15... Bh6 16. f3 Nd7 17. Kc2 Bxd2 (17... Rf 18. b4) 18. Rxd2 Nc5 19. b4 Ne6 20. Rd7 b5 "
        + "(20... R 21. Rb7 Nd4+ 22. Kd3) 21. Rxa7 Nd4+ 22. Kd3 R 23. Ke3 Nc2+ 24. Kf2 Rd 25. Rd1 R 26. R (26. c 27. Rc) 26... R 27. Kf1 Nd4 28. c 29. a (29. R 30. Bd3 R 31. "
        + "Be2 R 32. Kf2 R 33. R ) (29. B 29... N ) 29... R  29... b (29... b 30. Bc 30. ax b 31. b 32. b 32. K g ) ";

StringBuilder buffer = new StringBuilder();

int parenthesisCounter = 0;

for (char c : data.toCharArray()) {
    if (c == '(' || c == '{' )
        parenthesisCounter++;
    if (c == ')' || c == '}' )
        parenthesisCounter--;
    if (!(c == '(' || c == '{' || c == ')' || c == '}') && parenthesisCounter == 0)
        buffer.append(c);
}

Und danach können Sie sich einfach darauf konzentrieren, den Rest der unerwünschten Daten zu entfernen, wie Sie es zuvor verwendet haben

.replaceAll(Pattern.quote("$") + "[0-9]+", "");

Also wird das Ergebnis von

System.out.println(buffer.toString().replaceAll(
        Pattern.quote("$") + "[0-9]+", ""));

sein

1. d4 Nf6 2. c4 g6 3. Nc3 Bg7 4. e4 d6 5. Nf3 O-O 6. Be2 e5 7. dxe5 dxe5 8. Qxd8 Rxd8 9. Bg5 Nrd7 10. O�C Rf8 11. Nd5 c6 12. N�C8 Kf8 13. Nxc Rd8 14. B�6 14... Nf6 15. Nd2 15... Bh6 16. f3 Nd7 17. Kc2 Bxd2 18. Rxd Nc 19. b Nd6 20. Rd7 b 21. Rxa Nd4 22. Kd3 R 23. Ke3 Nc2 24. Kf2 Rd 25. D1 Rfd 26. R� 26... R 27. Kf Nd R 28. c 29. a 29... R 29... R 30. a Rb 31. b Rb4 32. b K g

```

Answer 2

Pshemos Antwort ist gut, aber ich wollte Ihnen zeigen, wie es mit regulären Ausdrücken gemacht werden kann und wie ich den Code optimieren könnte:

import java.util.regex.Pattern;

/**
 * Erstellt für http://stackoverflow.com/a/25335225/1266906
 */
public class RemoveBrackets {

    public static void main(String[] args) {
        String testData =
                "1. d4 Nf6 2. c4 g6 3. Nc3 Bg7 4. e4 d6 5. Nf3 O-O 6. Be2 e5 7. dxe5 dxe5 8. Qxd8 Rxd8 9. Bg5 Nbd7 10. O-0 {Diagram [#]} " +
                        "Rf8 (10... Re8 11. Nb5 (11. Nd5)) (10... h6 11. Bxf6 Bxf6 12. Nd5) 11. Nd5 c6 (11... Nxe4 12. Nxc7 Rb8 13. Be3 b6 ) 12. Ne7+ Kh8 13. " +
                        "Nxc8 Raxc8 14. Bxf6 (14. Be3) 14... Nxf6 15. Nd2 (15. Bd3) 15... Bh6 16. f3 Nd7 17. Kc2 Bxd2 (17... Rcd8 18. b4) 18. Rxd2 Nc5 19. b4 Ne6 20. Rd7 b5 " +
                        "(20... Rcd8 21. Rxb7 Nd4+ 22. Kd3) 21. Rxa7 Nd4+ 22. Kd3 Rcd8 23. Ke3 Nc2+ 24. Kf2 Rd2 25. Rd1 Rfd8 26. Rxd2 {Diagram [#]} (26. cxb5 c-b5 " +
                        "27. Rc7 R-d2+ 28. B-d7 Rd2+ 29. G-g7 30. B-b3 f6 31. R-f7 N-g2 32. R-f8+ K-g7 33. R-f7+ K-h6 34. R-f6 N-f4 35. Kh4 (35. R-f4 e-f4 36. K-gnu4 R-h2) 35..." +
                        " Rx-h2+ 36. G-g4 R-g2+ 37. Gh4 Nd3 38. a3 R-h2+ 39. gk4 R-h1 40. Rc6 {Diagram [#]}) 26. R-d2 R-d2 27. G-f1 Nd4 28. c-b5 c-b5 29. Gh4 (29. Rd7 R-a2 30. Bd3 R-a3 31. " +
                        "Be2 Ra1+ 32. Kf2 Ra2 ) (29. B-c5 N-b5) 29... R-e2 (29... b-a4 30. B-c4) 30. a-b R-b2 31. b-c R-b7 32. b-g  ";
        System.out.println(replaceLoop(testData).replaceAll(Pattern.quote("$") + "[0-9]+", ""));
        System.out.println(copyIterator(testData).replaceAll(Pattern.quote("$") + "[0-9]+", ""));
    }

    private static String replaceLoop(String data) {
        Pattern pattern = Pattern.compile("\\([^()]*\\)|\\{[^{}]*\\}");
        String previous, current = data;
        do {
            previous = current;
            current = pattern.matcher(previous).replaceAll("");
        } while (!previous.equals(current));
        return current;
    }

    private static String copyIterator(String data) {
        StringBuilder sb = new StringBuilder();
        int start = 0;
        int level = 0;
        for (int i = 0; i < data.length(); i++) {
            switch (data.charAt(i)) {
                case '(':
                case '{':
                    if (level == 0 && start >= 0) {
                        sb.append(data.substring(start, i));
                        start = -1;
                    }
                    level++;
                    break;
                case ')':
                case '}':
                    level--;
                    if (level == 0) {
                        start = i + 1;
                    } else if (level < 0) {
                        throw new IllegalStateException("Zu viele schließende Klammern.");
                    }
                    break;
            }
        }
        if (level > 0) {
            throw new IllegalStateException("Zu viele öffnende Klammern.");
        }
        if (start >= 0 && start < data.length()) {
            sb.append(data.substring(start, data.length()));
        }
        return sb.toString();
    }
}

In replaceLoop entferne ich nur Klammergruppen, die selbst keine Klammern enthalten (innerste Klammern) und muss daher wiederholen, bis der String nicht mehr geändert wird. Dies kann teuer sein, insbesondere wenn Sie erwarten, dass Klammern stark verschachtelt sind. Wie bereits erwähnt, das Problem ist, dass Sie sich nur auf bereits übereinstimmende Zeichen beziehen können, nicht auf ihr Gegenteil oder ihre Anzahl; wenn Sie wissen, wie tief die Dinge normalerweise verschachtelt sind, können Sie natürlich ein Muster schreiben, das alle erwarteten Ebenen auf einmal entfernt und nur selten mehr als zwei Suchvorgänge erfordert.

In copyIterator bestimme ich, welche Teile nicht umschlossen sind, und kopiere diese Teile in einen neuen StringBuilder. Durch das Kopieren von Blöcken minimiere ich die Anzahl der Male, die der StringBuilder neu dimensioniert wird, und da das Kopieren von Blöcken oft genauso teuer ist wie das Kopieren einzelner Zeichen, sinken die Kosten pro Zeichen. Auch indem ich switch verwende, kann der Compiler eine Integer-Map nutzen, die die Überprüfung der 4 relevanten Zeichen auf einmal durchführen kann, anstatt sie einzeln zu überprüfen, wie er es tun müsste, wenn ich ifs benutze (ja, coole Compiler sollten dies für Sie tun, aber ...).