C ++: удаление всех звездочек из строки, где звездочки НЕ являются символами умножения

Question

Так что, в принципе, у меня может быть какая-то строка, которая выглядит следующим образом: «эй, это строка * эта строка потрясающая 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 ++?

Кроме того, как я могу на самом деле проверить, является ли слово числом?Это разрешено быть десятичным.Я знаю, что есть функция для проверки, является ли символ числом ...

Answer 1

Полностью функционирующий код:

#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);
}

Обзор верхнего уровня:

Код ищет строку, пока не встретит *.Затем он просматривает первый непробельный символ до и после *.Если оба символа являются числовыми, код решает, что это операция умножения, и удаляет звездочку.В противном случае он игнорируется.

Просмотрите историю изменений этого поста, если вам нужны другие сведения.

Важные примечания:

• Вы должны серьезно подумать о добавлениипроверка границ в строке (т. е. не пытайтесь получить доступ к индексу, который меньше 0 или больше len
• Если вас беспокоят скобки, измените условие проверки пустых пространств натакже проверьте наличие скобок.
• Проверка того, является ли каждый отдельный символ числом, является плохой идеей. Как минимум, для этого потребуются две логические проверки (см. мойIsDigit() function). (Мой код проверяет '*', что является одной логической операцией.) Однако некоторые из опубликованных предложений были очень плохо продуманы. Не используйте регулярные выражения для проверки, является ли символ числовым.

Поскольку вы упомянули эффективность в своем вопросе, а у меня недостаточно точек повторения, чтобы комментировать другие ответы:

Оператор switch, который проверяет '0''1' '2' ... означает, что каждый символ, который НЕ является цифрой, должен пройти 10 логических операций.При всем уважении, , пожалуйста, , поскольку char s отображается на int s, просто проверьте границы (char <= '9' && char >= '0')

Answer 2

Мне показалась интересной ваша маленькая проблема, и я написал ( и протестировал ) небольшую и простую функцию, которая будет делать это только на 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", потому что он проверяет только первый непробельный символ после '*'. Но, честно говоря, я не могу вообразить много случаев, когда у вас была бы такая конструкция в предложении.

НТН,
JP.

Answer 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

Answer 4

Регулярное выражение не обязательно будет более эффективным, но оно позволит вам полагаться на то, что кто-то другой будет выполнять анализ и манипулирование строками.

Лично, если бы я беспокоился об эффективности, я бы реализовалВаша версия псевдокода, ограничивая ненужные выделения памяти.Я мог бы даже mmap входной файл.Я очень сомневаюсь, что вы получите намного быстрее, чем это.