递归解析字符串

Question

递归解析字符串

5

我正在尝试从一个字符串中提取信息 - 具体来说，是一个Fortran格式化字符串。该字符串的格式如下：

F8.3, I5, 3(5X, 2(A20,F10.3)), 'XXX'

使用逗号分隔格式字段，并在方括号内包含格式化组，方括号前面的数字表示格式化模式连续重复的次数。因此，上述字符串展开为：

F8.3, I5, 5X, A20,F10.3, A20,F10.3, 5X, A20,F10.3, A20,F10.3, 5X, A20,F10.3, A20,F10.3, 'XXX'

我正在尝试用C#编写一个可以扩展符合该模式的字符串的程序。我已经开始使用大量的switch和if语句，但是想知道我是否走错了路？

我想知道一些正则表达式专家是否认为正则表达式可以一次性解决这个问题？我对正则表达式一无所知，但如果它可以解决我的问题，我考虑花时间学习如何使用它们……另一方面，如果正则表达式无法解决这个问题，那么我宁愿花时间研究另一种方法。

- yu_ominae

4个回答

0

我建议使用递归方法，就像下面的示例一样（未经测试）：

ResultData Parse(String value, ref Int32 index)
{
    ResultData result = new ResultData();
    Index startIndex = index; // Used to get substrings

    while (index < value.Length) 
    {
        Char current = value[index];

        if (current == '(')
        {
            index++;
            result.Add(Parse(value, ref index));
            startIndex = index;
            continue;
        }
        if (current == ')')
        {
            // Push last result
           index++;
           return result;
        }

        // Process all other chars here
    }

    // We can't find the closing bracket
    throw new Exception("String is not valid");
}

你可能需要修改代码的某些部分，但这种方法是我在编写简单编译器时使用的。虽然它还没有完成，但只是一个例子。

- Felix K.

我最终做了你建议的那样，它起作用了。虽然不是递归的，但是从最高层嵌套到最低层都可以工作。看起来很有效，感谢你的建议。 - yu_ominae

0

今天最终重写了这个程序。结果发现可以在一个方法中完成：

private static string ExpandBrackets(string Format)
    {
        int maxLevel = CountNesting(Format);

        for (int currentLevel = maxLevel; currentLevel > 0; currentLevel--)
        {
            int level = 0;
            int start = 0;
            int end = 0;

            for (int i = 0; i < Format.Length; i++)
            {
                char thisChar = Format[i];
                switch (Format[i])
                {
                    case '(':
                        level++;
                        if (level == currentLevel)
                        {
                            string group = string.Empty;
                            int repeat = 0;

                            /// Isolate the number of repeats if any
                            /// If there are 0 repeats the set to 1 so group will be replaced by itself with the brackets removed
                            for (int j = i - 1; j >= 0; j--)
                            {
                                char c = Format[j];
                                if (c == ',')
                                {
                                    start = j + 1;
                                    break;
                                }
                                if (char.IsDigit(c))
                                    repeat = int.Parse(c + (repeat != 0 ? repeat.ToString() : string.Empty));
                                else
                                    throw new Exception("Non-numeric character " + c + " found in front of the brackets");
                            }
                            if (repeat == 0)
                                repeat = 1;

                            /// Isolate the format group
                            /// Parse until the first closing bracket. Level is decremented as this effectively takes us down one level
                            for (int j = i + 1; j < Format.Length; j++)
                            {
                                char c = Format[j];
                                if (c == ')')
                                {
                                    level--;
                                    end = j;
                                    break;
                                }
                                group += c;
                            }

                            /// Substitute the expanded group for the original group in the format string
                            /// If the group is empty then just remove it from the string
                            if (string.IsNullOrEmpty(group))
                            {
                                Format = Format.Remove(start - 1, end - start + 2);
                                i = start;
                            }
                            else
                            {
                                string repeatedGroup = RepeatString(group, repeat);
                                Format = Format.Remove(start, end - start + 1).Insert(start, repeatedGroup);
                                i = start + repeatedGroup.Length - 1;
                            }
                        }
                        break;

                    case ')':
                        level--;
                        break;
                }
            }
        }

        return Format;
    }

CountNesting() 返回格式语句中括号嵌套的最高级别，但也可以作为参数传递给该方法。 RepeatString() 只是将字符串重复指定次数，并将其替换为格式字符串中的括号组。

- yu_ominae

0

个人建议使用递归函数。每次遇到左括号时，调用该函数以解析该部分。我不确定是否可以使用正则表达式匹配递归数据结构。

- Jonathan

这会匹配 3(...(...)，对吧？ - duedl0r

是的，你说得对。我编辑了我的答案，删除了不正确的正则表达式。我已经阅读过正则表达式并不是匹配递归结构的好工具。也许，可以编写一个函数，逐个字符地检查字符串并计算括号数，而不是使用正则表达式。一旦关闭括号的数量与开放括号的数量相匹配，就可以得到子字符串。 - Jonathan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Huusom · Accepted Answer

这应该可以用正则表达式完成 :) 我已经扩展了我的以前的示例，并且它在你的示例中很好地测试。

// regex to match the inner most patterns of n(X) and capture the values of n and X.
private static readonly Regex matcher = new Regex(@"(\d+)\(([^(]*?)\)", RegexOptions.None);

// create new string by repeating X n times, separated with ','
private static string Join(Match m)
{
    var n = Convert.ToInt32(m.Groups[1].Value); // get value of n
    var x = m.Groups[2].Value; // get value of X
    return String.Join(",", Enumerable.Repeat(x, n));
}

// expand the string by recursively replacing the innermost values of n(X).
private static string Expand(string text)
{
    var s = matcher.Replace(text, Join);
    return (matcher.IsMatch(s)) ? Expand(s) : s;
}

// parse a string for occurenses of n(X) pattern and expand then.
// return the string as a tokenized array.
public static string[] Parse(string text)
{
    // Check that the number of parantheses is even.
    if (text.Sum(c => (c == '(' || c == ')') ? 1 : 0) % 2 == 1)
        throw new ArgumentException("The string contains an odd number of parantheses.");

    return Expand(text).Split(new[] { ',', ' ' }, StringSplitOptions.RemoveEmptyEntries);
}