Эхо всех палиндромов, в т - PullRequest
       37

Эхо всех палиндромов, в т

4 голосов
/ 25 сентября 2010

Мне нравятся идеи, представленные в книге Брайана Кернигана и Роба Пайка "Среда программирования UNIX", где они сосредоточены на том, чтобы работать в среде, где вы можете собрать множество (маленьких, точных, хорошо понятых) программкомандная строка для выполнения многих задач программирования.

Я изучаю строгие соглашения ANSI C и пытаюсь придерживаться этой философии.Где-то в этой книге (при необходимости я могу получить точный номер страницы) они предлагают, чтобы все программы в этой среде придерживались следующих принципов:

  1. Если ввод представлен в командной строкев качестве аргумента для самой программы обработайте этот ввод.

  2. Если в командной строке нет ввода, обработайте ввод из stdin.

Вот программа на C, которую я написал, которая будет отображать любой ввод (числовой или буквенный), который является палиндромом.Мой конкретный вопрос:

Является ли это программой на C с хорошим поведением?Другими словами, это то, что Керниган и Пайк предлагали, это оптимальное поведение для приложения командной строки, подобного этому?

#include <stdio.h>
#include <string.h> /* for strlen */

int main(int argc, char* argv[]) {

    char r_string[100];

    if (argc > 1) {

        int length = (int)strlen(argv[1]);

        int i = 0;
        int j = length;
        r_string[j] = (char)NULL;
        j--;
        for (i = 0; i < length; i++, j--) {
           r_string[j] = argv[1][i];
        }

        if (strcmp(argv[1], r_string) == 0) {
            printf("%s\n", argv[1]);
        }

    } else {

        char* i_string;

        while (scanf("%s", i_string) != EOF) {

            int length = (int)strlen(i_string);

            int i = 0;
            int j = length;
            r_string[j] = (char)NULL;
            j--;
            for (i = 0; i < length; i++, j--) {

               r_string[j] = i_string[i];
            }

            if (strcmp(i_string, r_string) == 0) {

                printf("%s\n", i_string); 
            }
        }
    }

    return 0;
}

Ответы [ 4 ]

3 голосов
/ 25 сентября 2010

Да, я думаю, что вы следуете совету R & K. Как сказал Хьюго, вы можете принять аргумент в качестве имени файла, но, ИМХО, для этой простой программы, я бы сказал, что использование параметра в качестве самого палиндрома может иметь больше смысла.

Кроме того, если вы дадите мне дополнительный совет, я бы отделил функциональность чтения строки от проверки, является ли она палиндромом или нет, потому что у вас сейчас есть дублированный код.

int ispalindrome(const char* c) { 
   size_t len = strlen(c);
   size_t limit = len/2;
   size_t i;
   for (i = 0; i < limit; i++) {
     if(c[i]!=c[len-i-1]) break; /* Different character found */
   }
   return i==limit; /* If we reached limit, it's a palyndrome */
}

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

ПРИМЕЧАНИЕ: отредактировано, чтобы отразить комментарий от Марка, большое спасибо, Марк!

3 голосов
/ 25 сентября 2010

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

Что касается фактического алгоритма, вам не нужно копировать обратную строку и затем сравнивать две строки. Вы можете выполнить проверку, используя только одну копию строки и указатель на обоих концах, оба перемещаются к середине.

Вот код, демонстрирующий принцип:

char* a = /* pointer to first character in string */;
char* b = /* pointer to last character in string (excluding the null terminator) */;

while (a < b && *a == *b)
{
    a++;
    b--;
}

if (a >= b)
{
    // Is palindrome.
}

Я согласен с Хавьером, что вы выделяете код проверки палиндрома в отдельную функцию.

1 голос
/ 25 сентября 2010

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

$ palindromes input*.txt # file patterns
$ find -name '*.txt' -print0 | xargs -0 palindromes

Это общее соглашение, которое поддерживается многими языками. Ниже приведены сценарии на Perl, Python, C, которые используются одинаково:

Usage: palindromes [FILE]
Print lines that are polindromes in each FILE.

With no FILE, or when FILE is -, read standard input.

в Perl

#!/usr/bin/perl -w
while (<>) { # read stdin or file(s) specified at command line
    $line = $_;
    s/^\s+//; # remove leading space
    s/\s+$//; # remove trailing space
    print $line if $_ eq reverse $_; # print line with a palindrome
}

