Java正则表达式中的递归替换？

Question

Java正则表达式中的递归替换？

5

使用以下方法，我可以将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

- CK Ho

参见：https://dev59.com/rmHVa4cB1Zd3GeqPoZuH#44570869 - Stephan

4个回答

1

你可以从最内层的可约表达式开始评估，直到没有更多的redux存在。但是你必须注意其他的,、(和)。@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;
}

- Joop Eggen

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);

- user172501

0

您可以尝试使用波兰式表示法重写字符串，然后将任何% X Y替换为ABC(X,Y)。

这里是波兰式表示法的维基链接。

问题在于，当您递归地替换字符串时，需要找出首先发生的ABC(X,Y)重写。波兰式表示法对于“解密”这些重写发生的顺序非常有用，并且在表达式评估中被广泛使用。

您可以通过使用堆栈并记录哪个替换首先发生来实现此目的：查找最内层的括号集，仅将该表达式推入堆栈，然后从字符串中删除该表达式。当您想要重构原始表达式时，只需从堆栈顶部开始并应用反向转换(X)%(Y) -> ABC(X,Y)。

这在某种程度上是波兰式表示法的一种形式，唯一的区别是您不会将整个表达式作为字符串存储，而是将其存储在堆栈中以便更轻松地处理。

简而言之，在替换时，请从最内层的术语（其中没有括号）开始并应用反向替换。

使用 (X)%(Y) -> ABC{X,Y} 作为中间重写规则可能会有所帮助，然后将花括号改写为圆括号。这样可以更容易地确定哪个是最内层的术语，因为新术语不会使用圆括号。此外，这种实现方式更简单，但不够优雅。

- lucian.pantelimon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Boris Strandjev · Accepted Answer

我将回答第一个问题。我无法在单个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)