Parsing in between of brackets

Question

I do parsing of the string in order to find wrapped sub-string inside brackets of the first level. a+(b+(d-g))+g+d, in this case I will need to separate (b+(d-g)). Below is the function which i use for such situations. This function is invoked when i find any opening bracket (. I did profiling of the program and unfortunately it is one of the slowest parts.

Could you please advise how I can optimise the code?

Input

"(b+(d-g))+g+d"
 ^            ^
 |            +--------iterator `end_` points to the end of the expression
 +-------------iterator `tail_` points to beginning of the expression with brackets

Output

string with (b+(d-g))

side-effect

tail_ iterator

"(b+(d-g))+g+d"
         ^            
         |            
         +------iterator `tail_` points to the last correctly closed bracket.

Function

string get_between_brackets(string::iterator& tail_, const string::iterator& end_)
{
    string brackets_content;
    brackets_content.reserve(248); //cannot be longer than that
    if(distance(tail_, end_) >= 2)
    {
        uint br_cnt = 0;
        while(tail_ != end_)
        {
            const auto& chr = *tail_;
            switch(chr)
            {
                case '(': ++br_cnt; break;
                case ')': --br_cnt; break;
            }
            if(br_cnt >= 0)
                brackets_content.push_back(chr);

            if (br_cnt == 0)
                break;

            advance(tail_, 1);
        }
    } else throw std::invalid_argument("brackets tail is not long enough");
    return(brackets_content);
}

It will be parsed on a level above, to two separate items. Function will get (a+b) and (c+d) separately. To be more correct, it will receive (a+b)*(c+d) first, and stop before *, and then will receive (c+d) — Cron Merdek
– Cron Merdek, Commented Apr 22, 2016 at 12:37
The obvious question here would be "why?" This looks a lot like parsing methods I've read about from the early 1950's or so. Reasonably current methods (e.g., shunting yard or recursive descent) render this unnecessary. — Jerry Coffin
– Jerry Coffin, Commented Apr 22, 2016 at 16:00
I agree with @JerryCoffin There is a lot of extra work here. You should look up shunting yard. — Loki Astari
– Loki Astari, Commented Apr 22, 2016 at 17:53

Loki Astari · Accepted Answer · 2016-04-22 18:06:10Z

Design

Your main issue is design. Without looking at the rest of your code to understand how it works this is a bit of a guess. But it feels like you have a design issue with your larger algorithm. There are much better ways to solve this without scanning way ahead in the input stream.

As pointed out by @JerryCoffin above in the comments shunting yard or recursive descent are things you should look into. Personally I think the shunting yard algorithm would give you the most benefit at this point.

Review of Code

Iterators are supposed to be very simple object that carry little state. So passing them by value should not be an issue. Also is there a need to limit this to string::iterator?

string get_between_brackets(string::iterator& tail_, const string::iterator& end_)

I would have done: string get_between_brackets(string::iterator& tail_, const string::iterator& end_)

template<typename I>
std::string get_between_brackets(I tail_, I end_)

That's a great comment.

    brackets_content.reserve(248); //cannot be longer than that

But i don't see that being enforced anywhere.

This switch is broken:

            switch(chr)
            {
                case '(': ++br_cnt; break;
                case ')': --br_cnt; break;
            }

Any character that does not match ')' or '(' leads to undefined behavior. You should must have a default option.

You throw if there is not enough charaters to hold two braces.

else throw std::invalid_argument("brackets tail is not long enough");

But your code works perfectly well if there are no braces in the code. Also I would expect it to throw if the braces were not balanced.

Also rather than building the result slowly character by character as you parse it. It would be simpler (and more effecient) to just remember the beignning and end and return a sub string.

    return std::string(firstBrace, lastBracePlusOne);

Stack Exchange Network

Parsing in between of brackets

Input

Output

side-effect

Function

1 Answer 1

Design

Review of Code

You must log in to answer this question.

Hot Network Questions

Parsing in between of brackets

Input

Output

side-effect

Function

1 Answer 1

Design

Review of Code

You must log in to answer this question.

Related

Hot Network Questions