Problema 3.6

.
Enunciado
Se desea construir una librería de funciones para agilizar el manejo de cadenas de caracteres.

A continuación se detalla el prototipo de cada una de las funciones que la librería (unit) deberá incluir.


función indexOf

11:
12:   // retorna la posicion de la primer ocurrencia
13:   // del caracter c dentro del string s contando
14:   // a partir del caracter offset.
15:   // Si s no contiene ningun caracter c entonces 
16:   // retorna un valor negativo
17:   function indexOf(s: string
18:                   ;c: char
19:                   ;offset: integer): integer;
20:

Basicamente lo que nos piden es recorrer el el string s comenzando desde la posición offset. Lo recorremos mientras no lleguemos al final y mientras no encontremos el caracter que buscamos: c.

Como vemos, cuando terminamos de recorrer el string preguntamos por que salió del while. Si i se mantiene menor o igual que la longitud de s entonces quiere decir que el caracter que buscamos se encontró en la posición i. Si no, significa que el while cortó porque llegamos al último caracter y nunca aparecío el caracter que buscamos. El caracter no existe y entonces retornamos -1 (un valor negativo).

Veamos el código Pascal.

144:
145:function indexOf(s: string
146:                ;c: char
147:                ;offset: integer): integer;
148:var i: integer;
149:begin
150:   i:=offset;
151:   while( (i<=length(s)) AND (s[i]<>c) ) do begin
152:      i:=i+1;
153:   end;
154:
155:   if( i<=length(s) ) then begin
156:      indexOf:=i;
157:   end else begin
158:      indexOf:=-1;
159:   end;
160:end;
161:

función indexOf (sobrecargada)

 5:
 6:   // retorna la posicion de la primer ocurrencia
 7:   // del caracter c dentro del string s.
 8:   // Si s no contiene ningun caracter c entonces 
 9:   // retorna un valor negativo
10:   function indexOf(s: string; c :char): integer;
11:

Esta función es una sobrecarga de la anterior. Decimos que una función está sobrecargada cuando está definida e implementada más de una vez pero con diferentes parámetros.

La versión anterior de indexOf recibía 3 parámetros: el string s, el caracter a buscar c y la posición desde la cual queríamos buscar offset. En esta versión de la función solo recibimos los primeros dos parámetros ya que la búsqueda del caracter debe realizarse desde la primer posición del string.

Resolver esta versión de indexOf es muy simple. Solo tenemos que invocar a la otra versión de indexOf pasándole el valor 1 en el argumento offset. Así buscará el caracter c desde la primer posición del string. Veamos el código Pascal.

139:
140:function indexOf(s:string; c:char): integer;
141:begin
142:   indexOf:=indexOf(s,c,1);
143:end;
144:

función lastIndexOf

20:
21:   // retorna la posicion de la ultima ocurrencia
22:   // del caracter c dentro del string s
23:   // Si s no contiene ningun caracter c entonces 
24:   // retorna un valor negativo  
25:   function lastIndexOf(s: string;c: char): integer;
26:

Esta función es similar a la anterior pero en lugar de buscar la primer ocurrencia del caracter c dentro de s busca la última. La forma de resolverla es similar a la de indexOf pero comenzando a recorrer el string desde atrás. Desde la última posición mientras no encontremos lo que buscamos y mientras no lleguemos a la primer posición del string.

El código Pascal es:

161:
162:function lastIndexOf(s:string;c:char):integer;
163:var i:integer;
164:begin
165:   i:=length(s);
166:   while( (i>=1 ) AND (s[i]<>c) ) do begin
167:      i:=i-1;
168:   end;
169:
170:   if( i>0 ) then begin
171:      lastIndexOf:=i;
172:   end else begin
173:      lastIndexOf:=-1;
174:   end;
175:end;
176:

función substring

26:
27:   // retorna la subcadena de s comprendida entre 
28:   // los caracteres cuyas posiciones son 
29:   // desde (inclusive) y hasta (no inclusive)
30:   function substring(s:string;
31:                      desde,hasta: integer): string;
32:

La idea de esta función es "mejorar" la función copy provista en librerías de Pascal. La función substring recibe el string s, desde y hasta y debe retornar la subcadena comprendida entre los caracteres desde (inclusive) hasta hasta (no inclusive).

La función se resuelve invocando a la función copy. La diferencia entre nuestra función substring y la función copy es que copy recibe la posición desde y la cantidad de caracteres a copiar mientras que substring recibe la posición desde y la posición hasta. Por lo tanto, para resolver nuestra función invocando a la la función copy tenemos que calcular la cantidad de caracteres comprendidos entre la posición desde y la posición hasta. Dicha cantidad la podemos obtener con la diferencia: hasta-desde.

176:
177:function substring(s:string; desde,hasta:integer):string;
178:begin
179:   substring:=copy(s,desde, hasta-desde);
180:end;
181:

