Extracting all-caps variables from string expressions

Question

I'm extracting variables from user entered mathematical expressions, so that I can enter them into the expression evaluator exprtk. For now, the condition is given that variable names will be composed of consecutive capital letters. Any mathematical constants or function names will be lowercase. Some hypothetical inputs and expected outputs:

Input: "(A + B) - 2"
Expected Output: { A, B }

Input: "pow(AC,E) * ( E * F )"
Expected Output: { AC, E, F }

The code I have right now seems to work, but I would love a critique. I add a space to the end of the string to make my algorithm catch cases at the end of the string, which seems a bit hacky(?).

template<class T>
std::vector<std::string> MapEvaluator<T>::extractVariables(std::string expression) {

    expression = expression + " ";
    std::vector<std::string> variables = {};
    std::string substring;
    size_t consecutiveCharsCaps = 0;
    bool previousCharCaps = false;

    for (size_t i = 0; i < expression.length(); i++)
    {
        if (isCapital(expression[i]))
        {
            consecutiveCharsCaps++;
            previousCharCaps = true;
        }
        else {
            if(previousCharCaps) {
                substring = expression.substr(i - consecutiveCharsCaps, consecutiveCharsCaps);
                variables.push_back(substring);
                consecutiveCharsCaps = 0;
                previousCharCaps = false;
            }
        }
    }

    unique(variables);
    return variables;
}

template <class T>
void MapEvaluator<T>::unique(std::vector<std::string> &vec)
{
    auto end = vec.end();
    for (auto it = vec.begin(); it != end; ++it) {
        end = std::remove(it + 1, end, *it);
    }
    vec.erase(end, vec.end());
}

template<class T>
bool MapEvaluator<T>::isCapital(char c) {
    return (c >='A' && c <= 'Z');
}

Answer 1

Some observations:

• It seems that std::adjacent_find essentially already does what you want, which is extracting all continuous sub-strings consisting of uppercase letters.

• Removing duplicates from a vector might be fine, but you can also avoid this completely by inserting the found elements into a std::set. I suspect that the number of unique variables is always small, so this is a cleaner approach.

• There is no reason for isCapital to be a member function. Instead, it should be a free function. Remember that interfaces should be complete but minimal. But in fact, there's no reason for the function in the first place: the standard already has std::isupper that we should rather use.

So with these in mind, we can re-write your function to e.g.,:

std::vector<std::string> get_variables(const std::string& str)
{
    std::set<std::string> vars;

    for (auto first = str.cbegin(); first != str.cend(); )
    {
        auto var_end = std::adjacent_find(first, str.cend(),
            [](char a, char b) 
        { 
            return std::isupper(static_cast<unsighed char>(a)) !=
                std::isupper(static_cast<unsigned char>(b)); 
        });

        if (var_end != str.cend())
        {
            ++var_end;
        }

        if (std::isupper(static_cast<unsigned char>(*first)))
        {
            vars.insert(std::string(first, var_end));
        }

        first = var_end;
    }

    return std::vector<std::string>(vars.cbegin(), vars.cend());
}

Notice that we've cast char to unsigned char before the call to std::isupper (thanks to Deduplicator for explaining this to me). The reason is that std::isupper takes an argument of type int which must be in the range of unsigned char (or special value EOF, -1). Unfortunately, a plain char has either the range of signed char or unsigned char, so we perform a cast to confer to this common convention of character classification functions.

Answer 2

1. Take advantage of views, specifically C++17 std::string_view, to avoid needless allocations.

2. Take advantage of the standard algorithms. They help writing clear, concise and fast code.

3. Text is hard. So, do you really want uppercase ASCII letters, all single-byte (thus non-unicode) uppercase letters the current locale supports, or full unicode support? I will ignore the last option.

4. Minimize the accessible context, and decouple as you can. extractVariables() can be a free function. Actually, extract a function for listing runs of any kind.

5. auto is very useful to avoid error-prone repetition.

Applying that:

template <class T, class F>
auto listRuns(T s, F f) {
    std::vector<T> r;
    auto first = begin(s);
    while ((first = std::find_if(first, end(s), f) != end(s)) {
        auto last = std::find_if_not(first, end(s), f);
        r.emplace(first, last - first);
        first = last;
    }
    std::sort(begin(r), end(r));
    r.resize(end(r) - std::unique(begin(r), end(r)));
    return r;
}

auto extractVariables(std::string_view s) {
    return listRuns(s, [](unsigned char c){ return std::is_upper(c); });
    // Keep in mind the defined domain of std::is_upper()

    return listRuns(s, [](char c){ return c >= 'A' && c <= 'Z';});
    // Assumes ASCII and asks for uppercase letters
}

Something to ponder:

It might seem (or rarely actually be) advantageous to first insert into a std::set or std::unordered_set to filter out duplicates.
Unfortunately the added complexity and reduced locality of reference will almost always destroy any potential advantage, unless it leads to a very significant saving of memory. Every single dynamic allocation has (sometimes significant) overhead though.
So if you want to try it, measure.

Answer 3

In the ExprTk readme.txt there is a section called: Helpers & Utils

In the sub-section called collect_variables there is a description of a helper free function named exprtk::collect_variables, which can be used to extract a list of variables used in a given expression.

The following is an example usage of the exprtk::collect_variables function:

std::string expression = "X + abs(y / Z)";

std::vector<std::string> variable_list;

if (exprtk::collect_variables(expression, variable_list))
{
   for (const auto& var : variable_list)
   {
      ...
   }
}
else
  printf("An error occurred.");

If successful the variable_list should contain the variables names "X", "y" and "Z".