Удаление из строки "лишних" пробелов

У меня есть программа, которая должна запросить у пользователя строку, и произвести с полученной строкой определённые действия. Но вот ведь незадача - некоторые очень неаккуратно работают с клавиатурой, и при вводе данных могут случайно нажать пробел несколько раз вместо одного, добавить совершенно ненужных пробелов в начале строки, или даже в конце. А представьте, что будет, если по клавиатуре пройдётся ваш любимый кот? Это будет катастрофа! Но спокойно, можно предусмотреть и это. Далее я хочу рассмотреть метод (несомненно, один из многих) удаления лишних пробелов из строки.

Для начала определим, какие пробелы считаются лишними. Лишними считаются

1. все пробелы, которые стоят в начале строки (т. е. перед первым символом строки, не являющегося пробелом);
2. пробелы между символами, если количество идущих подряд пробелов равно двум или более;
3. все пробелы в конце строки.

По условию задачи, нельзя пользоваться дополнительными массивами, кроме как массивом для хранения введённой пользователем строки.

Копать или не копать?

Для решения этой задачи удобно использовать так называемый конечный автомат. То есть, некий абстрактный автомат, который может пребывать в конечном количестве состояний. Например, в двух: "копать" или "не копать". Этот автомат будет переключаться из одного состояния в другое, в зависимости от выполнения каких-то условий.

Итак, звучит неплохо. Осталось придумать, как это использовать для решения задачи удаления пробелов.

Но прежде, чем что-то удалять из строки, мне нужна сама строка.

Получаю строку c помощью функции fgets()

Напишем работающую программу, которая считывает строку.

#include <stdio.h>
#include <string.h>
#define N 256

int main() {
  int charray[N];

  printf("Please enter string:\n> ");
  fgets(charray, N, stdin);
  
  return 0;
}

Эта программа пока только считывает строку со стандартного ввода (stdin) с помощью функции fgets() в массив символов размером N.

У функции fgets() есть замечательное свойство - используя её, я никогда не выйду за границу массива, если попытаюсь ввести строку длиннее, чем размер массива. Однако, у неё есть одна особенность: стоит мне ввести строку и нажать [Enter], как в конец введённой строки добавиться знак "\n", т.е. символ перехода на новую строку. Эта проблема решается гениально просто. Нужно лишь узнать длину введённой строки с помощью strlen():

len = strlen(charray); // Определяем длину строки
if('\n' == charray[len-1]) // Если предпоследний символ в строке='\n'
  charray[len-1] = 0;      // то заменяем его на нулевой символ, 
                           // т.е. символ конца строки, он же '\0'

Теперь у меня есть строка, готовая к дальнейшей обработке.

Реализация конечного автомата

Для удаления одного лишнего пробела, нужно сдвинуть элементы массива влево на 1. То есть, если пробел находится на позиции S, то на его место запишется символ из ячейки S+1, вместо S+1 запишется S+2 и т.д.

Идея состоит в следующем: можно использовать один и тот же алгоритм для удаления лишних пробелов в любом месте строки. А раз так, почему бы не вынести действие по удалению пробелов в отдельную функцию, и обращаться к ней, когда потребуется?.. Сказано - сделано.

int remove_spc(char *arr, int len, int pos) {
  int i;
  int len2 = len-1;

  for(i = pos; i <= len2; i++)
    arr[i] = arr[i + 1];

  return 0;
}

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

Самое забавное, что функции remove_spc() всё равно, какой элемент стоит после позиции pos - она так же будет сдвигать все пробелы, которые следуют за этой позицией. Более того, этой функции безразлично, какой элемент стоит на текущей позиции pos

Поэтому мне требуется что-то большее, чем эта функция. Лучше всего подходит для этой цели бесконечный цикл. В него я и помещу свой автомат. К слову, сейчас самое время подумать над его реализацией. Конечному автомату для решения этой задачи потребуется только два состояния, назову их STATE_1 и STATE_2. Находясь в состоянии STATE_1 автомат будет просто проверять, является ли текущий символ в просматриваемом массиве пробелом. Если пробел обнаруживается, автомат переключается в состояние STATE_2. В этом состоянии он будет копать удалять лишние пробелы.

Работу автомата удобно представить ввиде ленты и считывающей/записывающей головки над ней. Пустые ячейки - это пробелы, звёздочками отмечены занятые ячейки, т.е. в которых присутствуют символы, не являющиеся пробелами.

   _______________________________
1 | * | * |   |   |   | * | * | * |
   -------------------------------
        ^
   _______________________________
2 | * | * |   |   |   | * | * | * |
   -------------------------------
            ^
   _______________________________
3 | * | * |   |   |   | * | * | * |
   -------------------------------
                ^
   _______________________________
4 | * | * |   |   | * | * | * |   |
   -------------------------------
                ^
   _______________________________
5 | * | * |   | * | * | * |   |   |
   -------------------------------
                ^

На шаге 1 автомат находится в состоянии STATE_1. Ячейка занята, так что считывающая головка передвигается вправо на одну клетку.

На шаге 2 автомат всё ещё пребывает в состоянии STATE_1. Считывающая головка находится над пустой ячейкой, поэтому автомат перемещает считывающую головку вправо на одну ячейку и переключается в состояние STATE_2. Но здесь не всё так просто. Если мы хотим удалить пустую ячейку в начале строки, то нам не нужно перемещать считывающую головку на следующую ячейку перед переключением в STATE_2.

Теперь посмотрим, что же происходит, когда автомат находится в состоянии STATE_2. А происходит вот что: автомат начинает выкидывать пробелы из строки, вызывая функцию remove_spc (шаг 4). При этом, сама "считывающая головка" остаётся неподвижной, и после каждого вызова функции проверяет содержимое ячейки, над которой она находится.
Как только в ней оказывается какой-либо символ (шаг 5), не являющийся пробелом, автомат переключается вновь в состояние STATE_1.

Вот, как это выглядит в программном коде:

#define STATE_1 1
#define STATE_2 2

...

while(1) {
  switch(state) {
  
  case STATE_1:
    if(' ' == charray[i]) {
      state = STATE_2;
      if(0 == i)
        continue;
    }
    break;

  case STATE_2:
    if(' ' != charray[i])
      state = STATE_1;
    else {
      remove_spc(charray, len, i);
      continue;
    }
    break;

  } // end switch

  i++;

  if(i == len)
    break;

} // end while

А теперь плохая новость. После работы автомата, при количестве лишних пробелов в конце строки больше одного, после последнего символа всё равно оставался один пробел. Я не смог пока разобраться, почему так происходит. Поэтому, после завершения бесконечного цикла while(1), пришлось использовать костыль в виде следующих строчек:

len = strlen(charray);
if(' ' == charray[len-1])
  charray[len-1] = 0;

Этот кусок кода удаляет самый последний пробел, если он остаётся после работы автомата.

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

Исходник:
remove-spaces.c