c# - 需要算法来制作简单的程序(句子排列)

Question

我真的不明白如何在 C# 上制作一个简单的算法来解决我的问题。所以，我们有一句话:

{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}.

所以，我的程序应该让很多句子看起来像:

Hello my mate.
Hello my m8.
Hello my friend.
Hello my friends.
Hi my mate.
...
Hi-Hi my friends.

我知道，有很多程序可以做到这一点，但我想自己做。当然，它也应该适用于此:

{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}.

Answer 1

更新 我只是对使用正则表达式来解析如此简单的输入不太满意；但我不喜欢其他答案中的手动索引操作丛林。

因此，我将标记化替换为具有两个交替标记状态的基于枚举器的扫描器。输入的复杂性更能说明这一点，并且给人一种“Linqy”的感觉(尽管它确实不是 Linq)。我在文章末尾保留了原始的基于 Regex 的解析器，以供感兴趣的读者使用。

---

这只是必须使用Eric Lippert's/IanG's CartesianProduct Linq extension method解决，其中程序的核心变为:

public static void Main(string[] args)
{
    const string data = @"{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}.";
    var pockets = Tokenize(data.GetEnumerator());

    foreach (var result in CartesianProduct(pockets))
        Console.WriteLine(string.Join("", result.ToArray()));
}

仅使用两个正则表达式(chunks 和 legs)来解析为“pockets”，这就变成了编写 CartesianProduct 的问题到控制台 :) 这是完整的工作代码(.NET 3.5+):

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.Collections.Generic;

namespace X 
{ 
    static class Y 
    {
        private static bool ReadTill(this IEnumerator<char> input, string stopChars, Action<StringBuilder> action)
        {
            var sb = new StringBuilder();

            try 
            {
                while (input.MoveNext())
                    if (stopChars.Contains(input.Current))
                        return true;
                    else
                        sb.Append(input.Current);
            } finally 
            {
                action(sb);
            }

            return false;
        }


        private static IEnumerable<IEnumerable<string>> Tokenize(IEnumerator<char> input)
        {
            var result = new List<IEnumerable<string>>();

            while(input.ReadTill("{", sb => result.Add(new [] { sb.ToString() })) &&
                  input.ReadTill("}", sb => result.Add(sb.ToString().Split('|')))) 
            {
                // Console.WriteLine("Expected cumulative results: " + result.Select(a => a.Count()).Aggregate(1, (i,j) => i*j));
            }

            return result;
        }

        public static void Main(string[] args)
        {
            const string data = @"{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}.";
            var pockets = Tokenize(data.GetEnumerator());

            foreach (var result in CartesianProduct(pockets))
                Console.WriteLine(string.Join("", result.ToArray()));
        }

        static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) 
        { 
            IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
            return sequences.Aggregate( 
                    emptyProduct, 
                    (accumulator, sequence) =>  
                    from accseq in accumulator  
                    from item in sequence  
                    select accseq.Concat(new[] {item}));                
        }
    }
}

---

基于旧正则表达式的解析:

static readonly Regex chunks = new Regex(@"^(?<chunk>{.*?}|.*?(?={|$))+$", RegexOptions.Compiled);
static readonly Regex legs = new Regex(@"^{((?<alternative>.*?)[\|}])+(?<=})$", RegexOptions.Compiled);

private static IEnumerable<String> All(this Regex regex, string text, string group)
{
    return !regex.IsMatch(text) 
                ? new [] { text } 
                : regex.Match(text).Groups[group].Captures.Cast<Capture>().Select(c => c.Value);
}

public static void Main(string[] args)
{
    const string data = @"{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}.";
    var pockets = chunks.All(data, "chunk").Select(v => legs.All(v, "alternative"));

其余不变