5
\$\begingroup\$

I need to process an array of number pairs. Here are the constraints on the pairs:

  1. The second item may be missing, in this case 0 will be used as second item - - 38 is the same as 38,0
  2. The pair items may be a number, or a range - 149,0, 149,[3,7], [5,9],11, [3,6],[2,9], [4,8]
  3. The range may be inclusive or exclusive - [8,11], [3,9), (4,10]
  4. There may be any number of spaces between items - [ 3 , 6 ]
  5. The second item may be >=0, this is the same as bullet #1 - 36, >=0

Why do I need the ranges? If I have, say, 149,[3,5], then I need to have 3 pairs - 149,3, 149,4, 149,5. If I have [8,10], then the pairs are 8,0, 9,0, 10,0. You get the idea.

I wrote a regex to get the items from the input. I think regex is not the best choice here, maybe I'll change it. Here's my program:

#include <string>
#include <regex>
#include <vector>

using intRange = std::pair<int, int>;
std::vector<std::pair<int, int>> pairs;

intRange getRange(const std::string &value1, const std::string &value2, const std::string &value3)
{
    if (value1.length())
        return intRange(std::stoi(value1), std::stoi(value1));

    if (value2.length() && value3.length())
    {
        const short startIncrement = value2.front() == '(' ? 1 : 0;
        const short endDecrement = value3.back() == ')' ? 1 : 0;

        // remove the parentheses
        std::string val2 = value2, val3 = value3;
        val2.replace(0, 1, std::string{});
        val3.pop_back();

        return intRange(std::stoi(val2) + startIncrement, std::stoi(val3) - endDecrement);
    }

    return {};
}

bool parseRange(const std::string &input)
{
    pairs.clear();

    static const std::regex rx{ R"numrange(\s*(?:(\s*\d+\s*)|([\[\(]\s*\d+)\s*,\s*(\d+\s*[\]\)]))(?:,\s*(?:(\d+\s*)|\s*([\[\(]\d+)\s*,\s*(\d+\s*[\]\)])|(\s*>\s*=\s*0\s*)))?\s*)numrange" };

    std::smatch matches;
    if (std::regex_match(input, matches, rx))
    {
        // if 1st (4th) match group exists, first (second) item is a single number
        // if 2nd and 3rd (5th and 6th) match groups exist, first (second) item is a range
        // if neither 4th nor 5th and 6th groups exist, then second item isn't specified, and default value (0) is used 
        auto firstRange = getRange(matches[1], matches[2], matches[3]);
        auto secondRange = getRange(matches[4], matches[5], matches[6]);

        // save all pairs
        for (auto first = firstRange.first; first <= firstRange.second; ++first)
            for (auto second = secondRange.first; second <= secondRange.second; ++second)
                pairs.emplace_back(first, second);
    }
    else
        return false;

    return true;
}

int main()
{
    std::vector<std::string> inputs = {
        "38",
        "149,0",
        "149,[3,7]",
        "[5,9],11",
        "[3,6],[2,9]",
        "[4,8]",
        "[3,9)",
        "(4,10]",
        "[ 3 , 6 ]",
        "36, >= 0"
    };

    for (const auto &input : inputs)
    {
        if (parseRange(input))
        {
            std::cout << "input: " << input << '\n';
            for (const auto &pair : pairs)
                std::cout << pair.first << ", " << pair.second << '\n';
            std::cout << "-------------------\n";
        }
        else
        {
            std::cout << "Error occurred.";
            return -1;
        }
    }

    std::cin.get();
}

I think there is room for improvement for this code. Please let me know where I can improve. Thanks.

\$\endgroup\$
  • \$\begingroup\$ You say you need to process an array but seemingly match on a string. Is your original input an array but you flatten it into a string? \$\endgroup\$ – yuri Mar 23 at 6:47
  • \$\begingroup\$ no it's an array, i just presented the method for a single element. i'm running a simple for loop on the array \$\endgroup\$ – user3132457 Mar 23 at 8:25
  • \$\begingroup\$ Might be good to post the entire source code. \$\endgroup\$ – yuri Mar 23 at 8:35
  • \$\begingroup\$ I've only omitted the for loop on the array. Another thought is that, I can have a separate regex for each of those cases. don't know if it's more efficient, though. \$\endgroup\$ – user3132457 Mar 23 at 8:57
  • \$\begingroup\$ IMO It'd be nice to have the full code along with an example input as it makes it easier to reason about the code and architecture at large. See also SSCCE \$\endgroup\$ – yuri Mar 23 at 9:23
2
\$\begingroup\$

Just answering this question since it is unanswered. Hope, it would help:

Since your code is mainly about RegEx, which you'd most likely know that you can use this tool:

  • Your original RegEx based on an exact match method takes 265 steps and 1ms to match your 10 inputs, which is good.

    \s*(?:(\s*\d+\s*)|([\[\(]\s*\d+)\s*,\s*(\d+\s*[\]\)]))(?:,\s*(?:(\d+\s*)|\s*([\[\(]\d+)\s*,\s*(\d+\s*[\]\)])|(\s*>\s*=\s*0\s*)))?\s*
    
  • Sometimes, exact match may not be necessary, not sure about your case or if you might have certain boundaries, but maybe you could use a faster RegEx with a lower number of iterations, maybe something similar to this, if you are not looking for an exact match, which is pretty fast and might match your 10 inputs with only 50 steps:

    ^[0-9\,\[\]\(\) >=]*$
    

The drawback of this method is that it is based on your input characters, i.e., numbers, [, ], (, ), ,, space and >=.

\$\endgroup\$
2
\$\begingroup\$

The code is pretty easy to read (apart from the monster regexp, but I'm pleased you used raw-string quoting rather than filling it with backslashes!).

Some (mostly stylistic) comments:

  • If getRange() is an internal function, then give it internal linkage (static keyword, or an anonymous namespace). If it's intended to be user-visible, then it could use better argument names (perhaps only, first, last?).

  • I think that if (!string.empty()) shows intent a little better than if (string.length()).

  • Avoid calling std::stoi(value1) twice.

  • Prefer to pass pairs to parseRange(), rather than working with a global variable. Also it could be defined as std::vector<intRange>.

  • The big regexp could be split into several strings so that it can occupy several shorter lines, just as we do with ordinary string literals.

  • I'd invert the test so we can return early:

    std::smatch matches;
    if (!std::regex_match(input, matches, rx)) {
        return false;
    }
    
    // matched (rest of comment omitted)
    auto firstRange = getRange(matches[1], matches[2], matches[3]);
    auto secondRange = getRange(matches[4], matches[5], matches[6]);
    
    /* ... */
    
    return true;
    
  • Generation of the result pairs could alternatively be done using std::inner_product(). However, I think the nest of loops expresses it more clearly.

  • You forgot to #include <iostream> in the test program (preventing it compiling here).

  • inputs doesn't need to be a vector; it can be deduced (auto const inputs) as an initializer list.

\$\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.