6

所以基本上，我可能有一些看起来像这样的字符串：“嘿，这是一个字符串 * 这个字符串很棒 97 * 3 = 27 * 这个字符串很酷”。

但是，这个字符串可能很大。我正在尝试从字符串中删除所有星号，除非该星号似乎代表乘法。效率在这里有点重要，我很难想出一个好的算法来删除所有非乘法星号。

为了确定星号是否用于乘法，我显然可以检查它是否夹在两个数字之间。

因此，我想我可以做类似（伪代码）的事情：

wasNumber = false
Loop through string
   if number 
      set wasNumber = true
   else
      set wasNumber = false
   if asterisk
      if wasNumber
         if the next word is a number
            do nothing
         else
            remove asterisk
      else
         remove asterisk

然而，这 ^ 在一个巨大的字符串上是丑陋和低效的。你能想出一个更好的方法在 C++ 中完成这个任务吗？

另外，我怎么能真正检查一个单词是否是一个数字？允许为小数。我知道有一个功能可以检查字符是否为数字...

4

4 回答 4

4

功能齐全的代码：

#include <iostream>
#include <string>
using namespace std;

string RemoveAllAstericks(string);
void RemoveSingleAsterick(string&, int);
bool IsDigit(char);

int main()
{
    string myString = "hey this is a string * this string is awesome 97 * 3 = 27 * this string is cool";
    string newString = RemoveAllAstericks(myString);

    cout << "Original: " << myString << "\n";
    cout << "Modified: " << newString << endl;

    system("pause");
    return 0;
}

string RemoveAllAstericks(string s)
{
    int len = s.size();
    int pos;

    for(int i = 0; i < len; i++)
    {
       if(s[i] != '*') 
          continue;

       pos = i - 1;
       char cBefore = s[pos];
       while(cBefore == ' ')
       {
          pos--;
          cBefore = s[pos];
       }

       pos = i + 1;
       char cAfter  = s[pos];
       while(cAfter == ' ')
       {
          pos++;
          cAfter = s[pos];
       }

       if( IsDigit(cBefore) && IsDigit(cAfter) )
          RemoveSingleAsterick(s, i);
    }

    return s;
}

void RemoveSingleAsterick(string& s, int i)
{
    s[i] = ' '; // Replaces * with a space, but you can do whatever you want
}

bool IsDigit(char c)
{
   return (c <= 57 && c >= 48);
}

顶级概览：

代码搜索字符串，直到遇到*. 然后，它查看 . 之前 AND 之后的第一个非空白字符*。如果两个字符都是数字，则代码确定这是一个乘法运算，并删除星号。否则，将被忽略。

如果您想了解其他详细信息，请参阅这篇文章的修订历史。

重要笔记：

  • 您应该认真考虑在字符串上添加边界检查（即不要尝试访问小于0或大于的索引len
  • 如果您担心括号，则将检查空格的条件更改为也检查括号。
  • 检查每个字符是否都是数字是个坏主意。至少，它需要两个逻辑检查（参见我的IsDigit()函数）。（我的代码检查“*”，这是一种逻辑操作。）但是，发布的一些建议经过深思熟虑。不要使用正则表达式来检查字符是否为数字。

由于您在问题中提到了效率，并且我没有足够的代表点来评论其他答案：

检查 '0' '1' '2' ... 的 switch 语句意味着每个不是数字的字符都必须经过 10 次逻辑运算。恕我直言，由于schar映射到ints，请检查边界(char <= '9' && char >= '0')

于 2011-07-28T18:45:40.027 回答
3

您可以从实施慢速版本开始，它可能比您想象的要快得多。但是让我们说它太慢了。那么这是一个优化问题。效率低下在哪里？

  • “如果数字”很简单，您可以使用正则表达式或任何在发现不是数字的东西时停止的东西
  • “如果下一个单词是数字”同样容易有效地实现。

现在，“删除星号”部分对您来说是个问题。这里要注意的关键点是您不需要复制字符串：您实际上可以就地修改它，因为您只是删除元素。

在尝试实现它之前尝试直观地运行它。

保留两个整数或迭代器，第一个表示您当前正在读取字符串的位置，第二个表示您当前正在写入字符串的位置。由于您只擦除内容，因此读取的内容将始终领先于写入的内容。

如果您决定保留当前字符串，您只需要一个一个地推进每个整数/迭代器，并相应地复制。如果您不想保留它，只需推进阅读字符串！然后你只需要按照你删除的星号数量来切割字符串。复杂度只是 O(n)，没有使用任何额外的缓冲区。

另请注意，如果这样编写，您的算法会更简单（但等效）：

wasNumber = false
Loop through string
   if number 
      set wasNumber = true
   else
      set wasNumber = false
      if asterisk and wasNumber and next word is a number
          do nothing // using my algorithm, "do nothing" actually copies what you intend to keep
      else
          remove asterisk
于 2011-07-28T16:59:12.043 回答
3

我发现你的小问题很有趣，我编写（并测试）了一个小而简单的函数，可以在std::string. 给你：

// TestStringsCpp.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <string>
#include <iostream>

using namespace std;

string& ClearAsterisk(string& iString)
{
    bool bLastCharNumeric = false;
    string lString = "0123456789";

    for (string::iterator it = iString.begin(); it != iString.end() ; ++it) {
        switch (*it) {
        case ' ':   break;//ignore whitespace characters
        case '*':
            if (bLastCharNumeric) {
                //asterisk is preceded by numeric character. we have to check if
                //the following non space character is numeric also
                for (string::iterator it2 = it + 1; it2 != iString.end() ; ++it2) {
                    if (*it2 != ' ') {
                        if (*it2 <= '9' && *it2 >= '0') break;
                        else iString.erase(it);
                        break;  //exit current for
                    }
                }
            }
            else iString.erase(it);;
            break;

        default:
            if (*it <= '9' && *it >= '0') bLastCharNumeric= true;
            else bLastCharNumeric = false;  //reset flag
        }
    }
    return iString;
}

int _tmain(int argc, _TCHAR* argv[])
{
    string testString = "hey this is a string * this string is awesome 97 * 3 = 27 * this string is cool";

    cout<<ClearAsterisk(testString).c_str();
    cin >> testString;  //this is just for the app to pause a bit :)

    return 0;
}

它将与您的示例字符串完美配合，但如果您有这样的文本，它将失败："this is a happy 5 * 3day menu"因为它仅检查“*”之后的第一个非空格字符。但坦率地说，我无法想象在很多情况下你会在一个句子中使用这种结构。

HTH，
JP。

于 2011-07-28T18:45:58.060 回答
0

正则表达式不一定会更有效，但它会让您依赖其他人来进行字符串解析和操作。

就个人而言，如果我担心效率，我会实现您的伪代码版本，同时限制不必要的内存分配。我什至可能是mmap输入文件。我非常怀疑你会比这快得多。

于 2011-07-28T17:22:07.850 回答