将Markdown转换为HTML算法面试问题-最佳方法？

Question

我最近在一次技术面试中遇到了这个问题，但时间已经用完了。

任务是编写一个Markdown到HTML的转换器。给定以下输入：

This is a paragraph with a soft
line break.

This is another paragraph that has
> Some text that
> is in a
> block quote.

This is another paragraph with a ~~strikethrough~~ word.

生成以下输出：

<p>This is a paragraph with a soft<br />line break.</p>

<p>This is another paragraph that has <br />
  <blockquote>Some text that<br />is in a<br />block quote.</blockquote>
</p>

<p>This is another paragraph with a <del>strikethrough</del> word.</p>

输出的格式并不重要，只要是有效的HTML即可。

我想不出一个好的方法来做这件事。我唯一能想到的就是用两个换行符拆分得到段落，然后迭代每个段落以检查每个特殊符号的存在，并用它的HTML等效项替换。不过，这感觉有点老生常谈，我相信有一种更有条理的方法来解决这类问题，记住这是一个时间限制为30分钟的面试设置。

我欢迎任何建议。

Answer 1

这是我在一小时内的尝试，c#。

如果可能，代码会反复尝试合并相邻的行。为了提高可读性和性能，需要额外的时间对其进行调整。一些额外的错误检查就可以了。

using System;
using System.Collections.Generic;

namespace akMdConverter
{
    class Program
    {
        const string Break = "<br />";

        static void Main(string[] args)
        {
            var md = new string[]
            {
                "This is a paragraph with a soft",
                "line break.",
                "",
                "This is another paragraph that has",
                "> Some text that",
                "> is in a",
                "> block quote.",
                "",
                "This is another paragraph with a ~~strikethrough~~ word."
            };

            md = MergeBlockQuotes(md);
            md = MergeSoftLineBreaks(md);
            md = MergeParagraphs(md);
            ReplaceStrikeThroughs(md);

            foreach (var m in md)
            {
                Console.WriteLine(m);
            }
        }

        static string[] MergeBlockQuotes(string[] md)
        {
            var lines = new List<string>();
            string previousLine = "";

            foreach(string line in md)
            {
                if (line.StartsWith(">"))
                {
                    if (previousLine != "")
                    {
                        previousLine = previousLine + Break + 
                                       line.Substring(1).Trim();
                    }
                    else
                    {
                        previousLine = line.Trim();
                    }
                }
                else
                {
                    if (previousLine != "")
                    {
                        lines.Add(previousLine);
                        previousLine = "";
                    }
                    lines.Add(line);
                }
            }

            return lines.ToArray();
        }

        static string[] MergeSoftLineBreaks(string[] md)
        {
            var lines = new List<string>();
            string previousLine = "";

            foreach (string line in md)
            {
                if ((line == "") || line.StartsWith(">"))
                {
                    if (previousLine != "")
                    {
                        lines.Add(previousLine);
                        lines.Add(line);
                        previousLine = "";
                    }
                    else
                    {
                       lines.Add(line);
                    }
                }
                else
                {
                    if (previousLine != "")
                    {
                        previousLine += Break;
                    }

                    previousLine += line;
                }
            }

            if (previousLine != "")
            {
                lines.Add(previousLine);
            }

            return lines.ToArray();
        }

        static string[] MergeParagraphs(string[] md)
        {
            var lines = new List<string>();
            string previousLine = "";

            foreach (string line in md)
            {
                if (line == "")
                {
                    if (previousLine != "")
                    {
                        lines.Add(Bracket(previousLine, "p"));
                        previousLine = "";
                    }
                    lines.Add("");
                }
                else if (line.StartsWith(">"))
                {
                    if (previousLine != "")
                    {
                        previousLine += Break + "\n";
                    }

                    previousLine += Bracket(line.Substring(1), "blockquote");
                }
                else
                {
                    if (previousLine != "")
                    {
                        previousLine += Break;
                    }

                    previousLine += line;
                }
            }

            if (previousLine != "")
            {
                lines.Add(Bracket(previousLine, "p"));
            }

            return lines.ToArray();
        }

        static string Bracket(string s, string bracket)
        {
            return "<" + bracket + ">" + s.Trim() + "<" + bracket + "/>";
        }

        static void ReplaceStrikeThroughs(string[] md)
        {
            for(int i = 0; i < md.Length; i++)
            {
                string s = md[i];

                int tilde1 = s.IndexOf("~~");
                while (tilde1 >= 0)
                {
                    int tilde2 = s.IndexOf("~~", tilde1 + 2);

                    if (tilde2 > tilde1)
                    {
                        s = s.Substring(0, tilde1) + "<del>" + 
                            s.Substring(tilde1+2, tilde2 - tilde1 - 2) + "</del>" + 
                            s.Substring(tilde2 + 2);
                        tilde1 = s.IndexOf("~~");
                    }
                    else
                    {
                        tilde1 = -1;
                    }
                }

                md[i] = s;
            }
        }
    }
}