Java-如何递归解码字符串

Question

我需要解码一个递归编码为count后跟substring的字符串

给定一个编码字符串，任务是对其进行解码。字符串的编码模式如下所示。

示例：

输入：str[]=“1[b]”输出：b

输入：str[]="2[ab]输出：abab

输入：str[]=“2[a2[b]”输出：ABB

输入：str[]="3[b2[ca]]"输出：bcacabcacabcaca

下面是我试图实现的代码。我只知道它可以用两个堆栈来解决。

public class Main {
    public static void main(String[] args) {
        Stack<Interger> s1 = new Stack();
        Stack<String> s2 = new Stack();
        String result = "";
        for(int i = 0; i < args.length; i++){
            if(Interger.parseInt(args[i]) == 0){
                s1.push(args[i]);
            }
            if(args[i] == 0){
                if(args[i] == ']'){
                   result = s2.pop();
                }
                if(args[i] == '['){
                    continue;
                }
                s2.push(args[i])
            }
        }
    }
}

有人能帮我写代码以获得预期输出的有效方法是什么吗？

Answer 1

如何递归解码字符串

您需要定义基本情况和递归情况：

>

递归大小写-我们需要确定开始[和结束括号]的索引，并基于该合约创建一个新字符串。

这就是它的实现方式：

public static String decode(String str) {
    int startOfBrackets = str.indexOf('[');
    
    if (startOfBrackets == -1) { // base case there's no square brackets in the string
        return str;
    }

    int startOfDigits = getFirstDigitsPosition(str);
    int repeatNum = Integer.parseInt(str.substring(startOfDigits, startOfBrackets));
    
    return str.substring(0, startOfDigits) +
        decode(str.substring(startOfBrackets + 1, str.length() - 1)).repeat(repeatNum);
}

public static final Pattern SINGLE_DIGIT = Pattern.compile("\\d");

public static int getFirstDigitsPosition(String str) {
    Matcher matcher = SINGLE_DIGIT.matcher(str);
    if (matcher.find()) {
        return matcher.start();
    }
    return -1;
}

main（）

public static void main(String[] args) {
    System.out.println(decode("1[b]"));
    System.out.println(decode("2[ab]"));
    System.out.println(decode("2[a2[b]]"));
    System.out.println(decode("3[b2[ca]]"));
}

输出：

abab
abbabb
bcacabcacabcaca

Answer 2

其思想是使用两个堆栈，一个用于整数，另一个用于字符。现在，遍历字符串，

1. 每当我们遇到任何数字时，将其推入整数堆栈，如果是任何字母表（a到z）或开括号 (‘[‘), 将其推入字符堆栈。
2. 每当遇到任何关闭括号 (‘]’) 时，从字符堆栈中弹出字符，直到在字符堆栈中找不到打开括号 (‘[‘) 。此外，从整数堆栈中弹出顶部元素，例如n。现在创建一个字符串，重复弹出的字符n次。现在，将字符串的所有字符推入堆栈。

下面是这种方法的实现

        import java.util.Stack;
 
      class Test
      {
        // Returns decoded string for 'str'
        static String decode(String str)
        {
        Stack<Integer> integerstack = new Stack<>();
        Stack<Character> stringstack = new Stack<>();
        String temp = "", result = "";
      
        // Traversing the string
        for (int i = 0; i < str.length(); i++)
        {
            int count = 0;
      
            // If number, convert it into number
            // and push it into integerstack.
            if (Character.isDigit(str.charAt(i)))
            {
                while (Character.isDigit(str.charAt(i)))
                {
                    count = count * 10 + str.charAt(i) - '0';
                    i++;
                }
      
                i--;
                integerstack.push(count);
            }
      
            // If closing bracket ']', pop element until
            // '[' opening bracket is not found in the
            // character stack.
            else if (str.charAt(i) == ']')
            {
                temp = "";
                count = 0;
      
                if (!integerstack.isEmpty())
                {
                    count = integerstack.peek();
                    integerstack.pop();
                }
      
                while (!stringstack.isEmpty() && stringstack.peek()!='[' )
                {
                    temp = stringstack.peek() + temp;
                    stringstack.pop();
                }
      
                if (!stringstack.empty() && stringstack.peek() == '[')
                    stringstack.pop();
      
                // Repeating the popped string 'temo' count
                // number of times.
                for (int j = 0; j < count; j++)
                    result = result + temp;
      
                // Push it in the character stack.
                for (int j = 0; j < result.length(); j++)
                    stringstack.push(result.charAt(j));
      
                result = "";
            }
      
            // If '[' opening bracket, push it into character stack.
            else if (str.charAt(i) == '[')
            {
                if (Character.isDigit(str.charAt(i-1)))
                    stringstack.push(str.charAt(i));
      
                else
                {
                    stringstack.push(str.charAt(i));
                    integerstack.push(1);
                }
            }
      
            else
                stringstack.push(str.charAt(i));
        }
      
        // Pop all the element, make a string and return.
        while (!stringstack.isEmpty())
        {
            result = stringstack.peek() + result;
            stringstack.pop();
        }
      
        return result;
    }
 
    // Driver method
    public static void main(String args[])
    {
        String str = "3[b2[ca]]";
        System.out.println(decode(str));
     } 
    }

输出：BCACABCABCACA