Найдите пару скобок () в списке скобок

У меня есть список следующих символов класса Token:

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 («». Пожалуйста, помогите мне исправить логику здесь ??


c# regex string-matching ordereddictionary string-comparison
person iSahilSharma    schedule 15.09.2015    source источник
comment
@YaelBS это редактирование не является правильным редактированием.   -  person Thomas Ayoub    schedule 15.09.2015
comment
Так почему вы одобрили редактирование?   -  person Yael    schedule 15.09.2015
comment
Любое из решений работает для вас?   -  person Yael    schedule 15.09.2015

Ответы (4)


arrow_upward
3
arrow_downward

Я не тестировал это, но это должно решить проблему:

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;
}
person Sebastian Schumann    schedule 15.09.2015
comment
Понятия не имею, но похоже, что вы добавляете только пары верхнего уровня, а не вложенные. - person Rawling; 15.09.2015
comment
Это работало и для вложенных. Спасибо за код. - person iSahilSharma; 15.09.2015
comment
@iSahilSharma Нет проблем. У меня не было достаточно времени, чтобы проверить это. Не забывайте отмечать любой пост как ответ. - person Sebastian Schumann; 15.09.2015

arrow_upward
1
arrow_downward

Это классический вопрос на собеседовании, вы решаете его с помощью 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; 
}
person Yael    schedule 15.09.2015

arrow_upward
0
arrow_downward

Вы также можете использовать регулярное выражение. Возможно, это не так быстро, как раствор Веры Ринд.

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);
 }
person Jiri Sykora    schedule 15.09.2015

arrow_upward
0
arrow_downward

ИЗМЕНИТЬ

Благодаря предложению Веры Ринд, я также написал решение, позволяющее сделать это для каждого (вложенного уровня) с использованием регулярного выражения NET с регулярным выражением:

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

ДЕМО

он фиксирует пары значений в группах first и second. Регулярное выражение напрямую соответствует первому значению пары, второе значение захватывается группой при положительном просмотре вперед. Это не самый эффективный способ, просто его легче проверить в тестере регулярных выражений, если он правильно соответствует.

СТАРЫЙ ОТВЕТ

В других вариантах регулярных выражений (насколько я знаю) нет такого элегантного способа сопоставления сбалансированных повторяемых структур, поэтому для двухуровневых скобок это решение все еще работает. В этом случае решение stact лучше, но если все данные имеют одинаковый формат (интервал и максимальная глубина двухуровневых паратезов), это также возможно с регулярным выражением:

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

ДЕМО

Где:

  • (\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,

Однако это изменит порядок списка.

person m.cekiera    schedule 15.09.2015
comment
Вы можете использовать регулярное выражение для любой глубины: ([^()]|(?<open>[(])|(?<close-open>[)]))+(?(open)(?!)) Хорошее объяснение здесь и здесь. Проблема в том, что исходные данные это не строка. - person Sebastian Schumann; 15.09.2015
comment
@Verarind, но когда я пытаюсь использовать регулярное выражение с RegexHero или RegexStorm, возвращается неверный результат. И как он должен работать с сопоставлением шаблона n1 ( x1 (x2) y1 (y2) n2 )? - person m.cekiera; 15.09.2015
comment
@mcekiera Мое регулярное выражение - всего лишь подсказка, а не решение. Он использует определения групп балансировки для соответствия соответствующую скобку. Это может быть использовано для поиска совпадающих пар. Указанное регулярное выражение не распознает числа между скобками, или, лучше сказать, связь между числом и скобками теряется. Подсказка для вас на случай, если вам понадобится что-то подобное. - person Sebastian Schumann; 15.09.2015
comment
@Verarind Хорошо, я понимаю, это действительно интересная и уникальная возможность регулярного выражения NET. Спасибо за комментарий, извините за непонимание - person m.cekiera; 15.09.2015
comment
@Verarind Я узнал, как это работает, и изменил свой ответ, еще раз большое спасибо за подсказку, это действительно ценный урок для меня. - person m.cekiera; 15.09.2015