Разбор текстового файла в древовидную структуру данных

Question

У меня есть текстовый файл, который содержит вложенные объекты, и мне нужно сохранить связь между ними.Как бы я их прочитал?Я думаю, что мне нужно использовать структуру данных, такую ​​как дерево, у узлов которого может быть произвольное число дочерних элементов (вроде как n-арное дерево без ограничения 'n').Разбор данных и построение дерева в памяти приводят меня в замешательство.

Данные в текстовом файле структурированы следующим образом:

{
    Element_A (3)
    Element_B (3,4)

    {
        Element_B (6,24)
        Element_A (1)
    }

    {
        Element_A (3)

        {
            Element_A (4)
            Element_B (12,6)
        }

        Element_B (1,4)
    }
}

РЕДАКТИРОВАТЬ: просто чтобы уточнить, открытие / закрытиефигурные скобки заключают в себе один объект и все его дочерние элементы.Element_A и Element_B выше являются частями одного и того же объекта.

Пока что я анализирую весь файл в вектор строк, например:

vector<string> lines;

ifstream file("input.txt");

string s;

while (getline(file, s))
    lines.push_back(s);

и читаю данные из каждой строки, используя что-токак следующее

std::regex re(R"(Element_A \(\s*(\d+)\))");
std::smatch m;

if (std::regex_search(line, m, re) )
{
    // extract data from 'm'
}

РЕДАКТИРОВАТЬ 2: решение Шеффа адаптировано к моей программе.

// Node is defined somewhere at the top of the file
struct Node
{
    int a = 0;
    int b[2] = {0};
    std::vector<Node> children;
};

// this code is inside some function that does the parsing
Node root;
stack<Node*> nodeStack;
nodeStack.push(&root);

for(string line; getline(fin, line);)
{
    line = trim(line); // custom function to remove leading/trailing spaces/tabs (not included in this post for brevity)

    if (line.size() == 0) // empty line (data file might have empty lines for readability)
        continue;
    else if (line.size() == 1) // only one character
    {
        if (line[0] == '{')
        {
            nodeStack.top()->children.push_back(Node());
            nodeStack.push(&nodeStack.top()->children.back());
        }
        else if (line[0] == '}')
        {
            nodeStack.pop();
        }
        else 
            cerr << "Error: Invalid character detected.\n";
    }
    else // at least two characters
    {
        regex reEl_A(R"(Element_A \(\s*(\d+)\))");
        regex reEl_B(R"(Element_B \(\s*(\d+),\s*(\d+)\))");
        smatch m;

        if (std::regex_search(line, m, reEl_A))
        {
            nodeStack.top()->a = std::stoi(m[1]);
            continue;
        }    

        if (std::regex_search(line, m, reEl_B))
        {
            nodeStack.top()->b[0] = std::stoi(m[1]);
            nodeStack.top()->b[1] = std::stoi(m[2]);
            continue;
        }


    }
}

if (nodeStack.empty() || nodeStack.top() != &root)
{
    std::cerr << "ERROR! Data not well balanced.\n";
}

Answer 1

Вот как это может работать:

1. , пока строка чтения не перестала работать, продолжить
2. для
   • "{" вставить новый узел в текущий и установитьэто как текущий узел
   • "}" выдвигает текущий узел и устанавливает его родителя как текущий
   • "Element_A" разбирает значения
   • "Element_B" разбирает значение b
3. goto 1.

Узлы могут хранить своего родителя.В качестве альтернативы, программа чтения файлов может внутренне использовать std::stack для запоминания родителей (что я и сделал в приведенном ниже примере кода).

Пример программы для создания наброска:

#include <cstring>
#include <iomanip>
#include <iostream>
#include <stack>
#include <string>
#include <vector>

struct Node {
  std::pair<int, int> a;
  int b;
  std::vector<Node> children;
  Node(): a(0, 0), b(0) { }
};

std::ostream& operator<<(std::ostream &out, const Node &node)
{
  static unsigned indent = 0;
  out << std::setw(indent) << ""
    << "Node:"
    << " a(" << node.a.first << ", " << node.a.second << "),"
    << " b(" << node.b << ") {\n";
  indent += 2;
  for (const Node &child : node.children) out << child;
  indent -= 2;
  out << std::setw(indent) << ""
    << "}\n";
  return out;
}

void read(std::istream &in, Node &node)
{
  std::stack<Node*> nodeStack;
  nodeStack.push(&node);
  // nodeStack.top() is the (pointer to) current node
  for (std::string line; std::getline(in, line);) {
    if (line.compare(0, strlen("{"), "{") == 0) {
      nodeStack.top()->children.push_back(Node());
      nodeStack.push(&nodeStack.top()->children.back());
    } else if (line.compare(0, strlen("}"), "}") == 0) {
      nodeStack.pop();
    } else if (line.compare(0, strlen("Element_A"), "Element_A") == 0) {
      std::istringstream parser(line.substr(strlen("Element_A")));
      parser >> nodeStack.top()->a.first >> nodeStack.top()->a.second;
    } else if (line.compare(0, strlen("Element_B"), "Element_B") == 0) {
      std::istringstream parser(line.substr(strlen("Element_B")));
      parser >> nodeStack.top()->b;
    } // else ERROR!
  }
  if (nodeStack.empty() || nodeStack.top() != &node) {
    std::cerr << "ERROR! Data not well balanced.\n";
  }
}

const char *const sample =
"{\n"
"Element_A 3\n"
"Element_B 3 4\n"
"{\n"
"Element_B 6 24\n"
"Element_A 1\n"
"}\n"
"{\n"
"Element_A 3\n"
"{\n"
"Element_A 4\n"
"Element_B 12 6\n"
"}\n"
"Element_B 1 4\n"
"}\n"
"}\n";

int main()
{
  std::istringstream in(sample);
  Node root;
  read(in, root);
  std::cout << root;
  return 0;
}

Вывод:

Node: a(0, 0), b(0) {
  Node: a(3, 0), b(3) {
    Node: a(1, 0), b(6) {
    }
    Node: a(3, 0), b(1) {
      Node: a(4, 0), b(12) {
      }
    }
  }
}

Прямая демонстрация на coliru

Примечание:

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

Другой подход к анализатору можно найти, например, в Small Parser из синтаксической диаграммы или, возможно, с использованием std::regexприближение ОП.