C/C++/Java/C＃：帮助解析数字

我有一个真正的问题（这不是作业，你可以检查我的配置文件）。我需要解析格式不受我控制的数据。C/C++/Java/C＃：帮助解析数字

的数据是这样的：

6852：6100752

所以这是第一个由多达9位的数字，后面跟一个冒号。

然后，我确实知道，在冒号后面：

有，最多列
我知道究竟有多少数量加起来才加入到数字号码中至少一个有效组合冒号前的数（两位在这种情况下，但它可以高达十数）

在这种情况下，6852是6100 + 752

我的问题：我需要找到这些数字（在这个例子中，6100 + 752）。

不幸的是，在我被迫解析的数据中，数字（逗号）之间的分隔符也是数字本身内部使用的分隔符（6100写为6,100）。

再一次：那个不幸的格式化不在我的控制之下，再次，这不是作业。

我需要解决这个需要加起来多达10个数字。

下面是用三个数字加起来6855为例：

6,855：360,6,175,320

我担心有这样的情况，将有两个可能的不同的解决方案。但是如果我得到一个解决方案，作品“在大多数情况下”这就够了。

你是如何用C型括号语言解决这个问题的？

来源

2010-06-30 NoozNooz42

语言语法与您如何解决此问题很少有关。更相关的是你可用的库函数。你打算使用哪种语言？ – 2010-06-30 21:39:56

我认为他的意思更多的仅仅是指示伪代码语法样式的使用方式，而不是确定实际的实现。 – jdmichal 2010-06-30 22:00:29

这是一个子集总和问题的特例：http://en.wikipedia.org/wiki/Subset_sum – Mau 2010-06-30 22:04:07

递归执行（伪代码）：

int total; // The total read before the colon 

// Takes the list of tokens as integers after the colon 
// tokens is the set of tokens left to analyse, 
// partialList is the partial list of numbers built so far 
// sum is the sum of numbers in partialList 
// Aggregate takes 2 ints XXX and YYY and returns XXX,YYY (= XXX*1000+YYY) 
function getNumbers(tokens, sum, partialList) = 
    if isEmpty(tokens) 
     if sum = total return partialList 
     else return null // Got to the end with the wrong sum 
    var result1 = getNumbers(tokens[1:end], sum+token[0], Add(partialList, tokens[0])) 
    var result2 = getNumbers(tokens[2:end], sum+Aggregate(token[0], token[1]), Append(partialList, Aggregate(tokens[0], tokens[1]))) 
    if result1 <> null return result1 
    if result2 <> null return result2 
    return null // No solution overall

你可以从不同的角度，如尾递归好了很多，修剪（你可以有XXX，YYY只有YYY有3位数字） ...但这可能对您的应用程序足够好。分而治之将会带来不错的改善。

来源

2010-06-30 22:19:50 Mau

我认为你的主要问题是决定如何实际解析数字。剩下的就是用字符串 - >数字和迭代遍历组合的方式。

例如，在您给出的例子中，您可以试探性地确定一个三位数字后跟一位数字，实际上是一个四位数字。像这样的启发式是否适用于较大的数据集？如果不是，那么您也可能需要遍历可能的输入解析组合，这意味着天真的解决方案将具有很大的多项式复杂度（O（n ^x），其中x> 4）。

实际上，使用递归搜索来检查哪些数字加起来很容易。

List<int> GetSummands(int total, int numberOfElements, IEnumerable<int> values) 
{ 
    if (numberOfElements == 0) 
    { 
     if (total == 0) 
      return new List<int>(); // Empty list. 
     else 
      return null; // Indicate no solution. 
    } 
    else if (total < 0) 
    { 
     return null; // Indicate no solution. 
    } 
    else 
    { 
     for (int i = 0; i < values.Count; ++i) 
     { 
      List<int> summands = GetSummands(
       total - values[i], numberOfElements - 1, values.Skip(i + 1)); 
      if (summands != null) 
      { 
       // Found solution. 
       summands.Add(values[i]); 
       return summands; 
      } 
     } 
    } 
}

来源

2010-06-30 21:46:53 jdmichal

我想你应该尝试所有可能的方式来解析字符串并计算总和，并返回那些给出正确和结果的列表。在大多数情况下，这应该只是一个结果，除非你非常不走运。

有一点需要注意的是，如果您有aa,bbb和bbb恰好是3位数字，则可能性的数量会减少。如果您有aa,bb，只有一种解析方法。

来源

2010-06-30 21:47:27

那么，我会先从蛮力方法开始，然后应用一些启发式方法来修剪搜索空间。只需用逗号分割右边的列表，并遍历所有可能的方式将它们分成n个术语（其中n是解决方案中的术语数）。您可以使用以下两条规则跳过无效的可能性。（1）您知道任何一组1或2位数字必须开始一个任期。（2）您知道逗号分隔列表中的候选词不会超过左边的总数。（这也告诉你，任何一个候选词语可以有位组的最大数量。）

来源

2010-06-30 21:50:59

你误会了。问题描述的一部分是你不能有无效的输入。我的意思正是你所说的 - 你可以忽略这个价值（并跳过解决方案空间的相应部分）。 – 2010-07-01 04:38:17

是的，正如问题中所述，我知道在每一个案例中至少有一个正确的解决方案:) – NoozNooz42 2010-07-01 12:25:47

读入C++：

std::pair<int,std::vector<int> > read_numbers(std::istream& is) 
{ 
    std::pair<int,std::vector<int> > result; 
    if(!is >> result.first) throw "foo!" 
    for(;;) { 
    int i; 
    if(!is >> i) 
     if(is.eof()) return result; 
     else throw "bar!"; 
    result.second.push_back(i); 
    char ch; 
    if(is >> ch) 
     if(ch != ',') throw "foobar!"; 
    is >> std::ws; 
    } 
} 

void f() 
{ 
    std::istringstream iss("6,852:6,100,752"); 
    std::pair<int,std::vector<int> > foo = read_numbers(iss); 
    std::vector<int> result = get_winning_combination(foo.first 
                , foo.second.begin() 
                , foo.second.end()); 
    for(std::vector<int>::const_iterator i=result.begin(); i!=result.end(), ++i) 
    std::cout << *i << " "; 
}

数字的实际裂解留下作为一个练习读者。 :)

来源

2010-06-30 21:57:13 sbi

C/C++/Java/C＃：帮助解析数字

回答

相关问题