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

问题描述

字符串中有 3 条规则：

它包含单词或组（用括号括起来），组可以嵌套；
如果单词或组之间有空格，则这些单词或组应附加“+”。

例如：

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

我尝试过使用正则表达式、堆栈和递归下降解析器逻辑，但仍然无法完全解决问题。

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

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

例如：

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)

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

标签： javaparsingsyntaxnestedstack

解决方案

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

解决我假设字符串仅包含单词或仅包含单词的组的情况。
通过替换子组来解决单词和组，使用 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));
    }

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

问题描述

解决方案

推荐阅读