2
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ What would "(a+b)*(c+d)" output? \$\endgroup\$ – Kenny Lau Apr 22 '16 at 12:34
  • \$\begingroup\$ 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) \$\endgroup\$ – Cron Merdek Apr 22 '16 at 12:37
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Jerry Coffin Apr 22 '16 at 16:00
  • \$\begingroup\$ I agree with @JerryCoffin There is a lot of extra work here. You should look up shunting yard. \$\endgroup\$ – Martin York Apr 22 '16 at 17:53
2
\$\begingroup\$

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);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.