GrabDuck

C# Вложенность при парсинге скобок

:

Поскольку это выглядит как учебное задание, давайте-ка я покажу вам, как делается recursive descent parser для таких штук.

Для начала, определим вашу грамматику (вы знаете БНФ, да?):

text ::= clause-list <конец> # текст состоит из списка клауз
clause-list ::= { clause }  # список клауз - ноль, одна или более клауз
clause ::= letter | group   # клауза - буква или группа в скобках
letter ::= <что угодно кроме скобок>
group ::= '(' clause-list ')'  # группа в скобках - открывающая скобка,
                               # список клауз и закрывающая скобка

Теперь, структуры данных. Тут всё просто.

class Clause { }
class Letter : Clause { public char Value; }
class Group : Clause { public List<Clause> Clauses = new List<Clause>(); }

Для списка клауз будем использовать List<Clause>.

Я не буду писать токенизацию, для вашего случая она не нужна, а если хочется, можно посмотреть как это делается тут или тут. У вас текст можно считать сразу токенизированным.

Начинаем реализовывать разбор в согласии с написанной нами грамматикой. На вход будет подаваться строка и текущий индекс в ней. (Kрасивее было бы передавать IEnumerator<char>, но это отвлекло бы от задачи.) Методы будут пытаться разобрать фрагмент строки, и при удачном разборе продвигать текущий индекс.

// letter ::= <что угодно кроме скобок>
Letter TryParseLetter(string s, ref int currIdx)
{
    if (currIdx >= s.Length) // если строка закончилась, выход
        return null;
    var letter = s[currIdx]; // проверим текущую букву
    if (letter == '(' || letter == ')') // если это скобка - не наш случай
        return null;
    currIdx++;  // иначе наш, продвигаем индекс
    return new Letter() { Value = letter }; // и возвращаем результат
}

Пока всё просто? Теперь список в скобках. Он чуть-чуть сложнее.

// group ::= '(' clause-list ')'
Group TryParseGroup(string s, ref int currIdx)
{
    if (currIdx >= s.Length) // если строка закончилась, выход
        return null;
    var letter = s[currIdx]; // проверяем текущую букву
    if (letter != '(') // не скобка? на выход!
        return null;
    // а если скобка, это наш случай
    currIdx++; // продвигаемся вперёд от скобки
    var innerClauses = ParseClauseList(s, ref currIdx); // разбираем список клауз
    // за ним должна быть скобка
    // если нет, это ошибка во входном тексте, сообщаем
    if (currIdx >= s.Length || s[currIdx] != ')')
        throw new FormatException($"Expected closing parenthesis at position {currIdx}");
    currIdx++; // переходим к следующей букве и возвращаем результат
    return new Group() { Clauses = innerClauses };
}

Тоже ничего сложного, всё в согласии с грамматикой.

Одна клауза — это Letter или Group. Имплементируем!

// clause ::= letter | group
Clause TryParseClause(string s, ref int currIdx)
{
    // если TryParseLetter вернёт null, пробуем ещё TryParseGroup
    return (Clause)TryParseLetter(s, ref currIdx) ??
                TryParseGroup(s, ref currIdx);
}

Теперь список клауз. Просто пытаемся распарсить клаузу, пока возможно.

// clause-list ::= { clause }
List<Clause> ParseClauseList(string s, ref int currIdx)
{
    List<Clause> result = new List<Clause>();
    while (true)
    {
        Clause clause = TryParseClause(s, ref currIdx);
        if (clause == null) // не нашли? возвращаем всё, что накопили
            break;
        result.Add(clause); // нашли? добавляем к накопленному
    }
    return result;
}

Ну и внешняя часть, которая разбирает весь текст.

// text ::= clause-list <конец>
List<Clause> Parse(string s)
{
    int currIdx = 0;
    var clauses = ParseClauseList(s, ref currIdx); // получаем список
    if (currIdx != s.Length) // если в хвосте ещё что-то есть, непорядок
        throw new FormatException($"Unrecognized character at position {currIdx}");
    return clauses; // список и есть наш результат
}

Отлично, у нас есть разбор строки в объектную структуру (синтаксическое дерево). Для его вывода, как и для всякой саморекурсивной структуры, стоит применять рекурсивную функцию обхода. Я напишу классический вывод с отступами, чтобы не давать вам полное решение, а вы подумайте, как это переделать для вашего случая.

void PrintClauseRec(Clause clause, int indentLevel)
{
    Console.Write(new string(' ', 4 * indentLevel)); // индентация
    switch (clause)
    {
    case Letter l:
        Console.WriteLine(l.Value); // если буква, её и печатаем
        break;
    case Group g:
        Console.WriteLine("Group:"); // если группа, печатаем слово "Group"
        foreach (var innerClause in g.Clauses) // а затем все элементы группы
            PrintClauseRec(innerClause, indentLevel + 1);
        break;
    default: // а если непонятно что, то это какой-то баг у нас
        throw new Exception("Unknown clause type");
    }
}

Для вот такого тестового прогона:

var input = "a(b(c)(d))";
var clauses = Parse(input);
foreach (var clause in clauses)
    PrintClauseRec(clause, 0);

получаем вывод:

a
Group:
    b
    Group:
        c
    Group:
        d