c++:解析包含表达式 "access to the multidimensinal array"的字符串

Question

如何编写一个辅助方法，将给定的字符串(如 foo[0][1][2][3])拆分为数组名称和索引集合(例如 vector ) ？在上面的示例中，它应该分别生成 foo 和 0, 1, 2, 3。

字符串的格式总是像name[index_0][index_1]...[index_n]。 索引的数量 (n) 事先未知。都应该是数字。为简单起见，字符串中不允许有空格。数组的名称 (name) 可以是任意的。如果字符串不符合指定格式，辅助函数将抛出异常。

性能在这里不是问题。我正在寻找最优雅/最短的解决方案。

更新

好吧，在第一条评论中建议使用正则表达式。我是这个领域的新手，经历了用 C++ 完成它的麻烦。请随意简化它。同时，@MartinYork 和@Frodyne 提出了两个基于非正则表达式的解决方案。乍一看，正则表达式并没有给这里带来任何吸引人的东西。在我看来，该解决方案似乎并没有更短或更优雅。

#include <stdexcept>
#include <iostream>
#include <string>
#include <regex>
#include <tuple>

std::tuple<std::string, std::vector<int>> helper(std::string str) {
  // used to validate that the incoming string is in format
  // array[0][1][2]
  const std::regex rx_validate{
      "([[:alnum:]]+)((?:\\[[[:digit:]]+\\])+)$"};

  std::match_results<std::string::const_iterator> match_results;
  std::regex_search(str, match_results, rx_validate);

  // regex_search array[0][1][2] gives
  // match_results[0]: array[0][1][2]
  // match_results[1]: array
  // match_results[2]: [0][1][2]
  if (match_results.size() == 3) {
    std::vector<int> indices;

    // used to extract indices, it is guaranteed that
    // numbers are between brackets, no extra checks
    // needed
    const std::regex rx_index{"[0-9]+"};
    const std::string match{match_results[2]};
    auto it = std::sregex_iterator(match.begin(), match.end(), rx_index);
    for (; it != std::sregex_iterator(); ++it)
      indices.push_back(std::stoi((*it).str()));

    return std::make_tuple(match_results[1], indices);
  } else {
    throw std::invalid_argument("Invalid format (" + str + ")");
  }
}

int main() {
  const std::string str{"a[0][1][2][3][4][5]"};
  const auto tuple = helper(str);

  std::cout << "Name: " << std::get<0>(tuple) << std::endl;
  for (int index: std::get<1>(tuple))
    std::cout << index << std::endl;
}

更新 2

@rici 建议修改使用正则表达式的算法。它更短更简洁。

我真的很想在性能方面比较这些算法。

不会提倡数字:-)每个人都应该自己决定。

下面的程序编译为 g++ -std=c++11 -Ofast 并在 i7-8550U 上运行给出:

Regex measurements...
min/max/avg 955/154859/1072.88
Stream measurements...
min/max/avg 722/41252/800.402

#include <iostream>
#include <cstdlib>
#include <cstdint>
#include <limits>
#include <string>
#include <vector>
#include <regex>
#include <tuple>

#include <time.h>

inline uint64_t Timestamp() {
  timespec time_now;
  clock_gettime(CLOCK_REALTIME, &time_now);
  return static_cast<uint64_t>(time_now.tv_sec) * 1000000000ULL + time_now.tv_nsec;
}

std::tuple<std::string, std::vector<int>> helper_stream(std::string const& info)
{
    std::stringstream is(info);
    std::string         name;
    std::vector<int>    index;

    if (std::getline(is, name, '[')) {
        is.putback('[');
        name.erase(std::remove(std::begin(name), std::end(name), ' '), std::end(name));

        int   value;
        char  b1;
        char  b2;
        while(is >> b1 >> value >> b2 && b1 == '[' && b2 == ']') {
            index.push_back(value);
        }
    }
    return std::make_tuple(name, index);
}

