面试测试：实现解码算法

问题描述：

由于在Java中的字符串作为输入3[a]2[bc]写一个函数，因为它不对其进行解码，以便输出应该是为“**aaabcbc**”

Input 3[a]2[bc] -> aaabcbc 
Input 3[2[a]]4[b] -> aaaaabbbb 
Invalid Input 3[4] `enter code here` 
Invalid Input a[3]

我曾尝试以下方法，但不正确地址嵌套元素

String test = "3[a]2[b]5[b]"; 
Map<Character, Integer> map = new HashMap<>(); 

char[] characters = test.toCharArray(); 
for (int i = 0; i < characters.length-1; i++) { 
    if(characters[i]=='['){ 
     if(map.containsKey(characters[i+1])){ 
      int count = map.get(characters[i+1]); 
      map.put(characters[i+1], Character.getNumericValue(characters[i-1])+count); 
     }else{ 
      map.put(characters[i+1], Character.getNumericValue(characters[i-1])); 
     } 

    } 
} 
for (Map.Entry<Character, Integer> c : map.entrySet()) { 
    for (int i = 0; i < c.getValue(); i++) { 
     System.out.printf("%s",c.getKey()); 
    } 
}

这是什么正确的解决方案？

是有可能使用的封装类，如果你观察到的问题进行解码这个问题，仔细的格式，我们可以将它转换为解码器类的对象。作为问题提出 2 [...] 3 [...] 4 [...]

class Decoder{ private int count;// digit example 2[a]3[bc]4[d] the count value will be 2,3,4 private String data; // example a,bc,d private Decoder decoder; // for nested values example 3[2[a]] in this case decoder will be 2[a] }

任何尝试迄今所取得？你为什么不向我们展示？ –

@RahulMahajan：为什么'3 [2 [a]]'预计会是'aaaaa'？它不应该是'3 [2]] - >'3 [aa] - >'aaaaaa'吗？ – Cratylus

帮助你如何？你需要使用什么IDE的建议？您在阅读用户输入时遇到问题吗？你缺少“解码”算法吗？你有某种编译错误？你有一个编译程序会得到某种运行时错误吗？ – azurefrog

答

假设由具有歧义：

对于第二外壳，3 [ 2 [a]] - > 3 [aa] - > aaaaaa

对于第三种情况，如果整数在方括号内 - 用户将通过提供输入和解码。

对于第四情况下，如果是整数那里的拆卸，从输出这样字符串之前方括号之外。

能否请您试试这个代码。我在评论中询问了一些疑问，请澄清他们。

import java.util.Random; 
import java.util.Scanner; 


public class MyClass { 
    private static String code = "3[a]2[bc]"; 

    private static class Pair { 
     int s = 0; 
     int e = 0; 
    } 


    private static Pair getPair() { 
     char[] chars = code.toCharArray(); 
     Pair pair = new MyClass.Pair(); 
     int pointer = 0; 
     for (char c : chars) { 
      if (c == '[') { 
       pair.s = pointer; 
      } 
      if (c == ']') { 
       pair.e = pointer; 
       break; 
      } 
      pointer = pointer + 1; 
     } 
     if (pair.e > (pair.s + 1) || pair.s !=0) { 
      return pair; 
     }else{ 
      return null; 
     } 

    } 

    private static boolean parseInteger(String s) 
    { 
     try { 
      Integer.parseInt(s); 
      return true; 
     } catch(NumberFormatException e) { 
      return false; 
     } 
    } 

    private static void decode(Pair pair){ 
     String pattern = code.substring(pair.s+1, pair.e); 
     String patternCount = code.substring(pair.s-1, pair.s); 
     if(!parseInteger(patternCount)) { 
      code = code.replace(code.substring(pair.s-1, pair.e+1) , ""); 
     }else if(parseInteger(pattern)){ 
      Scanner scanner = new Scanner(System.in); 
      System.out.println("Enter Code for : "+code.substring(pair.s-1, pair.e+1) ); 
      String replacement = ""; 
      pattern = scanner.nextLine(); 
      for(int i = 0 ; i < Integer.parseInt(patternCount);i++){ 
       replacement = replacement + pattern; 
      } 
      code = code.replace(code.substring(pair.s-1, pair.e+1) , replacement); 
     }else{ 
      String replacement = ""; 
      for(int i = 0 ; i < Integer.parseInt(patternCount);i++){ 
       replacement = replacement + pattern; 
      } 
      code = code.replace(code.substring(pair.s-1, pair.e+1) , replacement); 
     } 
    } 

