Ejercicios resueltos laboratorio 14 - Aritmética de enteros con cadenas

Asignatura: Fundamentos de Informática
Especialidad: Electrónica - UPV/EHU
Curso académico: 2013-2014
Profesor: Ismael Etxeberria Agiriano

Ejercicio 14-001: SumaStrs

Utilizaremos el algoritmo de toda la vida para sumar, es decir, empezaremos por el dígito menos significativo de cada uno de los sumandos (el que está más a la derecha al final de la cadena) e iremos sumándolos teniendo en cuenta el acarreo o llevada. Cuando hayamos terminado con todos los dígitos de uno de los sumandos pero no con los del otro podremos suponer que el resto de los dígitos a la izquierda son ceros, siguiendo la norma de que "los ceros a la izquierda no valen nada".

No sabemos cuál será la longitud del resultado, pero supondremos que será la del mayor de los sumandos. En caso de que tras sumar nos quede una llevada por computar, si es posible desplazaremos todo el resultado a la derecha para incluir la última llevada; si ya hemos utilizado toda la cadena (según el valor de TOPE) devolveremos un 1 indicando que ha habido sobrepasamiento, devolviendo un 0 en caso contrario.

Podemos dividir el programa principal y la función propuesta para que ambos se pongan de acuerdo en el tamaño TOPE de las cadenas, así como en el prototipo.

Como ya hemos visto anteriormente, en el lenguaje C esto se realiza mediante ficheros de cabeceras, de extensión *.h (del inglés, headers). Normalmente la inclusión de un fichero de cabeceras no debe suponer un aumento en el tamaño del programa resultante, es decir, no se debe especificar en ellos código. Para eso están las bibliotecas, donde se guardaría la función propuesta, SumaStrs.

Para esta función y con previsión de la codificación de otras funciones el fichero de cabeceras de aritmética con cadenas podría ser:


/* AritStrs.h
 * Módulo de aritmética de enteros con cadenas.
 */

#define TOPE 25

int SumaStrs (char *res, const char *num1, const char *num2);

Hemos antepuesto const a la declaración de parámetro de los dos sumandos para indicar que no se va a modificar la cadena. De hecho esta declaración va a proteger la implementación de la función de modificaciones involuntarias.

A modo ilustrativo hemos intercambiado declaraciones tipo puntero como char *res con declaraciones tipo vector como char res[] sin ningún problema. Estos dos modos son intercambiables para el paso de parámetros pero no en la declaración de una variable local.

Adicionalmente, hemos utilizado dos funciones locales (que sólo tienen importancia dentro de este módulo): Digito y DesplazaDcha. Para evitar choques con funciones que se llamen igual en otros módulos las declaramos como static, lo que hace que no se puedan ver y/o utilizar fuera del módulo. Estas funciones se describen a continuación.

Una posible implementación de la función SumaStrs se proporciona a continuación:


/* AritStrs.c
 * Módulo de aritmética de enteros con cadenas.
 */
#include <string.h>
#include "AritStrs.h"

/* Prototipos de funciones locales.
 * Como no queremos exportarlas anteponemos la palabra static a su
 * definición. Así sólo son visibles dentro de este programa y se pueden
 * tener funciones con el mismo nombre en otros módulos */
static int  Digito (const char *num, int pos);
static void DesplazaDcha (char *num);

/* Sumador de números de longitud arbitraria expresados como cadena de
 * caracteres.
 *
 * Se supone que ambos operandos contienen una cadena positiva, es decir,
 * que no tienen signo. */
int SumaStrs (char res[], const char nu1[], const char nu2[])
{
  int l1, l2, l3, l4; /* Longitudes de las cadenas */
  int llevo;          /* Llevada de la suma */
  int s;              /* Suma parcial de dos dígitos más llevada */

  l1 = strlen (nu1);        /* l1: longitud de nu1 */
  l2 = strlen (nu2);        /* l2: longitud de nu2 */
  l4 = l3 = l1 > l2? l1:l2; /* l3 y l4: el mayor de entre l1 y l2 */
  res [l3] = '\0';          /* Ponemos el terminador a la cadena resultante */
  llevo = 0;                /* Al principio no hay llevada en la suma */

  while (l3 > 0) { /* Vamos de derecha a izquierda */
    s = Digito (nu1, --l1) + Digito (nu2, --l2) + llevo; /* Suma parcial */
    res [--l3] = '0' + s % 10; /* Unidades de s convertidas a letra */
    llevo = s / 10;            /* La llevada son las decenas de s */
  }

  if (llevo) {
    if (l4 == TOPE) /* l4 es la longitud de la cadena resultante */
      return 1; /* Sobrepasamiento: no me cabe la llevada en res */
    DesplazaDcha (res); /* Si no hay sobrepasamiento desplazar */
    res [0] = '1';      /*   e insertar la llevada */
  }
  return 0; /* Si llego aquí quiere decir que no hay sobrepasamiento */
}

