用于从字符串中提取数字/数字范围的复杂算法

我正在研究一种算法，我正在尝试以下输出：

给定值/输入：

char *Var = "1-5,10,12,15-16,25-35,67,69,99-105"; int size = 29;

这里“1-5”表示范围值，即它将被理解为“1,2,3,4,5”，而仅具有“，”的值是单独的值。

我正在编写一种算法，其中结束输出应该是这样的，它将提供完整的输出范围：

 int list[]=1,2,3,4,5,10,12,15,16,25,26,27,28,29,30,31,32,33,34,35,67,69,99,100,101,102,103,104,105; 

如果有人熟悉这个问题，那么帮助将非常感激。 提前致谢！

我的初始代码方法如下：

 if(NULL != strchr((char *)grp_range, '-')) { int_u8 delims[] = "-"; result = (int_u8 *)strtok((char *)grp_range, (char *)delims); if(NULL != result) { start_index = strtol((char*)result, (char **)&end_ptr, 10); result = (int_u8 *)strtok(NULL, (char *)delims); } while(NULL != result) { end_index = strtol((char*)result, (char**)&end_ptr, 10); result = (int_u8 *)strtok(NULL, (char *)delims); } while(start_index <= end_index) { grp_list[i++] = start_index; start_index++; } } else if(NULL != strchr((char *)grp_range, ',')) { int_u8 delims[] = ","; result = (unison_u8 *)strtok((char *)grp_range, (char *)delims); while(result != NULL) { grp_list[i++] = strtol((char*)result, (char**)&end_ptr, 10); result = (int_u8 *)strtok(NULL, (char *)delims); } } 

但它只有在我有“0-5”或“0,10,15”时才有效。 我期待着它变得更加多样化。

Answer 1

你的问题似乎是误解了strtok是如何工作的。 看看这个。

 #include  #include  int main() { int i, j; char delims[] = " ,"; char str[] = "1-5,6,7"; char *tok; char tmp[256]; int rstart, rend; tok = strtok(str, delims); while(tok != NULL) { for(i = 0; i < strlen(tok); ++i) { //// range if(i != 0 && tok[i] == '-') { strncpy(tmp, tok, i); rstart = atoi(tmp); strcpy(tmp, tok + i + 1); rend = atoi(tmp); for(j = rstart; j <= rend; ++j) printf("%d\n", j); i = strlen(tok) + 1; } else if(strchr(tok, '-') == NULL) printf("%s\n", tok); } tok = strtok(NULL, delims); } return 0; } 

Answer 2

这是一个供您学习的C ++解决方案。

 #include  #include  #include  #include  using namespace std; int ConvertString2Int(const string& str) { stringstream ss(str); int x; if (! (ss >> x)) { cerr << "Error converting " << str << " to integer" << endl; abort(); } return x; } vector SplitStringToArray(const string& str, char splitter) { vector tokens; stringstream ss(str); string temp; while (getline(ss, temp, splitter)) // split into new "lines" based on character { tokens.push_back(temp); } return tokens; } vector ParseData(const string& data) { vector tokens = SplitStringToArray(data, ','); vector result; for (vector::const_iterator it = tokens.begin(), end_it = tokens.end(); it != end_it; ++it) { const string& token = *it; vector range = SplitStringToArray(token, '-'); if (range.size() == 1) { result.push_back(ConvertString2Int(range[0])); } else if (range.size() == 2) { int start = ConvertString2Int(range[0]); int stop = ConvertString2Int(range[1]); for (int i = start; i <= stop; i++) { result.push_back(i); } } else { cerr << "Error parsing token " << token << endl; abort(); } } return result; } int main() { vector result = ParseData("1-5,10,12,15-16,25-35,67,69,99-105"); for (vector::const_iterator it = result.begin(), end_it = result.end(); it != end_it; ++it) { cout << *it << " "; } cout << endl; } 

实例

http://ideone.com/2W99Tt

Answer 3

这是我的推动方法：

这不会给你一组int，而是一个int的向量

使用的算法:(没什么新的）

• 拆分字符串使用,

• 使用-拆分单个字符串-

• 使范围low和high

• 借助此范围将其推入矢量

码：-

 #include #include #include  #include  int main(){ std::string line("1-5,10,12,15-16,25-35,67,69,99-105"); std::vector strs,r; std::vector v; int low,high,i; boost::split(strs,line,boost::is_any_of(",")); for (auto it:strs) { boost::split(r,it,boost::is_any_of("-")); auto x = r.begin(); low = high =boost::lexical_cast(r[0]); x++; if(x!=r.end()) high = boost::lexical_cast(r[1]); for(i=low;i<=high;++i) v.push_back(i); } for(auto x:v) std::cout< 

Answer 4

不要搜索。 只需一次浏览一个字符。 只要你看到数字，就把它们累积成一个值。 如果数字后跟a -那么您正在查看范围，并且需要解析下一组数字以获得范围的上限并将所有值放入列表中。 如果值后面没有-那么你就得到了一个值; 把它放到你的清单中。

Answer 5

停下来想一想：你实际拥有的是逗号分隔的范围列表，其中范围可以是单个数字，也可以是由'-'分隔的一对数字。 因此，您可能希望循环使用范围，使用递归下降进行解析。 （这种事情最好用istream处理，所以我会用它。）

 std::vector results; std::istringstream parser( std::string( var ) ); processRange( results, parser ); while ( isSeparator( parser, ',' ) ) { processRange( results, parser ); } 

有：

 bool isSeparator( std::istream& source, char separ ) { char next; source >> next; if ( source && next != separ ) { source.putback( next ); } return source && next == separ; } 

和

 void processRange( std::vector& results, std::istream& source ) { int first = 0; source >> first; int last = first; if ( isSeparator( source, '-' ) ) { source >> last; } if ( last < first ) { source.setstate( std::ios_base::failbit ); } if ( source ) { while ( first != last ) { results.push_back( first ); ++ first; } results.push_back( first ); } } 

实际上， isSeparator函数可能在将来的其他项目中很有用，应该保存在工具箱中。

Answer 6

首先将整个字符串分成数字和范围（使用带有“，”分隔符的strtok（）），将字符串保存在数组中，然后搜索数组，查找“ – ”，如果存在，则使用sscanf（）和“％d-％” d“格式化，否则使用单个”％d“格式的sscanf。

function使用很容易谷歌搜索。

Answer 7

一种方法：

你需要一个识别3种标记的解析器：’，’，’ – ‘和数字。 这提高了抽象级别，使您在字符之上操作。

然后，您可以解析令牌流以创建范围和常量列表。

然后，您可以解析该列表以将范围转换为常量。

一些代码可以完成部分工作：

 #include  // Prints a comma after the last digit. You will need to fix that up. void print(int a, int b) { for (int i = a; i <= b; ++i) { printf("%d, ", i); } } int main() { enum { DASH, COMMA, NUMBER }; struct token { int type; int value; }; // Sample input stream. Notice the sentinel comma at the end. // 1-5,10, struct token tokStream[] = { { NUMBER, 1 }, { DASH, 0 }, { NUMBER, 5 }, { COMMA, 0 }, { NUMBER, 10 }, { COMMA, 0 } }; // This parser assumes well formed input. You have to add all the error // checking yourself. size_t i = 0; while (i < sizeof(tokStream)/sizeof(struct token)) { if (tokStream[i+1].type == COMMA) { print(tokStream[i].value, tokStream[i].value); i += 2; // skip to next number } else { // DASH print(tokStream[i].value, tokStream[i+2].value); i += 4; // skip to next number } } return 0; }