Удалить все соседние дубликаты в строке с помощью стека


Вход: careermonk
Выход: camonk

Вход: Миссисипи
Выходные данные: м.

Я хочу улучшить этот код.

#include <iostream>
#include <string>

#define max 1000

class Stack
{
  int top;
public:
  char stk[max];
  Stack()
  {
    top = -1;
  }
  bool isStackEmpty();
  void push(char);
  char pop();
  std::string modifyString(std::string);
private:
  void removeAdjacentDuplicate(std::string);
};

bool Stack::isStackEmpty()
{
   if (top == -1)
      return true;
   else
      return false;
}

void Stack::push(char val)
{
   int s = max - 1;
   if (top < s)
   {
     top = top + 1;
     stk[top] = val;
   }
   else
    std::cerr << "Stack Overflow \n";
}

char Stack::pop()
{
   if (isStackEmpty() == true)
       std::cerr << "Stack Underflow \n";
   else
   {
      --top;
      return stk[top + 1];
   }
}

void Stack::removeAdjacentDuplicate(std::string str)
{
   int len = str.length();
   for (int i = 0; i < len; i++)
   {
      if (isStackEmpty() == true)
      {
         push(str[i]);
      }
      else if (str[i] == stk[top])
      {
         int discard = pop();
      }
      else
      {
         push(str[i]);
      }
   }
}

std::string Stack::modifyString(std::string str)
{
   removeAdjacentDuplicate(str);
   str.resize(top + 1);
   for (int i = 0; i <= top; i++)
   {
     str[i] = stk[i];
   }
   str[top + 1] = '\0';
   return str;
}

int main()
{
   Stack stack1;
   std::string str = "careermonk";
   std::cout << "Orignal string : " << str << "\n";
   str = stack1.modifyString(str);
   std::cout << "New string     : " << str << "\n";

   Stack stack2;
   std::string str2 = "mississippi";
   std::cout << "Original string : " << str2 << "\n";
   str2 = stack2.modifyString(str2);
   std::cout << "New string      : " << str2 << "\n";
}


472
1
задан 9 февраля 2018 в 07:02 Источник Поделиться
Комментарии
2 ответа

с std::массив

Вы могли бы использовать std::array и избавиться от max определение. В общем, я хотел бы предложить, избегая определяет, который может конфликтовать с любыми именами стл любой ценой.

Один из заголовков Windows имеет свою собственную #define max и это ужасно, когда ваш код хочет std::numeric_limits<int>::max(), std::max({a, b, c})и т. д.

Дела обстоят даже хуже, если ты пишешь только заголовок библиотеки:

#if defined max
# undef max
# define HAD_MAX
#endif

// ... C++ code ...

#if defined HAD_MAX
# define max(a, b) ... // copy-paste from Windows.h
#endif

Стек::removeAdjacentDuplicate подпись

Подпись Stack::removeAdjacentDuplicate(std::string) можно улучшить:

По крайней мере, он на самом деле не все удаляет. Его выполняют какую-то инициализацию из данной строки, так что попробуйте выбрать более понятное имя.

Кроме того, во избежание копирования параметров - можно использовать const std::string&

Стек::modifyString

Stack::modifyString также ничего не говорит о своей цели, и это также создает еще одну строку, а не изменять что-то. Рассмотрим лучше именования.

Использовать стандартную библиотеку

При копировании N символов, рекомендуется использовать функции стандартной библиотеки вместо for петли: strncpy, memcpy, std::copy_n и другие прекрасно работает, выглядит понятно и может выполнять некоторые оптимизации производительности.

Использовать стандартную библиотеку (альтернатива)

Как альтернатива, можно создать новую строку непосредственно из Stack::stk. Есть соответствующий конструктор: std::string(const char* s, size_t n);. В этом случае вы можете пройти все с std::string параметры по константной ссылке.

Кстати, я уверяю, вы уже надоели со своей переменной предложения именования, так что я не нужно добавлять еще один :)

Неконстантные члены общественных опасны

Рекомендуется использовать некоторые соглашения об именовании

Трудно определить, какая переменная является членом класса или нет. Для того, чтобы упростить вашу работу, сделать как-то переменные-члены. Вы можете использовать m_member, member_ и т. д.

2
ответ дан 14 февраля 2018 в 02:02 Источник Поделиться

Избегайте произвольных ограничений

