Рекурсивная замена с регулярным выражением Java?

Question

Я могу заменить ABC(10,5) на (10)%(5), используя:

replaceAll("ABC\\(([^,]*)\\,([^,]*)\\)", "($1)%($2)")

, но я не могу понять, как это сделать для ABC(ABC(20,2),5) или ABC(ABC(30,2),3+2).

Если я могу преобразовать в ((20)%(2))%5, как я могу преобразовать обратно в ABC(ABC(20,2),5)?

Спасибо, j

Answer 1

Вы можете использовать эту библиотеку регулярных выражений https://github.com/florianingerl/com.florianingerl.util.regex, которая также поддерживает рекурсивные регулярные выражения.

Преобразование ABC (ABC (20,2), 5) в ((20)% (2)))% (5) выглядит следующим образом:

    Pattern pattern = Pattern.compile("(?<abc>ABC\\((?<arg1>(?:(?'abc')|[^,])+)\\,(?<arg2>(?:(?'abc')|[^)])+)\\))");
    Matcher matcher = pattern.matcher("ABC(ABC(20,2),5)");
    String replacement = matcher.replaceAll(new DefaultCaptureReplacer() {
        @Override
        public String replace(CaptureTreeNode node) {
            if ("abc".equals(node.getGroupName())) {
                return "(" + replace(node.getChildren().get(0)) + ")%(" + replace(node.getChildren().get(1)) + ")";
            } else
                return super.replace(node);
        }

    });
    System.out.println(replacement);
    assertEquals("((20)%(2))%(5)", replacement);

Обратное преобразование, т. Е. Из ((20)% (2))% (5) в ABC (ABC (20,2), 5)выглядит так:

    Pattern pattern = Pattern.compile("(?<fraction>(?<arg>\\(((?:(?'fraction')|[^)])+)\\))%(?'arg'))");
    Matcher matcher = pattern.matcher("((20)%(2))%(5)");
    String replacement = matcher.replaceAll(new DefaultCaptureReplacer() {
        @Override
        public String replace(CaptureTreeNode node) {
            if ("fraction".equals(node.getGroupName())) {
                return "ABC(" + replace(node.getChildren().get(0)) + "," + replace(node.getChildren().get(1)) + ")";
            } else if ("arg".equals(node.getGroupName())) {
                return replace(node.getChildren().get(0));
            } else
                return super.replace(node);
        }

    });
    System.out.println(replacement);
    assertEquals("ABC(ABC(20,2),5)", replacement);

Answer 2

Я собираюсь ответить на первый вопрос. Я не смог выполнить задачу за один replaceAll. Я не думаю, что это даже достижимо. Однако, если я использую цикл, это должно сделать работу за вас:

    String termString = "([0-9+\\-*/()%]*)";
    String pattern = "ABC\\(" + termString + "\\," + termString + "\\)";
    String [] strings = {"ABC(10,5)", "ABC(ABC(20,2),5)", "ABC(ABC(30,2),3+2)"};
    for (String str : strings) {
        while (true) {
            String replaced = str.replaceAll(pattern, "($1)%($2)");
            if (replaced.equals(str)) {
                break;
            }
            str = replaced;
        }
        System.out.println(str);
    }

Я предполагаю, что вы пишете синтаксический анализатор для числовых выражений, таким образом, определение термина termString = "([0-9+\\-*/()%]*)". Это выводит это:

(10)%(5)
((20)%(2))%(5)
((30)%(2))%(3+2)

РЕДАКТИРОВАТЬ В соответствии с запросом OP я добавляю код для декодирования строк. Это немного более хакерский, чем прямой сценарий:

    String [] encoded = {"(10)%(5)", "((20)%(2))%(5)", "((30)%(2))%(3+2)"};
    String decodeTerm = "([0-9+\\-*ABC\\[\\],]*)";
    String decodePattern = "\\(" + decodeTerm + "\\)%\\(" + decodeTerm + "\\)";
    for (String str : encoded) {
        while (true) {
            String replaced = str.replaceAll(decodePattern, "ABC[$1,$2]");
            if (replaced.equals(str)) {
                break;
            }
            str = replaced;
        }
        str = str.replaceAll("\\[", "(");
        str = str.replaceAll("\\]", ")");
        System.out.println(str);
    }

И вывод:

ABC(10,5)
ABC(ABC(20,2),5)
ABC(ABC(30,2),3+2)

Answer 3

Вы можете начинать сначала вычислять внутренние наиболее редуцируемые выражения, пока не останется больше избыточности. Однако вы должны позаботиться о других ,, ( и ). Решение @BorisStrandjev лучше, более пуленепробиваемо.

String infix(String expr) {
    // Use place holders for '(' and ')' to use regex [^,()].
    expr = expr.replaceAll("(?!ABC)\\(", "<<");
    expr = expr.replaceAll("(?!ABC)\\)", ">>");
    for (;;) {
        String expr2 = expr.replaceAll("ABC\\(([^,()]*)\\,([^,()]*)\\)",
                "<<$1>>%<<$2>>");
        if (expr2 == expr)
            break;
        expr = expr2;
    }
    expr = expr.replaceAll("<<", ")");
    expr = expr.replaceAll(">>", ")");
    return expr;
}

Answer 4

Вы можете попробовать переписать строку, используя польскую запись, а затем заменить любое % XY на ABC (X, Y) .

Здесь - это вики-ссылка для польской нотации.

Проблема в том, что вам нужно выяснить, какая перезапись ABC (X, Y) произошла первой, когда вы их рекурсивно заменилив твоей строке.Польская нотация полезна для «расшифровки» порядка, в котором происходят эти переписывания, и широко используется при оценке выражений.

Вы можете сделать это, используя стек и запись, замена которой произошла первой: найдите самый внутренний набор скобок, поместите только это выражение в стек, а затем удалите его из вашей строки.Если вы хотите восстановить исходное выражение выражения, просто начните с верха стека и примените обратное преобразование (X)% (Y) -> ABC (X, Y) .

Это в некоторой степени форма польской нотации, с той лишь разницей, что вы не сохраняете все выражение в виде строки, а скорее сохраняете его в стеке для облегчения обработки.

Короче говоря, при замене начните с самых внутренних терминов (тех, у которых нет скобок в них) и примените обратную замену.

Может быть полезно использовать (X)% (Y) -> ABC {X, Y} в качестве промежуточного правила перезаписи, а затем переписать фигурные скобкикак круглые скобки.Таким образом, будет легче определить, какой термин является самым внутренним, поскольку новые термины не будут использовать круглые скобки.Также его проще реализовать, но не так элегантно.