java - 用一些规则替换嵌套字符串

Question

字符串中有3条规则:

1. 它包含单词或组(用括号括起来)，并且组可以嵌套；

2. 如果单词或组之间有空格，这些单词或组应附加“+”。

例如:

"a b" needs to be "+a +b"
"a (b c)" needs to be "+a +(+b +c)"

如果单词或组之间有 |，则这些单词或组应用括号括起来。例如:

"a|b" needs to be "(a b)"
"a|b|c" needs to be "(a b c)"

考虑所有规则，这是另一个示例:

"aa|bb|(cc|(ff gg)) hh" needs to be "+(aa bb (cc (+ff +gg))) +hh"

我尝试使用正则表达式、堆栈和 recursive descent parser logic ，但还是不能完全解决问题。

有人可以分享这个问题的逻辑或伪代码吗？

新编辑:一项更重要的规则:竖线具有更高的优先级。

例如:

aa|bb hh cc|dd (a|b) 需要为 +(aa bb) +hh +(cc dd) +((a b))

(aa dd)|bb|cc (ee ff)|(gg hh) 需要为 +((+aa +dd) bb cc) +((+ee + ff) (+gg +hh))

新编辑:为了解决优先级问题，我找到了一种方法，在调用 Sunil Dabburi 的方法之前添加括号。

例如:

aa|bb hh cc|dd (a|b) 将是 (aa|bb) hh (cc|dd) (a|b)

>

(aa dd)|bb|cc (ee ff)|(gg hh) 将是 ((aa dd)|bb|cc) ((ee ff)|(gg hh))

由于性能对于我的应用程序来说并不是一个大问题，因此这种方式至少使它适合我。我想JavaCC工具可以完美地解决这个问题。希望其他人能够继续讨论和贡献这个问题。

Answer 1

这是我的尝试。根据你的例子和我想出的一些例子，我相信它在规则下是正确的。我通过将问题分成两部分解决了这个问题。

1. 解决我假设字符串仅包含单词或仅包含单词的组的情况。
2. 通过替换子组来解决单词和组问题，使用 1) 部分并用子组递归重复 2)。

    private String transformString(String input) {
        Stack<Pair<Integer, String>> childParams = new Stack<>();
        String parsedInput = input;
        int nextInt = Integer.MAX_VALUE;
        Pattern pattern = Pattern.compile("\\((\\w|\\|| )+\\)");
        Matcher matcher = pattern.matcher(parsedInput);
        while (matcher.find()) {
            nextInt--;
            parsedInput = matcher.replaceFirst(String.valueOf(nextInt));
            String childParam = matcher.group();
            childParams.add(Pair.of(nextInt, childParam));
            matcher = pattern.matcher(parsedInput);
        }

        parsedInput = transformBasic(parsedInput);
        while (!childParams.empty()) {
            Pair<Integer, String> childGroup = childParams.pop();
            parsedInput = parsedInput.replace(childGroup.fst.toString(), transformBasic(childGroup.snd));
        }
        return parsedInput;
    }

    // Transform basic only handles strings that contain words. This allows us to simplify the problem
    // and not have to worry about child groups or nested groups.
    private String transformBasic(String input) {
        String transformedBasic = input;
        if (input.startsWith("(")) {
            transformedBasic = input.substring(1, input.length() - 1);
        }

        // Append + in front of each word if there are multiple words.
        if (transformedBasic.contains(" ")) {
            transformedBasic = transformedBasic.replaceAll("( )|^", "$1+");
        }
        // Surround all words containing | with parenthesis.
        transformedBasic = transformedBasic.replaceAll("([\\w]+\\|[\\w|]*[\\w]+)", "($1)");
        // Replace pipes with spaces.
        transformedBasic = transformedBasic.replace("|", " ");
        if (input.startsWith("(") && !transformedBasic.startsWith("(")) {
            transformedBasic = "(" + transformedBasic + ")";
        }
        return transformedBasic;
    }

使用以下测试用例进行验证:

@ParameterizedTest
    @CsvSource({
            "a b,+a +b",
            "a (b c),+a +(+b +c)",
            "a|b,(a b)",
            "a|b|c,(a b c)",
            "aa|bb|(cc|(ff gg)) hh,+(aa bb (cc (+ff +gg))) +hh",
            "(aa(bb(cc|ee)|ff) gg),(+aa(bb(cc ee) ff) +gg)",
            "(a b),(+a +b)",
            "(a(c|d) b),(+a(c d) +b)",
            "bb(cc|ee),bb(cc ee)",
            "((a|b) (a b)|b (c|d)|e),(+(a b) +((+a +b) b) +((c d) e))"
    })
    void testTransformString(String input, String output) {
        Assertions.assertEquals(output, transformString(input));
    }

    @ParameterizedTest
    @CsvSource({
            "a b,+a +b",
            "a b c,+a +b +c",
            "a|b,(a b)",
            "(a b),(+a +b)",
            "(a|b),(a b)",
            "a|b|c,(a b c)",
            "(aa|bb cc|dd),(+(aa bb) +(cc dd))",
            "(aa|bb|ee cc|dd),(+(aa bb ee) +(cc dd))",
            "aa|bb|cc|ff gg hh,+(aa bb cc ff) +gg +hh"
    })
    void testTransformBasic(String input, String output) {
        Assertions.assertEquals(output, transformBasic(input));
    }