std::tuple<std::string, std::vector<int>> helper_regex(std::string str) {
    static const std::regex strip_prefix{"^[[:alpha:]][[:alnum:]]*"};
    static const std::regex index{"\\[([[:digit:]]+)\\]|."};
    std::match_results<std::string::const_iterator> match;
    if (std::regex_search(str, match, strip_prefix)) {
        auto e = match[0].second;
        std::vector<int> indices;
        for (auto it = std::sregex_iterator(e, str.end(), index), lim = std::sregex_iterator(); it != lim; ++it) {
            if ((*it)[1].matched)
                indices.push_back(std::stoi((*it)[1]));
            else throw std::invalid_argument("Invalid format");
        }
        return std::make_tuple(std::string(str.cbegin(), e), indices);
    }
    else
        throw std::invalid_argument("Invalid format (" + str + ")");
}

std::string make_str(int n) {
  std::string str{"array"};

  for (int i = 0; i < n; ++i) {
    str += "[";
    str += std::to_string(std::rand());
    str += "]";
  }

  return str;
}

template <typename F>
void measurements(F f) {
  constexpr int kNumRounds = 1000000;
  constexpr int kLength = 3;

  std::vector<uint64_t> time_diffs(kNumRounds);

  for (int i = 0; i < kNumRounds; ++i) {
    const std::string str{make_str(kLength)};

    const auto before = Timestamp();
    f(str);
    const auto after = Timestamp();

    time_diffs[i] = after - before;
  }

  uint64_t min{std::numeric_limits<uint64_t>::max()};
  uint64_t max{std::numeric_limits<uint64_t>::min()};
  uint64_t sum{0};

  for (int i = 0; i < kNumRounds; ++i) {
    const auto time_diff = time_diffs[i];

    if (time_diff < min)
      min = time_diff;

    if (time_diff > max)
      max = time_diff;

    sum += time_diff;
  }

  std::cout << "min/max/avg " << min << "/" << max << "/" << static_cast<double>(sum) / kNumRounds << std::endl;
}

int main() {
  std::cout << "Regex measurements..." << std::endl;
  measurements(helper_regex);

  std::cout << "Stream measurements..." << std::endl;
  measurements(helper_stream);

  return 0;
}

Answer 1

这是我提倡退回到 C 解析函数的少数几次之一。虽然它可以通过正则表达式来完成，但对于如此微不足道的事情来说，这似乎有点沉重。

我会使用 C 函数 sscanf()

std::tuple<std::string, std::vector<int>> ck1(std::string const& info)
{

    int                 functionStartSize = 0;
    int                 functionNameSize = 0;
    char                check = 'X';
    std::vector<int>   index;

    if (std::sscanf(info.data(), " %n%*[^\[]%n%c", &functionStartSize, &functionNameSize, &check) == 1 && check == '[') {

        // Format String: " %n%*[^\[]%n%c"
        // ' ':        Ignore all leading space.
        // %n:         Save number of characters of space we dropped.
        // %*[^\[]:    Lets split this up
        //             %*      scan but don't save to a variable.
        //             [..]    Only the letters we find inside the brackets.
        //             ^\]     Everything except ]
        // %n:         Save the number of characters we have used to here.
        // %c:         A character This should now be a '['
        // We have correctly found the beginning and end of the name.

        int size;
        int value;
        int offset = functionNameSize;
        while(std::sscanf(info.data() + offset, "[%d%c%n", &value, &check, &size) == 2 && check == ']') {
            // We have found another index
            index.push_back(value);
            offset += size;
        }
    }
    return std::make_tuple(info.substr(functionStartSize, (functionNameSize-functionStartSize), index);
}

当我第一次编写上面的代码时，我假设 %n 会像任何其他参数一样计数。不幸的是，它不计入返回值。这使得对每个索引的检查稍微更加模糊，因此我不认为使用下面的流更好。

流并没有那么糟糕:
将字符串的完整拷贝放入字符串流中。但对于小字符串不是大问题。

std::tuple<std::string, std::vector<int>> ck2(std::string const& info)
{
    std::stringstream is(info);
    std::string         name;
    std::vector<int>    index;

    if (std::getline(is, name, '[')) {
        is.putback('[');
        name.erase(std::remove(std::begin(name), std::end(name), ' '), std::end(name));

        int   value;
        char  b1;
        char  b2;
        while(is >> b1 >> value >> b2 && b1 == '[' && b2 == ']') {
            index.push_back(value);
        }
    }
    return std::make_tuple(name, index);
}