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

Question

字符串中有3条规则：

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

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

例如：

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

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

"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，但仍不能完全解决问题。

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

Answer 1

我试图解决问题。不确定是否在所有情况下均有效。验证了问题中提供的输入，效果很好。

步骤：

1. 首先找到用竖线分隔的单词，将(添加到第一个单词
2. 由于管道分隔的单词被转换为包含空格。这会干扰我们下一步处理空间以添加+的操作。因此暂时使用$掩盖生成的空格。
3. 现在查找以空格分隔的单词，在其中添加+。此处可能包含未处理的包含(的单词。检查寄生计数。如果不匹配，请在正确的位置添加+。

注：我这里没有使用任何数据结构。请尝试使用其他输入，看看是否可行。

下面是代码：

public class Test {

    public static void main(String[] args) {

        String input = "aa|bb|(cc|(ff gg)) hh";

        String[] pipeTokens = input.split("\\|");

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < pipeTokens.length - 1; i++) {
            String token = pipeTokens[i];
            if (sb.toString().isEmpty()) {
                sb.append("(");
            }
            sb.append(token + "$");
        }

        int startParenthesesCount = 0;
        int closeParenthesesCount = 0;
        int closeParanthesesIndex = -1;

        if (pipeTokens.length > 1) {
            // If there are pipe separated tokens, get the last token and see if it is part of previous token.
            // i.e., if the parentheses count match. If they don't it's a continuation

            String lastToken = pipeTokens[pipeTokens.length - 1];
            char[] chars = lastToken.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char ch = chars[i];
                if (ch == '(') {
                    startParenthesesCount++;
                } else if (ch == ')') {
                    closeParenthesesCount++;
                    closeParanthesesIndex = i;
                }
            }

            if (startParenthesesCount != closeParenthesesCount) {
                lastToken = lastToken.substring(0, closeParanthesesIndex) + ')' + lastToken.substring(
                        closeParanthesesIndex);
            } else {
                // If the parentheses matched, if the word is space separated, add )
                if (lastToken.contains(" ")) {
                    lastToken =
                            lastToken.substring(0, lastToken.indexOf(" ")) + ")" + lastToken.substring(
                                    lastToken.indexOf(" "));
                } else {
                    lastToken = lastToken + ")";
                }
            }
            sb.append(lastToken);
        } else {
            // No pipe separated tokens, just take the complete word.
            sb.append(pipeTokens[0]);
        }

        input = sb.toString().trim();
        System.out.println(input); // should display pipes replaced with $ and parantheses added where necessary.

        String[] spaceTokens = input.split(" ");
        StringBuilder result = new StringBuilder();
        if (spaceTokens.length > 1) {

            // Space separated words found, find right place to put the parentheses
            for (String token : spaceTokens) {
                if (token.contains("(")) {

                    startParenthesesCount = 0;
                    closeParenthesesCount = 0;
                    int startParanthesesIndex = -1;

                    char[] chars = token.toCharArray();
                    for (int i = 0; i < chars.length; i++) {
                        char ch = chars[i];
                        if (ch == '(') {
                            startParenthesesCount++;
                            startParanthesesIndex = i;
                        } else if (ch == ')') {
                            closeParenthesesCount++;
                        }
                    }

                    if (startParenthesesCount != closeParenthesesCount) {
                        token = token.substring(0, startParanthesesIndex + 1) + '+' + token.substring(
                                startParanthesesIndex + 1);
                    }
                }
                result.append("+" + token + " ");
            }
        } else {
            // No space separated word found, just take the whole word.
            result.append(spaceTokens[0]);
        }

        input = input.replaceAll("\\$", " ");
        System.out.println(input);
    }

}