在括号列表中查找括号对 ()

Question

我有一个 class 令牌的以下字符列表：

3 ( 16 ) 23 ( 24 ( 40 ) 50 ( 66 ) 76 ) 83 ( 88 ( 104 ) 127 )

我的要求是在此列表中找到一对括号。在列表中，括号对是：3,16； 24,40； 50,66； 23,76； 88,104； 83,127.

我正在尝试使用以下方法来做到这一点：

public static Dictionary<int,int> GetPair(List<Token> data)
{
     List<Token> token = data;
     var pair = new Dictionary<int, int>();

     int startIndex = -1;
     int currentPosition = -1;
     int finalIndex = -1;

     foreach (var item in token)
     {
         if (item.TokenValue == "(" && (currentPosition == -1 || currentPosition>startIndex) )
         {
             startIndex = item.TokenID;
             currentPosition = startIndex;
         }
         if (item.TokenValue == ")")
         {
             finalIndex = item.TokenID;
             currentPosition = finalIndex;
             pair.Add(startIndex, finalIndex);
         }               
     }   

     return pair;
}

public class Token
{
    public int TokenID { get; set; }
    public string TokenValue { get; set; }
}

我一直在寻找“23 (”的位置，因为列表中还有另一个左括号，它用“24 (”替换了它。请帮我修正这里的逻辑？？

Answer 1

这是一道经典的面试题，你用一道Stack:

public static Dictionary<int,int> GetPair(List<Token> data)
{
    Stack<Token> stacken = new Stack<Token>();
    var pair = new Dictionary<int, int>();
    Token temp = new Token();

    foreach (char A in data)
    {
         if (item.TokenValue == "(" )
         {
              stacken.Push(A);
         }

         if (item.TokenValue == ")" )
         {
             if (stacken.Last() == '(')
             {
                  temp = stacken.Pop();
                  pair.Add(temp.TokenID,item.TokenID)
             }
             else
             {
                  stacken.Push(A);
             }
         }
    }

    return pair; 
}

Answer 2

我没有测试过，但这应该可以解决问题：

public static Dictionary<int,int> GetPair(List<Token> data)
{
    var pair = new Dictionary<int, int>();

    var stack = new Stack<Token>();
    foreach (var item in token)
    {
        if (item.TokenValue == "(")
        {
            stack.Push(item);
            continue;
        }

        if (item.TokenValue == ")")
        {
            var starting = stack.Pop();
            pair.Add(starting.TokenId, item.TokenId);
        }
    }

    return pair;
}

Answer 3

您也可以使用正则表达式。可能它不像维拉外皮溶液那样太快。

string s = "3 ( 16 ) 23 ( 24 ( 40 ) 50 ( 66 ) 76 ) 83 ( 88 ( 104 ) 127 )".Replace(" ", string.Empty);
Regex regex = new Regex(@"(([0-9]+)\([0-9]+\))");
Regex regexNumber = new Regex(@"[0-9]+");
Match match = regex.Match(s);
List<Tuple<int, int>> pairs = new List<Tuple<int, int>>();
while (match.Success)
{
     var pairNumber = regexNumber.Matches(match.Value);
     if (pairNumber.Count == 2)
     {
         var newPair = new Tuple<int, int>(int.Parse(pairNumber[0].Value), int.Parse(pairNumber[1].Value));
         pairs.Add(newPair);
     }

     // remove last parse
     s = s.Replace(match.Value, string.Empty);
     match = regex.Match(s);
 }

Answer 4

编辑

感谢 Vera rind 的建议，我还编写了解决方案，以使用 NET 正则表达式和正则表达式为每个（嵌套级别）执行此操作：

(?<first>\d+)(?=\s\(\s(?<second>\d+)\s\))|(?<first>\d+)\s(?=\(\s(?:(?:[^()]|(?<Open>\()|(?<Content-Open>\)))+(?(Open)(?!))\s(?<second>\d+)))

DEMO

它捕获组 first 和 second 中的值对。正则表达式直接匹配 pairs 的第一个值，第二个值由 group in positive lookahead 捕获。这不是最有效的方法，如果匹配正确，在正则表达式测试器中更容易验证。

旧答案

在其他正则表达式中（据我所知）没有这种优雅的方式来匹配平衡的可重复结构，所以对于两级括号，这个解决方案仍然有效。在这种情况下，stact 解决方案更好，但如果整个数据采用相同格式（间距和最大两级平行深度），则也可以使用正则表达式：

(\d+)\s\(\s(\d+)\s\)|(\d+)(?=\s\(\s(?:\d+\s\(\s\d+\s\)\s)+(\d+))

DEMO

其中：

(\d+)\s\(\s(\d+)\s\) - 匹配简单的大小写：名称与以下括号中的数字：n1 (n2)，值在第 1 组和第 2 组中捕获，
(\d+)(?=\s\(\s(?:\d+\s\(\s\d+\s\)\s)+(\d+)) - 匹配数字以下嵌套括号中的最后一个孤独数字：n1 ( x1 (x2) y1 (y2) n2 )，值在第 3 组和第 4 组中捕获，

但是它会改变列表顺序。

在括号列表中查找括号对 ()

Find the parenthesis pair () within a list of parenthesis

c#

regex

ordereddictionary

string-comparison

string-matching