Определение max (и особенно в качестве #define а не как в C++ константа) вызывает тревогу. Особенно как проверять просто выводит диагностическое и игнорирует действие, которое было предложено.

Простые рефакторинги

if (test) return true; else return false; такой же, как и return test;. Итак, мы можем написать

bool Stack::isStackEmpty()
{
return top == -1;
}

Кроме того, тестирование ==true является избыточной:

   if (isStackEmpty())

Более активное участие рефакторинг

void Stack::removeAdjacentDuplicate(std::string str)
{
int len = str.length();
for (int i = 0; i < len; i++)
{
if (isStackEmpty() == true)
{
push(str[i]);
}
else if (str[i] == stk[top])
{
int discard = pop();
}
else
{
push(str[i]);
}
}
}

Здесь мы перебора элементов str, так что мы можем использовать for (char c: str), который является более четким и менее подверженным ошибкам, чем использование индексов.

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

void Stack::removeAdjacentDuplicate(const std::string& str)
{
for (auto c: str) {
if (isStackEmpty() || c != stk[top]) {
push(c);
} else {
(void)pop();
}
}
}

Думаю как стандартные алгоритмы

У нас есть стандартные алгоритмы - один похож на наши потребности std::unique(). Это делает один проход над его вход, и возвращает итератор на новый конец позиции.

Если мы сделаем функцию с похожим интерфейсом, мы можем использовать идиомы 'стереть/удалить', чтобы заменить символы в строке:

#include <string>

std::string repeatedly_remove_duplicates(std::string s)
{
s.erase(repeatedly_remove_duplicates(s.begin(), s.end()), s.end());
return s;
}

Как мы реализуем repeatedly_remove_duplicates()? Я предполагаю, что один проход называется remove_duplicates()и вызывать его до тех пор, пока вернулись итоге не меняет:

template <typename Iter>
Iter repeatedly_remove_duplicates(Iter begin, Iter end)
{
Iter new_end;
while ((new_end = remove_duplicates(begin, end)) != end) {
end = new_end;
}
return end;
}

(Я сделал этот шаблон, поэтому он может работать с любым контейнером. Также позволяет нам сделать repeatedly_remove_duplicates() шаблон для работы с любым типом string, в том числе std::wstring, например).

Теперь, нам нужна реализация remove_duplicates. Мы можем сделать это на месте:

template <typename Iter>
Iter remove_duplicates(Iter begin, Iter end)
{
auto dest = begin;
if (begin == end) { return dest; }

auto prev = begin;
bool is_duplicate = false;
while (++begin != end) {
if (*begin == *prev) {
is_duplicate = true;
} else {
if (!is_duplicate) {
*dest++ = *prev;
}
is_duplicate = false;
prev = begin;
}
}

if (!is_duplicate) {
*dest++ = *prev;
}

return dest;
}

Есть и другие способы сделать это; мы могли бы использовать std::adjacent_find()например:

#include <algorithm>
#include <functional>

template <typename Iter>
Iter remove_duplicates(Iter begin, Iter end)
{
using namespace std::placeholders;
using not_equal_to = std::not_equal_to<typename Iter::value_type>;

auto dest = begin;

do {
Iter pair = std::adjacent_find(begin, end);
if (dest != begin) {
std::copy(begin, pair, dest);
dest += std::distance(begin, pair);
} else {
dest = pair;
}
} while (begin != end);

return dest;
}


Собираем все вместе

#include <algorithm>
#include <functional>

template <typename Iter>
Iter remove_duplicates(Iter begin, Iter end)
{
using namespace std::placeholders;
using not_equal_to = std::not_equal_to<typename Iter::value_type>;

auto dest = begin;

do {
Iter pair = std::adjacent_find(begin, end);
if (dest != begin) {
std::copy(begin, pair, dest);
dest += std::distance(begin, pair);
} else {
dest = pair;
}
#ifdef REMOVE_PAIR_ONLY
begin = pair;
if (pair != end) {
begin += 2;
}
#else
begin = std::adjacent_find(pair, end, not_equal_to());
if (begin != end) {
++begin;
}
#endif
} while (begin != end);

return dest;
}

template <typename Iter>
Iter repeatedly_remove_duplicates(Iter begin, Iter end)
{
Iter new_end;
while ((new_end = remove_duplicates(begin, end)) != end) {
end = new_end;
}
return end;
}

#include <string>
std::string repeatedly_remove_duplicates(std::string s)
{
s.erase(repeatedly_remove_duplicates(s.begin(), s.end()), s.end());
return s;
}

#include <iostream>
int main(int argc, char **argv)
{
for (auto i = 1; i < argc; ++i) {
std::cout << argv[i] << " ⇒ "
<< repeatedly_remove_duplicates(argv[i])
<< std::endl;
}
}

1
ответ дан 14 февраля 2018 в 05:02 Источник Поделиться