david@ukma.UUCP (David Herron, NPR Lover) (11/23/85)
Everybody I've shown this program to has *groaned* and complained
about what a nasssty program it was... This program was written
to help decode a bitnet routing table that I had been netcopy'd
to me and didn't get translated into ascii. So after running dd
over it, the line markers had disappeared into never never land.
But from looking real closely at the file I could see that each
line was supposed to start with ROUTE..... thus this program:
I think it's *cute*!
#include <stdio.h>
main()
{
register int r, o, u, t, e;
while ((r = getchar()) != EOF) {
if (r == 'R')
if ((o = getchar()) == 'O')
if ((u = getchar()) == 'U')
if ((t = getchar()) == 'T')
if ((e = getchar()) == 'E')
printf("\nROUTE");
else
printf("ROUT%c", e);
else
printf("ROU%c", t);
else
printf("RO%c", u);
else
printf("R%c", o);
else
putchar(r);
}
putchar('\n');
}
--
David Herron, cbosgd!ukma!david, david@UKMA.BITNET.
Experience is something you don't get until just after you need it.jimc@ucla-cs.UUCP (12/03/85)
In article <2389@ukma.UUCP> david@ukma.UUCP (David Herron, NPR Lover) writes: >Everybody I've shown this program to has *groaned* ... >I think it's *cute*! >#include <stdio.h> >main() >{ > register int r, o, u, t, e; > while ((r = getchar()) != EOF) { > if (r == 'R') > if ((o = getchar()) == 'O') > if ((u = getchar()) == 'U') > if ((t = getchar()) == 'T') > if ((e = getchar()) == 'E') > printf("\nROUTE"); > else > printf("ROUT%c", e); > else > printf("ROU%c", t); > else > printf("RO%c", u); > else > printf("R%c", o); > else > putchar(r); > } > putchar('\n'); >} Yes, indeed, the above program is aesthetically disgusting. But what is wrong with it in practice? 1. It works only for that one pattern (not that files are often wiped like that, but let's keep our standards up). 2. The multiple if's and library calls can get lengthy on some mach- ines. 3. Using printf is expensive when you just want to concatenate strings on the way out. Here is a looping version. Isn't this one just as cute? #include <stdio.h> main(an, av) int an; char *av[]; /*When the pattern av[1] is found in stdin, a new- *line is put in front of it, the result going to *stdout. */ { register char c, *p, *r; if (an < 2) {puts("Usage: gorf pattern"); exit(1);} /*Idiotproof*/ for (p = av[1]; ; ) { c = getchar(); if (c == *p && c != '\0') { /*Char does match pattern (last term is *nitpick overkill since \0 unlikely in text). *Note, EOF doesn't match pattern.*/ if (*++p == '\0') putchar('\n'); /*Found whole pattern, write new- *line before it. Pattern dumped on next char.*/ } else { /*Char. doesn't match pattern*/ for (r = av[1]; r < p; ) putchar(*r++); /*Dump portion of pattern, *if any, that was matched*/ if (c == EOF) break; putchar(c); /*After which, write non-matching char.*/ p = av[1]; /*Again start looking for pattern*/ } } } (Bug: if the pattern is ROUTE and the text is ROUROUTE, the pattern will be missed. This is an easy fix. But if the pattern is TINTINABULATION and the text is TINTINTINABULATION, even with the above fix the pattern will be missed. It could be seen only with long and expensive pattern checking -- or does someone see a smart way to do it?
ken@rochester.UUCP (Ipse dixit) (12/04/85)
In article <7839@ucla-cs.ARPA> jimc@ucla-cs.UUCP (Jim Carter) writes: >(Bug: if the pattern is ROUTE and the text is ROUROUTE, the pattern will >be missed. This is an easy fix. But if the pattern is TINTINABULATION >and the text is TINTINTINABULATION, even with the above fix the pattern >will be missed. It could be seen only with long and expensive pattern >checking -- or does someone see a smart way to do it? Yes, in the chapter on string matching in Design and Analysis of Computer Algorithms (Aho, Hopcroft and Ullman?) you can see how to construct a finite state machine to recognize a substring anywhere in the input word. Basically, when a failure to match occurs, the machine goes back to the last state which it could be in. In your second example, when it fails to match the third T it goes back to the state it would have been in after seeing TINT. All the states can be computed in advance and the algorithm runs in linear time. Ken -- UUCP: ..!{allegra,decvax,seismo}!rochester!ken ARPA: ken@rochester.arpa USnail: Dept. of Comp. Sci., U. of Rochester, NY 14627. Voice: Ken!
abh6509@ritcv.UUCP (A. hudson) (12/04/85)
That program looks like it should first be modelled with a finite state diagram. A few theoretical considerations will quickly show if you are testing for impossible conditions or have redundant code. Or if a group of IF's are clumsily arranged, always testing true and therefore unnecesary. If that BITNET routine function exhibited none of those maladies then your cryptic style is functionally justified. Providing no one has to understand it or modify it later on. Andrew Hudson
avg@diablo.ARPA (12/05/85)
In article <7839@ucla-cs.ARPA> jimc@ucla-cs.UUCP (Jim Carter) commented on: >>#include <stdio.h> >>main() >>{ >> register int r, o, u, t, e; >> while ((r = getchar()) != EOF) { >> if (r == 'R') >> if ((o = getchar()) == 'O') >> if ((u = getchar()) == 'U') >> if ((t = getchar()) == 'T') >> if ((e = getchar()) == 'E') >> printf("\nROUTE"); >> else >> printf("ROUT%c", e); >> else >> printf("ROU%c", t); >> else >> printf("RO%c", u); >> else >> printf("R%c", o); >> else >> putchar(r); >> } >> putchar('\n'); >>} and submitted his own "improvement". My question is, "What is the original program supposed to do?" Judging from Jim's comments, he believes that input ROUROUTE should produce output ROU\nROUTE\n. It doesn't. However, input ROUXROUTE produces ROUX\nROUTE\n. So perhaps the answer to "What's wrong with this program?" is "It doesn't meet specs." On a very simple style level, what's wrong is that it uses nested if's when it could use if ... else if ... else if ... The following version corrects both complaints. The technique of getting the first char before the loop is called "priming", and has wide applicability. #include <stdio.h> main() { register int r, o, u, t, e; r = getchar(); while (r != EOF) { if (r != 'R') { putchar(r); r = getchar(); } else if ((o = getchar()) != 'O') { printf("R"); r = o; } else if ((u = getchar()) != 'U') { printf("RO"); r = u; } else if ((t = getchar()) != 'T') { printf("ROU"); r = t; } else if ((e = getchar()) != 'E') { printf("ROUT"); r = e; } else { printf("\nROUTE"); r = getchar(); } } putchar('\n'); } Not to pick on Jim C., but I don't see how his program, or any other program that is mainly explanatory comments, can be considered "cute."