función substring (sobrecargada)

32:
33:   // retorna la subcadena de s comprendida entre el
34:   // caracter desde y el ultimo caracter. Es decir:
35:   // desde desde hasta el ultimo
36:   function substring(s:string
37:                     ;desde: integer): string;
38:

Esta versión sbrecargada de la función substring solo recibe la posición desde y debe retornar la subcadena de s comprendida entre la posición desde (inclusive) y el último caracter. Es decir: desde desde hasta el final.

Resolver esta función es muy simple: solo tenemos que invocar a la otra versión de substring. El parámetro desde lo tenemos y para pasarle el parámetro hasta le pasamos el length(s). Desde desde hasta el final.

Notemos que invocamos a la otra versión de substring pasándole length(s)+1. Esto se debe a que el parámetro hasta es NO INCLUSIVE. Por lo tanto le pasamos 1 más que la posición del último caracter para que solo se considere hasta las posición del último.

181:
182:function substring(s:string; desde: integer): string;
183:begin
184:   substring:=substring(s,desde,length(s)+1);
185:end;
186:

función replicate

38:
39:   // retorna un string compuesto por n caracteres c
40:   function replicate(c: char; n: integer): string;
41:

Esta función recibe un caracter c y una cantidad n y debe retornar un string compuesto de n caracteres c. Por ejemplo: replicate('x',5) debe retornar el string: 'xxxxx'.

Tenemos que generar un string concatenando n veces el caracter c. Por eso definimos un "acumulador de caracteres" aux. Lo inicializamos con '' (dos comillas simples sin espacio en el medio), es decir: un string vacio. Luego, en un for que itera exactamente n veces concatenamos en aux el valor de c. El resultado será un string compuesto por n caracteres c.

210:
211:function replicate(c:char; n:integer):string;
212:var aux:string; i:integer;
213:begin
214:   aux:='';
215:   for i:=1 to n do begin
216:      aux:=aux+c;
217:   end;
218:   replicate:=aux;
219:end;
220:

funciones xpad

41:
42:   // retorna un string compuesto por n-length(s) 
43:   // caracteres c y luego s. Si n<=length(s) 
44:   // retorna s;
45:   function lpad(s: string
46:                ;c: char
47:                ;n: integer): string;
48:
49:   // idem lpad pero generando los caracteres
50:   // a la derecha
51:   function rpad(s: string
52:                ;c: char
53:                ;n: integer): string;
54:
55:   // idem lpad y rpad pero generando la mitad de 
56:   // los caracteres a la izquierda y la otra mitad
57:   // a la derecha
58:   function cpad(s: string
59:                ;c: char
60:                ;n: integer): string;
61:

La idea de estas funciones es formatear el string s que reciben como parámetro retornandolo alineado a izquierda (lpad), a derecha (rpad) o centrado (cpad)

Todas las funciones reciben s (el string a formatear), c (el caracter de relleno) y n (la cantidad de caracteres que debe tener el string de retorno.

Por ejemplo:

• lpad('HolaMundo','X',15) debe retornar 'XXXXXXHolaMundo'. Es decir: completó con 6 caracteres 'X' a la izquierda el string 'HolaMundo' haciendo un total de 15 caracteres.
  
• rpad('HolaMundo','X',15) debe retornar 'HolaMundoXXXXXX'. Idéntico al anterior pero completa con caracteres a derecha.
• cpad('HolaMundo','X',15) debe retornar 'XXXHolaMundoXXX').
  

Para resolver estas funciones utilizaremos la función replicate con la que podremos generar los caracteres necesarios para completar el string.

Vemos que la única diferencia entre lpad y cpad es que la primera retorna el resultado de replicate + s y la segunda concatena s y luego el resultado de replicate.

Para la función cpad tendremos que dividir por 2 el valor de n para ver cuantos caracteres debemos concatenar a la izquierda y cuantos a la derecha. Obviamente la división tiene que ser entera por lo tanto, si n-length(s) es impar, concatenaremos la mitad menos 1 a la izquierda y la mitad más 1 a la derecha.

El código de las tres funciones lo vemos a continuación.

220:
221:function lpad(s:string; c:char; n:integer):string;
222:var len:integer;
223:begin
224:   len:=length(s);
225:   if( n<=len ) then begin
226:      lpad:=s;
227:   end else begin
228:      lpad:=replicate(c,n-len)+s;
229:   end;
230:end;
231:
232:function rpad(s:string; c:char; n:integer):string;
233:var len:integer;
234:begin
235:   len:=length(s);
236:   if( n<=len ) then begin
237:      rpad:=s;
238:   end else begin
239:      rpad:=s+replicate(c,n-len);
240:   end;
241:end;
242:
243:function cpad(s:string; c:char; n:integer):string;
244:var len,izq,der:integer;
245:begin
246:   len:=length(s);
247:   if( n<=len ) then begin
248:      cpad:=s;
249:   end else begin
250:      izq:=(n-len) div 2;
251:      der:=(n-len)-izq;
252:      cpad:=replicate(c,izq)+s+replicate(c,der);
253:   end;
254:end;
255:

