CS 113

HOMEWORK 3

Due: Friday, September 15, 2000  (there is a good chance that this will be extended to Monday 18)

WARNING: The input for all the programs should be just asking for numbers or phrases, without the program printing anything (except the output of course); so do not print something like "Give me a line>", before you ask for a line to be inputted etc.

Crypto

Now that you've had the opportunity to get yourselves accustomed to the encryption and decryption process in the last problem of the 2nd homework, you are asked to implement a non-mono-alphabetic substitution system (only the encryption part).

The characters that should be encrypted are lower (a-z) and capital (A-Z) letters and also numbers (0-9) and no other characters...

The first phase is to read the correspondences between a character or group of characters of the plain text (plain text is how the unencrypted-original text is called) and a character or group of characters of the crypto text (the encrypted text). The correspondences should be given as input with each pair given in a separate line as follows:

hi asw             or

>>.G5f,,..5Fg6,./

which mean that whenever "hi" appears in the plain text it should be replaced by "asw" in the crypto text and whenever "G5f" appears in the plain text it should be replaced by "5Fg6" in the crypto text. As you notice the valid characters (0-9, A-Z, a-z) can be surrounded by invalid characters (anything else) and that is how the program knows which are the two groups of characters.

At the beginning an unknown number of such pairs is inputted by the keyboard; the program knows that it has received all the pairs when the line "...ENDPAIRS..." is read.

Since the number of pairs is unknown it is a good idea that the pairs are stored in a dynamic structure, so that no memory is wasted... I would suggest that you use a linked list, with each node of the list having as data the two strings (groups of characters). You may assume that the maximum number of characters that each group is going to have is 10.

Also note that if a given line has only one pair of character then that implies that the second pair has no characters:

..)))9f,.,.,**

means that whenever "9f" is met it is going to be replaced by " " (a single space character).

After the pairs are stored, then lines of plain text are going to be inputted one at a time. For each line inputted the program should encrypt it using the following algorithm:

1. If the first character of the rest of the plain text (by rest I mean the characters that were not matched/substituted yet) is not a valid character (0-9, A-Z, a-z) then delete it.
2. Go through all the pairs (in the order that they were given) and try to match the beginning of the rest of the plain text with the first group of characters. If this happens then replace this text with the second group of character in the pair.
3. If no match was found then leave the character as it was.

The last line should be "...ENDLINES..." and when this line is read the program terminates (note that this last line is not coded!)

A small example execution of my program:

..afg ;12             \
fg 0                   | input
;;[a/.                 |
...ENDPAIRS...        /
"afg"->"12"           \
"fg"->"0"              | output of pairs (do not print this in final program)
"a"->" "              /
Afgafgab..,           <input
A012 b                <output
...ENDLINES...        <input

Things that I want you to notice in the above execution:

1. All non alphanumeric characters in the input are not taken into account
2. The last line does not match 'a' to anything else so it is matched to ' ' (a single space character)
3. "Afg" does not match to "afg" and since the beginning of string does not match to anything we just print 'A' again
4. "afg" matches both to "afg" and "a", but since "afg" was given first that means that we will match it to "afg"

This is the program that I have written for this assignment. You may choose to use this code and add you own code in the places that I have removed the code (namely the 4 functions that do all the work), or you can opt to write your own programs completely from scratch... All that I care is that the program works, not that you have done it in the same way as I did!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* linked list node structure */
typedef struct linked_list {
  char group1[12], group2[12];
  int len;
  struct linked_list *next;
} llnode;

llnode *Head, *Tail; /* head and tail of linked list */

/* returns False if c is not alphanumeric and True otherwise */
int isalphanum(char _c)
{
  /* put your code here */
}

/* gets a line with a pair of groups and insert a new node into the list
or return 0 if the end is found */
int insertNode(char *_str)
{
  /* put your code here */
}

/* DEBUG Function: print all pairs */
void printPairs()
{
  llnode *ptr=Head;
  for (; ptr; ptr = ptr->next)
    printf("\"%s\"->\"%s\"\n", ptr->group1, ptr->group2);
}

/* find a matching group of characters to the beginning of the string */
llnode *findPair(char *_str)
{
  /* put your code here */
}

/* codes and prints one line based on the pairs
or return 0 if the end is found */
int codeNprintLine(char *_line)
{
  /* put your code here */
}

void main()
{
  char line[80];

  Head=Tail=NULL;
  while (1)
  {
    fgets(line, 80, stdin);
    if (!insertNode(line))
      break;
  }
  printPairs();  /* this is just for debugging purposes only */
  while (1)
  {
    fgets(line, 80, stdin);
    if (!codeNprintLine(line))
      break;
  }
}