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

我有一个Token类的以下字符列表:

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

我的要求是在这个列表中找到括号对。在列表中，括号对分别为:3,16;24日,40;50, 66;23日,76;88104;83127 .

我正在尝试用以下方法做这件事:

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("代替了它。请帮我修复这里的逻辑??

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

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;
}

这是一个经典的面试问题，你可以用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; 
}

您也可以使用正则表达式。可能不会像Vera rind溶液那么快。

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);
 }

EDIT

多亏了Vera rind的建议，我也写了解决方案，为每一个(嵌套级别)与。NET regex风味，正则表达式:

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

演示

捕获first和second组中的成对值。Regex直接匹配对的第一个值，第二个值由正向前看的组捕获。这不是最有效的方法，只是更容易在正则表达式测试器中验证是否匹配正确。

老回答

在其他正则表达式口味(据我所知)没有这样优雅的方式来匹配平衡的可修复结构，所以对于两级括号，这个解决方案仍然有效。静态解决方案在这种情况下更好，但如果整个数据是相同的格式(空格和最大两层括号深度)，也可以使用regex:

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

演示

地点:

(d+)s(s(d+)s) -匹配简单情况:与以下数字匹配括号中的数字:n1 (n2)，值捕获在组1 &2,
(d+)(?=s(s(?:d+s(sd+s)s)+(d+)) -匹配号码以下嵌套括号中的最后一个单独数字:n1 ( x1 (x2) y1 (y2) n2 )，值在第3组&4、

相关内容

最新更新

热门标签：