funciones xtrim

61:
62:   // elimina los blancos que tenga el string s
63:   // a la izquieda
64:   function ltrim(s: string): string;
65:
66:   // elimina los blancos que tenga el string s
67:   // a la derecha
68:   function rtrim(s: string): string;
69:
70:   // elimina los blancos que tenga el string s
71:   // a ambos lados, es el ltrim(rtrim(s))
72:   function trim(s: string): string;
73:

Las funciones ltrim, ctrim y trim eliminan los espacios en blanco que pueda contener el string s. Por ejemplo:

• ltrim('......HolaMundo') debe retornar: 'HolaMundo'
• rtrim('HolaMundo.......') debe retornar: 'HolaMundo'
• trim('....HolaMundo....') debe retornar: 'HolaMundo'

Para resolver ltrim la idea es recorrer el string de izquierda a derecha (es decir: desde el caracter en la posición 1 en adelante) mientras no lleguemos al final y (esto es lo que nos intereza) mientras el caracter sub i sea '.' (un espacio en blanco). Cuando termina el while con el que iteramos el string preguntamos por el valor de i. Si i es menor que el length(s) entonces el caracter sub i es el primer caracter distinto de '.' comenzando desde la izquierda. Debemos retornar el substring desde comprendido entre las posiciones i y length(s)+1.

Para rtrim el análisis es el mismo, solo que comenzando desde el último caracter.

Como vemos, ahora i comienza en length(s) y dentro del while lo decrementamos. El while itera mientras el caracter sub i sea blanco y mientras no lleguemos al primer caracter. Cuando corta el while, si i es menor o igual que cero entonces el string no tenía blancos a derecha. Pero si i es mayor que cero significa que tenemos que retornar el substring comprendido entre los caracteres 1 e i+1 (no inclusive).

Por último, la función trim se puede resolver como el ltrim(rtrim(s)).

El código Pascal:

285:
286:function trim(s:string):string;
287:begin
288:   trim:=ltrim(rtrim(s));
289:end;
290:

funciones toUpperCase, toLowerCase, isEmpty

73:
74:   // retorna true si s es vacio (''), o false
75:   // si tiene al menos algun caracter
76:   function isEmpty(s:string):boolean;
77:
78:   // retorna un string como s pero en mayuscula
79:   function toUpperCase(s:string):string;
80:
81:   // retorna un string como s pero en muniscula
82:   function toLowerCase(s:string):string;
83:

Estas funciones simplemente cambian el nombre a funciones que ya existen. Salvo isEmpty que retorna true o false según el string s sea igual a ' ' (dos comillas simples).

Directamente veamos el código Pascal.

284:
285:function toUpperCase(s:string):string;
286:begin
287:   toUpperCase:=upCase(s);
288:end;
289:
290:// retorna un string como s pero en muniscula
291:function toLowerCase(s:string):string;
292:begin
293:   toLowerCase:=lowerCase(s);
294:end;
295:
296:function isEmpty(s:string):boolean;
297:begin
298:   isEmpty:=length(s)=0;
299:end;
300:

funciones tokenizer, tokenCount y tokenAt

 83:
 84:   // considera al string s como varios strings 
 85:   // separados por el separador sep permitiendo
 86:   // iterarlo y obtener cada token (substring entre
 87:   // sep y sep) contenido en s
 88:   function tokenizer(s:string
 89:                     ;sep:char
 90:                     ;var buff:string
 91:                     ;var offset:integer):boolean;
 92:
 93:   // cuenta la cantidad de tokens contenidos en s
 94:   function tokenCount(s:string;sep:char): integer;
 95:
 96:   // retorna el token que se encuentra 
 97:   // en la posicion i
 98:   function tokenAt(s:string
 99:                   ;sep:char;i:integer): string;
100:

Para explicar estas funciones vamos a considerar la siguiente cadena como ejemplo:

s := 'Pablo|Juan|Jose|Pedro'

Vemos que el string s contiene una lista de nombres separados por un caracter '|' (pipe). Llamaremos token a cada uno de los nombres, es decir: cada substring delimitado por (en este caso) pipes. Y llamaremos separador al caracter que separa los tokens. En este ejemplo el separador es el caracter '|'.