в Python

#!/usr/bin/env python
import fileinput, sys

for line in fileinput.input(): # read stdin or file(s) specified at command line
    s = line.strip()    # strip whitespace characters
    if s == s[::-1]: # is palindrome
        sys.stdout.write(line)

в С

#!/usr/local/bin/tcc -run -Wall
#include <ctype.h>
#include <errno.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

enum { 
  MATCH,
  NO_MATCH,
  ERROR 
};

bool is_palindrome(char *first, char *last) {
  /** Whether a line defined by range [first, last) is a palindrome.

      `last` points either to '\0' or after the last byte if there is no '\0'.
      Leading and trailing spaces are ignored.
      All characters including '\0' are allowed
  */
  --last; // '\0'
  for ( ; first < last && isspace(*first); ++first); // skip leading space
  for ( ; first < last && isspace(*last); --last);   // skip trailing space
  for ( ; first < last; ++first, --last)
    if (*first != *last)
      return false;
  return true;
}

int palindromes(FILE *fp) {
  /** Print lines that are palindromes from the file.

      Return 0 if any line was selected, 1 otherwise;
      if any error occurs return 2
   */
  int ret = NO_MATCH;

  char *line = NULL;
  size_t line_size = 0; // line size including terminating '\0' if any
  ssize_t len = -1;     // number of characters read, including '\n' if any,
                        // . but not including the terminating '\0'
  while ((len = getline(&line, &line_size, fp)) != -1) {
    if (is_palindrome(line, line + len)) {
      if (printf("%s", line) < 0) {
        ret = ERROR;
        break;
      }
      else
        ret = MATCH;
    }
  }
  if (line)
    free(line);
  else 
    ret = ERROR;

  if (!feof(fp))
    ret = ERROR;
  return ret;
}

int main(int argc, char* argv[]) {
  int exit_code = NO_MATCH;
  if (argc == 1) // no input file; read stdin
    exit_code = palindromes(stdin);
  else {
    // process each input file
    FILE *fp = NULL;
    int ret = 0;
    int i;
    for (i = 1; i < argc; i++) { 
      if (strcmp(argv[i], "-") == 0)
        ret = palindromes(stdin);
      else if ((fp = fopen(argv[i], "r")) != NULL) {
        ret = palindromes(fp);
        fclose(fp);
      } else {
        fprintf(stderr, "%s: %s: could not open: %s\n",
                argv[0], argv[i], strerror(errno));
        exit_code = ERROR;
      }
      if (ret == ERROR) {
        fprintf(stderr, "%s: %s: error: %s\n",
                argv[0], argv[i], strerror(errno));
        exit_code = ERROR;
      } else if (ret == MATCH && exit_code != ERROR) 
        // return MATCH if at least one line is a MATCH, propogate error
        exit_code = MATCH;
    }
  }
  return exit_code;
}

Статус выхода равен 0, если выбрана какая-либо строка, в противном случае - 1; если возникает какая-либо ошибка, статус выхода равен 2. Он использует GNU getline(), который допускает произвольные большие строки в качестве ввода.

1 голос
/ 25 сентября 2010

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

Например, sort.Если вы не укажете никаких аргументов, содержимое из stdin будет отсортировано.В противном случае содержимое файла, имя которого вы указали, будет отсортировано.Обрабатываются не сами аргументы.

Код для этого будет выглядеть примерно так:

FILE * input = stdin;
if (argc > 1)
{
  input = fopen(argv[1], "r");
  // handle possible errors from the fopen
}

while (fscanf(input, "%s", i_string) != EOF)
  // check if i_string is a palindrome and output to stdout

Кроме того, вы должны быть осторожны с переполнением буфера, указанным Марком Байерсом.

Вы неправильно обрабатываете чтение строк.Буфер i_string не инициализирован, и даже если бы это было так, вам следует ограничить число байтов, которые читает scanf, чтобы избежать упомянутого переполнения:

char i_string[1000];
while (scanf("999%s", i_string) != EOF)
  if (is_palindrome(i_string)) /* Use any function defined in the other answers */
    printf("%s\n", i_string);

Вы должны всегда резервировать еще один байт (1000 против999) для учета пустого терминатора строки.Если вы хотите разрешить строки произвольной длины, я думаю, вам придется динамически распределять буфер и изменять его размер в случае присутствия больших строк.Это было бы немного сложнее.

...