La función Digito obtiene el dígito numérico (no carácter) en una posición dada del número, devolviendo un cero si se trata de una posición negativa. La definición de esta función puede ser:


/* Devuelve el dígito (int) correspondiente al carácter en la posición pos,
 * considerando un cero a la izquierda cuando se hace referencia a una
 * posición negativa.
 *
 * Ejemplos:
 * - Digito ("46",  0) -> 4
 * - Digito ("46",  1) -> 6
 * - Digito ("46", -2) -> 0 (dos ceros a la izquierda 0046) */
static int Digito (const char *num, int pos)
{
  if (pos < 0)
    return 0;
  return num [pos] - '0';/* Ej. '1' - '0' -> 1 ya que 31 - 30 -> 1 */
}

La función DesplazaDcha copia toda la cadena una posición a la derecha, lo cual sirve en nuestra función para introducir la última llevada. La definición de esta función puede ser:


/* Desplaza una cadena a la derecha, manteniendo el primer carácter.
 * Si antes contenía "Hola" luego contendrá "HHola" */
static void DesplazaDcha (char *num)
{
  int lon;

  lon = strlen (num);
  while (lon >= 0) {
    num [lon + 1] = num [lon];
    lon--;
  }
}

Se ilustra un programa principal con una llamada convencional, una llamada con sobrepasamiento y una llamada en la que los operandos se introducen del teclado, teniendo en cuenta el tamaño máximo reservado para las cadenas.


/* 14-001.c (laboratorio)
 *
 * Programa que demuestra el uso del Sumador de números naturales positivos
 * (sin signo) de longitud arbitraria expresados mediante cadenas de caracteres.
 */

#include <stdio.h>
#include <stdlib.h>
#include "aritstrs.h"

int main (void)
{
  char n1[TOPE+1], n2[TOPE+1], rs[TOPE+1];
  int  sob;

    /* Un caso simple */
  sob = SumaStrs (rs, "56789", "9521032");
  printf ("    56789\n"
          "+ 9521032\n"
          "---------\n"
          "  %s\n\n", rs);

    /* Sobrepasamiento cuando el TOPE es 25: al número mayor le sumamos 1 */
  sob = SumaStrs (rs, "9999999999999999999999999", "1");
  printf ("(%d)%s\n\n", sob, rs);

    /* Caso general. Ojo: no introducir un número de mayor longitud que TOPE */
  printf ("Introduce un número entero (máximo %d dígitos):   ", TOPE);
  gets (n1);
  printf ("Introduce otro número entero (máximo %d dígitos): ", TOPE);
  gets (n2);

  sob = SumaStrs (rs, n1, n2);
    /* Pasamos la anchura de la cadena como parámetro: %*s */
  printf ("%*s\n+%*s\n---------------------------\n%s%*s\n",
            TOPE+2, n1, TOPE+1, n2,
            sob? " 1":"  ", TOPE, rs);

  system ("pause");
  return 0;
}

Ejercicio 14-002: SubsStrs

El algoritmo para la resta será de similar características. En este caso no podemos tener un sobrepasamiento pero sí podemos tener como resultado un número negativo, condición que será expresada devolviendo el signo (0 positivo, 1 negativo).

Una particularidad de este algoritmo es que vamos a buscar cuál de los dos números es mayor ya que en función de eso se podrá deducir el signo del resultado. Además, siempre tenemos que restar al mayor el menor.

Es buen ejercicio descubrir los entresijos del algoritmo analizando el código resultante.

Si queremos plantear la realización de una biblioteca de operaciones aritméticas con cadenas introduciríamos en el fichero de cabeceras anterior nuestra nueva función, conservando la anterior:


/* AritStrs.h */
 * Módulo de aritmética de enteros con cadenas.
 */

#define TOPE 25

int SumaStrs (char *res, const char *num1, const char *num2);
int SubsStrs (char *res, const char *num1, const char *num2);

Podemos introducir la función en el mismo fichero fuente que SumaStrs.

Una posible implementación de la función SubsStrs se proporciona a continuación:


/* Prototipo de otra función local */
static void EliminaCerosIzda (char *num);

/* Restador de números de longitud arbitraria expresados como cadena de
 * caracteres.
 *
 * Se supone que ambos operandos contienen una cadena positiva, es decir,
 * que no tienen signo.  */
