Find the parenthesis pair () within a list of parenthesis

Question

I have a list of following characters of class Token:

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

My requirement is to find the pair of parenthesis within this list. In the list, the pairs of parenthesis are: 3,16; 24,40; 50,66; 23,76; 88,104; 83,127.

I'm trying to do this with following approach:

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

I'm stuck in finding the position of "23 (" because there is another opening parenthesis in the list and it replaces it with "24 (". Kindly help me to fix the logic here??

Answer 1

I've not tested it but this should solve the problem:

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 2

This is a classic interview qustion, you solve it with a 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 3

You can also use regex. Probably it's not too fast like Vera rind solution.

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

EDIT

Thanks to Vera rind suggestion, I wrote also solution to do that for every (nested level) with NET regex flavour, with regular expression:

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

DEMO

it captures pairs of values in groups first and second. Regex directly match first value of pairs, the second one is captured by group in positive lookahead. It is not the most efficient way, just easier to verified in regex tester if it match properly.

OLD ANSWER

In other regex flavours (as far I know) there is no such elegant way to match balanced repatable structures, so for two level of brackets, this solution still works. The stact solution is better in this case, but if whole data is in same format (spacing and max two level paratheses depth) it is also possible with regex:

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

DEMO

Where:

• (\d+)\s\(\s(\d+)\s\) - match simple case: namber with following number in brackets: n1 (n2) , values are captured in groups 1 & 2,
• (\d+)(?=\s\(\s(?:\d+\s\(\s\d+\s\)\s)+(\d+)) - match number with last lonely number in following nested brackets: n1 ( x1 (x2) y1 (y2) n2 ), values are captured in groups 3 & 4,

However it will chage list order.