    public static void main(String[] args) { 
     boolean decoding = false; 
     do{ 
      Pair pair = getPair(); 
      decoding = pair != null ? true : false; 
      if(decoding){ 
       decode(pair); 
      } 

     }while(decoding); 

     System.out.println(code); 
    } 
}

答

减少像2[2[a]3[b]]aabbbaabbb到嵌套表达式可通过最内redux的（=可还原表达式）来完成。

因此保持代替嵌套的表格digit[letters]直到没有更多可以减少。

由于这似乎作业只是草图：

String expression = "..."; 
for (;;) { 
    boolean reduced = false; 
    for (int i = 0; i < expression.length(); ++i) { 
     if (found reducable expression) { 
      reduced = true; 
      expression = reduced expression; 
      break; // Otherwise we would need to correct i. 
     } 
    } 
    if (!reduced) { 
     break; 
    } 
}

2 [2 [α] 3 [B]]
2 [AA3并[b]]
2 [aabbb]
aabbbaabbb

基于模式匹配的具体解决方案。

String expression = "..."; 
Pattern reduxPattern = Pattern.compile("(\\d+)\\[(\\pL*)\\]"); 
boolean reducing; 
do { 
    Matcher m = reduxPattern.matcher(expression); 
    reducing = false; 
    StringBuffer sb = new StringBuffer(); 
    while (m.find()) { 
     reducing = true; 
     int n = Integer.parseInt(m.group(1)); 
     String letters = m.group(2); 
     String repetition = String.join("", Collections.nCopies(n, letters)); 
     sb.appendReplacement(repetition); 
    } 
    m.appendTail(sb); 
    expression = sb.toString(); 
} while (reducing);

正如在评论中所讨论的，基于堆栈的解决方案是优越的，但我发现它有点多的工作。

我想我解决了这个堆栈（请检查我的答案），但我会感兴趣的如何处理它与正则表达式 – Cratylus

@Cratylus基于堆栈的解决方案是**更快**，但对于初学者更复杂。此外，错误处理更困难（形成错误的输入）。很高兴看到你提供了这样的答案+1 –

你的答案是基于正则表达式吗？我发现更复杂，因为它需要强大的正则表达式技能。原来的海报不能成为初学者。他说这是他在亚马逊的面试问题 – Cratylus

答

可能有点清洁，但似乎解决问题中提到
更新我已经更新代码，以解决这些问题所指出的@JimMichel 这是考虑到多位数号码，不接受格式不正确的输入。

public static String decode(String in) {  
    Deque<Character> stack = new ArrayDeque<Character>(); 
    Deque<Integer> occurencesStack = new ArrayDeque<Integer>(); 
    StringBuilder result = new StringBuilder(); 
    int brackets = 0; 
    for(int i = 0; i < in.length(); ++i) { 
     Character ch = in.charAt(i); 
     if(ch == '[') { 
      ++brackets; 
      continue; 
     } 
     else if(ch == ']') { 
      --brackets; 
      StringBuilder temp = new StringBuilder();    
      while(!stack.isEmpty()) { 
       Character top = stack.pop(); 
       temp.append(top);    
      } 
      int times = occurencesStack.pop(); 
      if(temp.length() == 0) { 
       temp = new StringBuilder(result); 
       result.setLength(0); 
       for(int j = 0; j < times; ++j) { 
        result.append(temp); 
       }     
      } 
      else { 
       temp.reverse(); 
       for(int j = 0; j < times; ++j) { 
        result.append(temp); 
       } 
       temp.setLength(0);    
      } 
     } 
     else if(Character.isDigit(ch)) {     
      StringBuilder nb = new StringBuilder(); 
      nb.append(ch); 
      while(i < in.length() - 1 && Character.isDigit(in.charAt(i + 1))) { 
       nb.append(in.charAt(i + 1)); 
       ++i;      
      } 
      if(i < in.length() - 1 && in.charAt(i + 1) == ']') { 
       throw new IllegalArgumentException("Invalid sequence"); 
      } 
      occurencesStack.push(Integer.parseInt(nb.toString())); 
     } 
     else if(ch >= 'a' && ch <= 'z') { 
      if(i < in.length() - 1 && in.charAt(i + 1) == '[') { 
       throw new IllegalArgumentException("Invalid sequence"); 
      } 
      stack.push(ch); 

     } 
     else { 
      throw new IllegalArgumentException("Invalid character in sequence "+ch); 
     }   
    } 

    if(brackets != 0) { 
     throw new IllegalArgumentException("Unmatched brackets!"); 
    } 

    return result.toString(); 

}

有趣的做法。你会想要处理像a [4]或者4 [3 [a]'（不平衡括号）或者[4] a ['等等）的错误输入。我还建议你不要假设该数字将是一个数字。 –

@JimMischel：非常好的评论。我更新了代码以包含多位数字和格式错误的输入。似乎是正确的，但我期待着您的评论评论，如果你有时间给我一些 – Cratylus

答

请考虑如果添加几个运算符会发生什么情况。也就是说，"3[a]2[bc]"变成3*[a] + 2*[bc]。如果您将*运算符重新定义为“重复”，并且将+运算符重新定义为“连接”。

使用Shunting yard algorithm，可以将字符串解析为后缀形式：3 a * 2 bc +。调车场容易处理嵌套的表情。例如，您的3[2[a]]4[b]变为3 2 a * * 4 b * +。关于postfix的好处是评估非常简单。

一旦您确信正确生成后缀表单，您可以编写代码来评估后缀表达式（这很容易），也可以修改分流码算法以在输出阶段进行评估。也就是说，不是将操作数和运算符输出到字符串，而是将操作数推送到堆栈上，并且每当输出操作符时，就会弹出堆栈中的操作数，应用操作符并将结果推送到堆栈。所以，你的输出步变为：

if (token is an operand) 
    push token onto stack 
else 
    pop operand2 
    pop operand1 
    result = operand1 <operator> operand2 
    push result onto stack

当你做分析，应该是在栈上一个操作数，并且可以输出。

后缀方法的替代方法是创建一个binary expression tree，然后对其进行评估。另一种选择是编写一个recursive descent parser，尽管除非您最近一直在处理表达式解析，否则在面试过程中您可能会遇到困难时间。

答

我试着用递归这个问题，我觉得这是解读这些正确的做法：

举例：如果我们有一个字符串2 3 [ABC] 2 [XY]则在解码一个水平

1级：3 [ABC] 3 [ABC] 2 [XY]

2级：abcabcabc3 [ABC] 2 [XY]

3级：abcabcabcabcabcabc2 [XY]

4级：abcabcabcabcabcabcxyxy

演示如下代码：

private static void decode(String value) { 
    int startBracket=0; 
    int endBracket=0; 
    int encodedCount=0; 
    int startIndex=0; 
    String result=""; 
    StringBuilder temp=new StringBuilder(); 
    char[] data = value.toCharArray(); 
    for (int i = 0; i < data.length; i++) { 
     if(data[i]=='['){ 
      if(encodedCount==0){ 
       encodedCount=Character.getNumericValue(data[i-1]); 
       startIndex=i; 
      } 

      startBracket++; 
      continue; 
     } 
     if(data[i]==']'){ 
      endBracket++; 
     } 
     if(startBracket==endBracket && startBracket!=0 && endBracket !=0){ 
      System.out.println(encodedCount); 
      result=value.substring(0,startIndex-1);    
      String expandedTarget=value.substring(startIndex+1,i); 
      String remainingEncodedValue = value.substring(i+1,value.length()); 
      System.out.println(expandedTarget); 
      System.out.println(remainingEncodedValue); 

      for (int j = 1; j <= encodedCount; j++) { 
       temp.append(expandedTarget); 
      } 
      if(remainingEncodedValue.length()>1) 
       temp.append(remainingEncodedValue); 

      System.out.println("Decoded Result : "+result + temp.toString()); 
      decode(result + temp.toString()); 
      break; 
     } 
    } 

}

面试测试：实现解码算法

相关推荐