int SubsStrs (char *res, const char *nu1, const char *n2)
{
  int l1, l2, tmp;
  char *n1, *n2;
  int r;
  int signo;
  int debo;

  l1 = strlen (nu1);
  l2 = strlen (nu2);
  if      (l1 > l2)               signo = 0;
  else if (l2 > l1)               signo = 1;
  else if (strcmp (nu1, nu2) < 0) signo = 1;
  else                            signo = 0;
  if (signo) {
    n1 = nu2;
    n2 = nu1;
      /* Intercambiar longitudes */
    tmp = l1;
    l1 = l2;
    l2 = tmp;
  }
  else {
    n1 = nu1;
    n2 = nu2;
  }
  res [l1] = '\0'; /* Ponemos el terminador a la cadena resultante */
  debo = 0;        /* Al principio no debo nada en la resta */

  while (l1 > 0) {
    r = Digito (n1, --l1) - Digito (n2, --l2) - debo;
    if (r < 0) {
      r += 10;
      debo = 1;
    }
    else
      debo = 0;
    res [l1] = '0' + r % 10; /* Unidades de r convertidas a letra */
  }

  EliminaCerosIzda (res);

  return signo;
}

Además de la función local Digito cuya codificación se ha proporcionado anteriormente se ha utilizado la función EliminaCerosIzda.


  /* Eliminar todos los ceros a la izquierda (menos el último si es 0) */
static void EliminaCerosIzda (char *num)
{
  int n0; /* Número de ceros a la izquierda */
  int nd; /* Número de dígitos significativos */

  if (num [0] == '0') { /* Si el primer carácter es '0' */
      /* Contar ceros */
    n0 = 0;
    while (num [n0] == '0' && num [n0] != '\0')
      n0++;
    if (num [n0] == '\0') /* Si todos son ceros */
      num [1] = '\0';
    else { /* copiar los digitos significativos sobreescribiendo los ceros */
      nd = 0;
      while (num [n0+nd] != '\0')
        num [nd++] = num [n0+nd];
      num [nd] = '\0';
    }
  }
}

Se ilustra un programa principal con una llamada convencional, una llamada con resultado negativo y una llamada en la que los operandos se introducen del teclado, teniendo en cuenta el tamaño máximo reservado para las cadenas.


/* 14-002.c
 *
 * Programa que demuestra el uso del Restador de números positivos de longitud
 * arbitraria expresados como cadena de caracteres.
 */

#include <stdio.h>
#include "AritStrs.h"

void main (void)
{
  char n1[TOPE+2]; /* Número máximo de dígitos + signo + terminador */
  char n2[TOPE+2];
  char rs[TOPE+2];

    /* Un caso simple */
  SubsStrs (rs, "56789", "52103");
  printf ("  56789\n"
          "- 52103\n"
          "---------\n"
          "   %s\n\n", rs);

  if (SubsStrs (rs, "1", "21"))
    printf ("-%s\n\n", rs);

    /* Caso general. Ojo: no introducir un número de mayor longitud que TOPE */
  printf ("Introduce un número entero (máximo %d dígitos):   ", TOPE);
  gets (n1);
  printf ("Introduce otro número entero (máximo %d dígitos): ", TOPE);
  gets (n2);
  if (SubsStrs (rs, n1, n2))
    printf ("%12s\n-%11s\n------------\n -%10s\n", n1, n2, rs);
  else
    printf ("%12s\n-%11s\n-------------\n%12s\n", n1, n2, rs);
}

Ejercicio 14-003: SumaConSigno y SubsConSigno

La resolución consiste básicamente en una llamada a la función de suma (SumaStrs) o a la de resta (SubsStrs) de cadenas, calculando el signo resultante.

Según sean los signos de los operandos n1 y n2, la operación a realizar para la suma con signo se detalla en la tabla 14.1.

n1+n2
Caso Signo n1 Signo n2 Operación a realizar Función
1+ + n1+n2 SumaStrs
2- - -(|n1|+|n2|) SumaStrs
3- + n2-|n1| SubsStrs
4+ - n1-|n2| SubsStrs

Tabla 14.1. Correspondencia de la suma según signos de los operandos.

Para saber si un número n expresado como cadena es positivo o negativo será suficiente con mirar si el primer carácter de la cadena es el signo '-'. La Tabla 14.2 muestra la condición en ambos casos.

SignoVerificaciónEstilo alternativo
Es negativon[0] == '-'*n == '-'
Es positivon[0] != '-'*n != '-'

Tabla 14.2. Verificación del signo de un número expresado como cadena

Cuando querramos realizar la llamada a la función de suma (SumaStrs) o a la de resta (SubsStrs), como estas funciones no entienden de signos tendremos que enviarles la subcadena sin el signo, es decir, si el número n es negativo realizaremos la llamada con eliminando el signo, |n|, mediante &n[1] o, lo que es lo mismo, n+1; si n es positivo |n| es &n[0] o, lo que es lo mismo, n.

