How to parse a structured format?

Question

I've a string and I'd like to parse the one on structure blocks.

So, structure in string like this:

if(true) {
    if(true) {
        if(true) {}
    }
}
if(true) {
    if(true) {
        if(true) {}
    }
}

And I'd like to split the one on parent blocks like this:

if(true) {
    if(true) {
        if(true) {}
    }
},

if(true) {
    if(true) {
        if(true) {}
    }
}

My code:

string condition = 
"if(true) {\
    if(true) {\
        if(true) {}\
    }\
}\
if(true) {\
    if(true) {\
        if(true) {}\
    }\
}";

string item; 
stringstream stream(condition);
vector<string> array;

//splitting on sections
while (getline(stream, item, '}')) {
    array.push_back(item + "}");
}

for(int i = 0; i < array.size(); i++) {
    cout << i << array[i] << endl;
}

Result:

0 if(true) { if(true) { if(true) {}
1   }
2 }
3 if(true) { if(true) { if(true) {}
4   }
5 }

But need:

0 if(true) { if(true) { if(true) {} } }
1 if(true) { if(true) { if(true) {} } }

How to detect and parse the parent blocks more correctly or tell an algorithm?

It seems like you want to split a string? If that's true take a look here at some solutions: http://stackoverflow.com/questions/236129/how-to-split-a-string-in-c — , Dec 25 '11 at 19:35
Thanks, I already saw that post, but I've a slightly different problem. I don't understand an algorithm to parse. — Alexander Abashkin, Dec 25 '11 at 19:49
@AlexanderGuiness: You might want to look into Boost.Spirit for some high-functionality parsing. — GManNickG, Dec 25 '11 at 19:50
@GMan, I don't want to install additional libraries for this one and would like to do a simple algorithm. — Alexander Abashkin, Dec 25 '11 at 19:54

score 2 · Accepted Answer · answered Dec 25 '11 at 20:17

You'll need to keep a count of your current depth. I find the best parsers are iterator-based, so that's what I'll show here. std::getline isn't very useful for parsing except with the very simplest of formats.

Completely untested code:

std::vector<std::string> vec;

int depth = 0;
std::string::const_iterator first = condition.begin(),
                            last = condition.end(),
                            iter = first;

for(;;)
{
    iter = std::find_if(iter, last,
                        [](char ch) { return ch == '{' || ch == '}'; });

    if(iter == last)
    {
        if(depth)
        {
            throw std::runtime_error("unclosed block found.");
        }

        break;
    }

    if(*iter == '{')
    {
        ++depth;
        ++iter;
    }
    else if(*iter == '}' && !--depth)
    {
        v.push_back(std::string(first, ++iter));
        first = iter;
    }
    else
    {
        ++iter;
    }
}

How to parse a structured format?

1 Answers1