El string s (en este caso) tiene 4 tokens ('Pablo', 'Juan', Jose', 'Pedro'). Pero, si en lugar de considerar el separador '|' consideramos el separador 'J' entonces el string s tendrá 3 tokens: ('Pablo|', 'uan|', 'ose|Pedro').

Con esto podemos comenzar a analizar la función más simple: tokenCount. Esta función debe retornar la cantidad de tokens contenidos en un string, considerando un separador especificado.

Volviendo al ejemplo, si consideramos como separador al caracter '|' entonces el string contiene 4 tokens. Es decir: uno más que la cantidad de veces que aparece el caracter '|'. Ahora, si consideramos que el separador es el caracter 'J' entonces el string contiene 3 tokens, uno más que la cantidad de veces que aparece el caracter 'J'. Por lo tanto, para resolver la función tenemos que contar cuantas veces aparece el caracter separador y luego retornar ese valor más uno.

El único problema se puede presentar en el caso que el string s no contenga ningún caracter separador. En este caso consideraremos que todo el string es un token. El valor de retorno debe ser 1.

Recorremos el string y contamos cada vez que aparece un caracter separador. Notemos que cont comienza en 1 por lo tanto si no existe ninguna ocurrencia de sep estaremos retornando 1 (indicando que el string tiene 1 token). Pero si existen n ocurrencias entonces retornaremos n+1 ya que cont se inicializó en 1.

116:
117:function tokenCount(s:string;sep: char): integer;
118:var i,n,cont:integer;
119:begin
120:   n:=length(s);
121:   i:=0;
122:   cont:=1;
123:   while( i<=n ) do begin
124:      if( s[i]=sep ) then begin
125:         cont:=cont+1;
126:      end;
127:      i:=i+1;
128:   end;
129:
130:   tokenCount:=cont;
131:end;
132:

La función tokenizer se pensó para ser usada de la siguiente manera.

   1:
   2:uses untString;
   3:
   4:var
   5:   s,buff,token: string;
   6:   offset:integer;
   7:
   8:begin
   9:   s:='Pablo|Juan|Jose|Pedro';
  10:   offset:=1;
  11:   while( tokenizer(s,'|',buff,offset) ) do begin
  12:      // en cada iteracion buff contendra
  13:      // cada el valor de cada uno de los tokens
  14:      writeln(buff);
  15:   end;
  16:end.
  17:

En cada iteración la función asigna en buff el valor de cada token por lo tanto la salida del programa será la lista de tokens (nombres en este caso). El valor de retorno de la función tokenizer será true o false según queden más tokens o no en el string.

La estrategia será recibir por referencia el parámetro offset e incrementarlo cada vez que se invoque la función. offset debe comenzar en 1 por lo tanto la primera vez que se invoque a la función debemos retornar el substring contenido entre offset y la primer ocurrencia del caracter separador. Antes de salir debemos incrementar offset a "uno más" que la posición de la primer ocurrencia del separador. Así, la próxima vez que se invoque a la función retornaremos el segundo token.

Comenzamos preguntando si offset es mayor que la longitud del string s, en ese caso no quedan más tokens y la función debe retornar false. La sentencia exit finaliza la llamada a la función y retorna el control al programa principal (quien invocó a la función). Es decir: si offset es mayor que la longitud de s la función retorna false y termina allí. El resto del código no se ejecuta.

Ahora, si offset es menor que la longitud de s entonces tenemos que buscar la posición del próximo separador, considerando a partir del caracter en la posición offset. Por eso usamos las variables desde y hasta.

La variable desde se inicializa en offset y hasta en la primer ocurrencia del separador, contando desde offset (desde). Si ho hay más separadores entonces asignamos a hasta el valor de la cantidad de caracteres de s + 1 (recordemos que indexOf recibe el parámetro hasta como no inclusive).

El código Pascal es:

181:
182:function tokenizer( s:string; sep: char
183:                   ;var buff: string
184:                   ;var offset:integer):boolean;
185:var desde,hasta:integer;
186:begin
187:   if( offset>length(s) ) then begin
188:      tokenizer:=false;
189:      exit;
190:   end;
191:
192:   desde:=offset;
193:   hasta:=indexOf(s,sep,desde);
194:
195:   if( hasta<0 ) then begin
196:      hasta:=length(s)+1;
197:   end;
198:
199:   offset:=hasta+1;
200:
201:   buff:=substring(s,desde,hasta);
202:   tokenizer:=true;
203:end;
204:

Por último veamos el desarrollo de la función tokenAt. Esta función retorna el token que se encuentra en la posición i.

Simplemente "avanzamos" los tokens con tokenizer y retornamos el último token.

El código Pascal es:

106:
107:function tokenAt(s:string;sep: char
108:                ;i:integer): string;
109:var x:integer; offset:integer; buff:string;
110:begin
111:   offset:=1;
112:   for x:=1 to i do begin
113:      tokenizer(s,sep,buff,offset);
114:   end;
115:   tokenAt:=buff;
116:end;
117:

El código completo de untString.pas lo podemos ver en este enlace: untString.pas










.