java - 递归文本转换

Question

鉴于以下情况:

  > This is level 1
  > This is level 2
  >> This is level 2.1
  >> This is level 2.2
  >>> This is level 2.2.1
  >>> This is level 2.2.2
  > This is level 3

How would you convert that text to XHTML, without a parser library such as ANTLR? That is:

  <ul>
  <li>This is level 1</li>
  <li>This is level 2
    <ul>
    <li>This is level 2.1</li>
    <li>This is level 2.2
      <ul>
      <li>This is level 2.2.1</li>
      <li>This is level 2.2.2</li>
      </ul>
    </li>
    </ul>
  </li>
  <li>This is level 3</li>
  </ul>

我已经尝试过递归和迭代算法。麻烦的部分是关闭从深度 3 (2.2.2) 到深度 1 (3) 的 ul 标签。

解决方案

下面的代码解决了这个问题。当每个级别代表一个数字而不是一行文本时，标记为正确的解决方案是正确的。输出中的新行是为了便于人类阅读，但由于 (X)HTML 是计算机可读的，因此它们已从下面的代码中删除。

public String transform( String source ) {
  // Level 0 means no >, level 1 for one >, etc.
  //
  int currentLevel = 0;
  int nextLevel = 0;

  StringBuilder sb = new StringBuilder( 512 );

  // Split source on newlines.
  //
  String[] lines = source.split( "\\r?\\n" );

  for( String line: lines ) {
    int indents = line.lastIndexOf( ">" );

    if( indents < 0 ) {
      continue;
    }

    String content = line.substring( indents + 1 ).trim();

    nextLevel = indents + 1;

    if( nextLevel == currentLevel ) {
      sb.append( "</li><li>" );
    }
    else if( nextLevel > currentLevel ) {
      sb.append( "<ul><li>" );
    }
    else if( nextLevel < currentLevel ) {
      for( int i = 0; i < currentLevel - nextLevel; i++ ) {
        sb.append( "</li></ul>" );
      }
      sb.append( "</li><li>" );
    }

    sb.append( content );

    currentLevel = nextLevel;
  }

  // Close the remaining levels.
  //
  for( int i = 0; i < currentLevel; i++ ) {
    sb.append( "</li></ul>" );
  }

  return sb.toString();
}

Answer 1

这是一个基于 Pavel 算法的示例实现

class listCreator {

    public String createList(String source) {
        int currentLevel = 0; //Level 0 means beginning, level 1 means a single > was present and so on
        int nextLevel = 0;
        StringBuilder sb = new StringBuilder();
        //Assumes source is to be split on newlines
        String[] tmp = source.split("\n");
        for (String t: tmp) {
            //Needs validation, if source is not what we expect it'll blow up...
            //We are expecting a number of > followed by a space
            String[] levelContent = t.split(" ");
            nextLevel = levelContent[0].lastIndexOf(">") + 1;

            if (nextLevel == currentLevel) {
                sb.append("</li>\n<li>");
                sb.append(levelContent[1]);
            } else if (nextLevel > currentLevel) {
                sb.append("<ul>\n<li>");
                sb.append(levelContent[1]);
            } else if (nextLevel < currentLevel) {
                for (int i = 0; i < currentLevel-nextLevel; i++) {
                    sb.append("</li>\n</ul>\n");
                }
                sb.append("</li>\n<li>");
                sb.append(levelContent[1]);
            }

            currentLevel = nextLevel;
        }
        //Close up remaining levels
        for (int i=0; i < currentLevel; i++) {
            sb.append("</li>\n</ul>\n");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String source1 = "> 1\n> 2\n>> 2.1\n>> 2.2\n>>> 2.2.1\n>>> 2.2.2\n> 3\n";
        String source2 = "> 1\n> 2\n>> 2.1\n>> 2.0.1\n>>> 2.0.1.2\n>> 2.2\n>>> 2.2.1\n>>> 2.2.2\n> 3\n";
        listCreator lc = new listCreator();
        System.out.println(lc.createList(source1));
        System.out.println(lc.createList(source2));
    }

}