Aclarados estos puntos podemos ver una posible resolución de la función de SumaconSigno, que utiliza la función DesplazaDcha ya introducida y explicada anteriormente en este capítulo. No vamos a volver a especificar el prototipo.


int SumaConSigno (char res[], const char nu1[], const char nu2[])
{
  int signo;

  if (*nu1 != '-' && *nu2 != '-')    /* Caso 1 */
    return SumaStrs (nu1, nu2, res); /* La función termina */

  if (*nu1 == '-' && *nu2 == '-') {              /* Caso 2 */
    *res = '-';
    return SumaStrs (&nu1[1], &nu2[1], &res[1]); /* La función termina */
  }

  if (*nu1 == '-') signo = SubsStrs (nu2, &nu1[1], res); /* Caso 3 */
  else             signo = SubsStrs (nu1, &nu2[1], res); /* Caso 4 */
  if (signo) {
    DesplazaDcha (res);
    *res = '-';
  }

  return 0;
}

Según sean los signos de los operandos n1 y n2, la operación a realizar para la resta con signo se detalla en la tabla 14.2.

n1-n2
Caso Signo n1 Signo n2 Operación a realizar Función
1+ - n1+|n2| SumaStrs
2- + -(|n1|+n2) SumaStrs
3+ + n1-n2 SubsStrs
4- - |n2|-|n1| SubsStrs

Tabla 14.3. Correspondencia de la resta según signos de los operandos.

Todos los casos con suma (SumaStrs) tienen peligro de sobrepasamiento y es lo que devolverá esta función.

Por todas las analogías con la función SumaConSigno el resto de las explicaciones no aportan gran cosa. Por ello podemos mostrar una posible resolución de la función SubsConSigno:


int SubsConSigno (char res[], const char nu1[],
const char nu2[])
{
  int signo;

  if (*nu1 != '-' && *nu2 == '-')            /* Caso 1 */
    return SumaStrs (nu1, &nu2[1], res);     /* La función termina */

  if (*nu1 == '-' && *nu2 != '-') {          /* Caso 2 */
    *res = '-';
    return SumaStrs (&nu1[1], nu2, &res[1]); /* La función termina */
  }

  if (*nu1 != '-') signo = SubsStrs (nu1, nu2, res);         /* Caso 3 */
  else             signo = SubsStrs (&nu1[1], &nu2[1], res); /* Caso 4 */
  if (signo) {
    DesplazaDcha (res);
    *res = '-';
  }

  return 0;
}

Un programa que utilice la aritmética con signo aquí especificada requerirá la definición de los números con un tamaño suficiente de acuerdo al máximo número de dígitos TOPE. Consecuentemente, la correspondiente cadena tendrá TOPE caracteres más uno para el signo más un terminador.

El fichero de cabeceras final AritStrs.h incluyendo todas las funciones accesibles podría quedar como sigue:


/* AritStrs.h */
 * Módulo de aritmética de enteros con cadenas.
 */

#define TOPE 25

int SumaStrs (char *res, const char *num1, const char *num2);
int SubsStrs (char *res, const char *num1, char *num2);
int SumaConSigno (char *res, const char *num1, const char *num2);
int SubsConSigno (char *res, const char *num1, const char *num2);

Se ilustra un programa principal con llamadas cubriendo los casos posibles.


/* 14-003.c (laboratorio)
 *
 * Programa que demuestra el uso del la aritmética con signo de números
 * de longitud arbitraria expresados como cadena de caracteres.
 */

#include <stdio.h>
#include <stdlib.h>
#include "AritStrs.h"

int main (void)
{
  char rs[TOPE+2]; /* Nº máximo + signo + terminador */

  SumaConSigno (rs, "12", "10");
  printf (" 12 +  10 =  %s\n", rs);
  SumaConSigno (rs, "-12", "-10");
  printf ("-12 + -10 = %s\n", rs);
  SumaConSigno (rs, "-12", "10");
  printf ("-12 +  10 =  %s\n", rs);
  SumaConSigno (rs, "12", "-10");
  printf (" 12 + -10 =   %s\n", rs);

  SubsConSigno (rs, "12", "-10");
  printf (" 12 + -10 =   %s\n", rs);
  SubsConSigno (rs, "-12", "10");
  printf ("-12 +  10 =  %s\n", rs);
  SubsConSigno (rs, "12", "10");
  printf (" 12 +  10 =  %s\n", rs);
  SubsConSigno (rs, "-12", "-10");
  printf ("-12 + -10 = %s\n", rs);

  system ("pause");
  return 0;
}