根据数字 * 括号内容扩展给定字符串

Question

我正在尝试获取给定的字符串，当括号前有一个数字时，括号内的内容将重复该次数。我考虑过使用 StringBuilder 并构建了这个函数，但我不确定如何重复括号内的内容。示例- 3(ab) - 结果将是 ababab ，示例- 3(b(2(c))) 结果将是 bccbccbcc 在我在这里构建的函数中，它重复了括号而不是括号的内容。

  public static String solve(String s){
    StringBuilder sb = new StringBuilder();
    int repeat = 0;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            repeat = repeat * 10 + Character.getNumericValue(c);
        } else {
            while (repeat > 0) {
                sb.append(c);
                repeat--;
            }
            sb.append(c);
        }
    }
    return sb.toString();
    }
}

Answer 1

您需要一个堆栈来维护从最内层到最外层容器所需操作的某种内存。

这是Python中的代码：

def parenthesis_printer(s):
    L = [""]   # maintains the stack of the string-containers
    N = [1]    # maintains the stack of the print-multiplier needed for the corresponding string-container
    nstr = ""
    for i in range(len(s)):
        if s[i].isnumeric():
            nstr += s[i]
        elif s[i] == '(':
            nstr = "1" if len(nstr) == 0 else nstr
            nval = int(nstr)
            N.append(nval)
            L.append("")
            nstr = ""
        elif s[i] == ')':
            nval = N.pop()
            lval = L.pop()
            lstr = "".join([lval for _ in range(nval)])
            L[-1] += lstr
        else:
            L[-1] += s[i]
    return L[-1]

print(parenthesis_printer("3(b(2(c)))"))

输出：

bccbccbcc

Answer 2

这个问题自然是递归的。保留您已经开始的方法，您可以编写如下内容。在实际代码中，我可能更喜欢将标记化和解析分开的方法，这意味着我将进行两次单独的传递：第一次将输入字符串转换为标记，第二次从标记流中生成输出。

public static Pair<String, Integer> solve(String s, int start) {
    int repeat = 0;
    String ret = "";

    for (int i = start; i < s.length(); i++) {
        final char c = s.charAt(i);

        if (Character.isDigit(c)) {
            repeat = repeat * 10 + Character.getNumericValue(c);
        } else if (c == '(') {
            final Pair<String, Integer> inner = solve(s, i + 1);
            // At least one repetition, even if no explicit `repeat` given.
            ret += inner.first;
            while (--repeat > 0) {
                ret += inner.first;
            }
            repeat = 0; // Ensure that `repeat` isn’t -1 after the loop.
            i = inner.second;
        } else if (c == ')') {
            return new Pair<>(ret, i);
        } else {
            ret += c;
        }
    }

    return new Pair<>(ret, s.length());
}

将此代码转换为使用单个 StringBuilder——以避免冗余字符串复制——留作练习。

上面使用了一个简单的 Pair 助手 class。由于 Java 没有附带一个 (groan)，这里有一个非常简单的实现可以与上面的代码放在一起；你也可以使用 JavaFX 的 javafx.util.Pair 或 java.util.AbstractMap.SimpleEntry 或其他任何东西。

static class Pair<T, U> {
    final T first;
    final U second;

    Pair(T f, U s) {
        first = f;
        second = s;
    }
}

Answer 3

与几乎相同的答案，但在 java 中并带有一些调试输出以查看代码的行为方式：

public static String solve(String s)
{
    Stack<Integer> countStack = new Stack<>();   // stack for counting
    Stack<StringBuilder> stubs = new Stack<>();  // stack for parts of the string that were processed
    stubs.push(new StringBuilder());
    
    int count = 0;
    for(char c : s.toCharArray())
    {
        System.out.println(Character.toString(c) + "   " + count + "   " + countStack + stubs);
        
        if(Character.isDigit(c))
        {
            // part of a count (assumes digits are never part of the actual output-string)
            count = count * 10 + (c - '0');
        }
        else if(c == '(')
        {
            // encountered the start of a new repeated group
            if(count == 0)
                // no count specified, assume a count of one
                countStack.push(1);
            else
                // push the count for this group
                countStack.push(count);

            // push a new stringbuilder that will contain the new group
            stubs.push(new StringBuilder());
            count = 0;  // reset count
        }
        else if(c == ')')
        {
            // group terminated => repeat n times and append to new group one above
            String tmp = stubs.pop().toString();
            int ct = countStack.pop();
            
            for(int i = 0; i < ct; i++)
                stubs.peek().append(tmp);
        }
        else
        {
            // just a normal character, append to topmost group
            stubs.peek().append(c);
            count = 0;
        }
    }
    
    // if the string was valid there's only the output-string left on the stubs-list
    return stubs.peek().toString();
}

输出：

3   0   [][]
(   3   [][]
b   0   [3][, ]
(   0   [3][, b]
2   0   [3, 1][, b, ]
(   2   [3, 1][, b, ]
c   0   [3, 1, 2][, b, , ]
)   0   [3, 1, 2][, b, , c]
)   0   [3, 1][, b, cc]
)   0   [3][, bcc]

Returns:

bccbccbcc

根据数字 * 括号内容扩展给定字符串

Expansion on given string according to number * contents of the parentheses

java

string

algorithm

stringbuilder

expansion