Week 10 Laboratory
A comment about exercise 5 below:
it requires you to demonstrate to your tutors that you have completed Stage 1 of the assignment. You do not have submit any code.
The following program postfixQ.c evaluates a postfix expression given on the command line. The program uses the quack ADT.
// postfixQ.c: a client of the quack ADT // a calculator for command-line postfix expressions // assume arguments are well-formed (no error handling done) // assume operands are >=0 // supports only + and * #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include "quack.h" #define PLUSCHAR "+" #define MULTCHAR "*" int main(int argc, char *argv[]) { if (argc >= 2) { Quack sq = NULL; sq = createQuack(); int arg; for (arg=1; arg<argc; arg++) { int a, b; if (strcmp(argv[arg], PLUSCHAR) == 0) { a = pop(sq); b = pop(sq); push(a+b, sq); } else if (strcmp(argv[arg], MULTCHAR) == 0) { a = pop(sq); b = pop(sq); push(a*b, sq); } else if (isdigit(*argv[arg])) { if (sscanf(argv[arg], "%d", &a) == 1) { push(a, sq); } } } if (!isEmptyQuack(sq)) { // quack must contain the result printf("%d\n", pop(sq)); makeEmptyQuack(sq); // it is an error if there is more } } return EXIT_SUCCESS; }The program above assumes that the expression is well-formed, and that operands are not negative. The following testcases show the program executing.
prompt$ ./postfixQ 1 2 3 \* + 7
prompt$ ./postfixQ 24 19 4 \* + 8 6 \* 2 + + 150
prompt$ ./postfixQ 1 2 3 4 5 6 7 8 9 \* + \* + \* + \* + 3839
Your tasks:
Note the following:
this function cannot be part of the ADT of course
to avoid that, precede the '*' with a backslash (e.g. \*) wherever it is used above
most UNIX shells treat an asterisk as a special character
you should match the error messages precisely
you may find it useful to write a function that indicates whether there is exactly 1 element on the quack or not
you will be submitting postfixerQ.c only so do not alter the quack ADT in any way
Download the Quack ADT, compile the above program and ADT, and try the above testcases.
Try a testcase with a negative operand. What does the program do with the negative operand?
Now extend this program, calling the new program postfixerQ.c (which stands for postfix with error handling), to:
handle negative numbers. Here is a testcase:
prompt$ ./postfixerQ 24 -5 \* 20 + -1 \* -15 -6 \* + -90 + -1 \* -100
handle the ill-formed postfix expressions such as those below:
prompt$ ./postfixerQ 1 2 Error: missing operator(s) prompt$ ./postfixerQ 1 2 3 + Error: missing operator(s) prompt$ ./postfixerQ + Error: missing operand(s) prompt$ ./postfixerQ 1 + Error: missing operand(s) prompt$ ./postfixerQ a 2 + Error: invalid argument a prompt$ ./postfixerQ - 2 + Error: invalid argument - prompt$ ./postfixerQ 1 2 - Error: invalid argument -
Bracket matching is an important problem, e.g. for parsing computer programs. A bracket-matching program checks whether all opening brackets such as '(', '[' and '{' have corresponding closing brackets ')', ']' and '}'. A stack is an excellent data structure to implement a bracket-matching program. Write a program called bracketsQ.c that uses the quack ADT to check whether all the brackets on the stdin text stream are balanced or not.
Each of the following 4 testcases:
(a+b)*c (a[i]+b[j])*c[k] void f(char a[], int n) {int i; for(i=0;i<n;i++) a[i] = (a[i]*a[i]*a[i])*(i+1); return;} ((())){{[]}{()()()}}should result in the output:
balanced
Each of the following 5 testcases:
a(a+b*c a(a+b]*c a[i]+b[j]*c[k]) ((]()) ((())){{[]}{(()()}}should result in the output:
unbalanced
Write a program called llmax.c that:
If the largest number occurs more than once in the list, print all nodes starting from the first occurrence of the largest number.
A testcase showing execution of the program is:
prompt$ echo "4 1 4 2 3" | ./llmax Original list = 1->4->2->3 Truncated list = 4->2->3
Notice here that the first number, 4, indicates the size of the list only. More examples are:
prompt$ echo "6 5 10 14 1921 14 2" | ./llmax Original list = 5->10->14->1921->14->2 Truncated list = 1921->14->2
prompt$ echo "17 2 2 4 4 4 6 4 8 6 10 6 2 4 10 2 10 10" | ./llmax Original list = 2->2->4->4->4->6->4->8->6->10->6->2->4->10->2->10->10 Truncated list = 10->6->2->4->10->2->10->10
prompt$ echo "2 1 2" | ./llmax Original list = 1->2 Truncated list = 1->2
prompt$ echo "1 13" | ./llmax Original list = 13 Truncated list = 13
prompt$ echo "20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1" | ./llmax Original list = 1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1 Truncated list = 1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1
If there are not enough numbers, then the result is:
prompt$ echo "3 1 2" | ./llmax Data missing
If the first data is not numerical, then the result is:
prompt$ echo "xx 1" | ./llmax No data
Finally, if there is no data then:
prompt$ echo "" | ./llmax No data
The only data structure that you may use in your program is a single singly-linked list.
Note the following:
in a UNIX pipeline
the output (on stdout) of the first program, prog1, feeds directly as input (on stdin) to the second program, prog2prompt$ prog1 | prog2
reads numbers from stdin
inserts these numbers into a linked list
prints the linked list
prints all nodes in the list starting from the largest number in the list
(This exercise can be challenging.)
Write a program called llunique.c that:
A number is repeated if it appears anywhere else in the list: all instances of repeated numbers should be removed, including(!) the first occurrence of each such number. For example:
prompt$ echo "10 1 2 3 1 2 3 4 5 6 7" | ./llunique Original list = 1->2->3->1->2->3->4->5->6->7 Unique list = 4->5->6->7
Notice that the numbers 1, 2 and 3 occur more than once in the original list and hence are not in the resulting list. Notice also that, as usual, the first number on stdin indicates the size of the list only.
More testcases are:
prompt$ echo "6 5 10 14 1921 14 2" | ./llunique Original list = 5->10->14->1921->14->2 Unique list = 5->10->1921->2
prompt$ echo "1 13" | ./llunique Original list = 13 Unique list = 13
prompt$ echo "20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1" | ./llunique Original list = 1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1 Unique list is empty
As before, if there are not enough numbers, then the result is:
prompt$ echo "3 1 2" | ./llunique Data missing
If the first data is not numerical, then the result is:
prompt$ echo "xx 1" | ./llunique No data
Finally, if there is no data then:
prompt$ echo "" | ./llunique No data
As before, the only data structure that you may use in your program is a single singly-linked list.
reads numbers from stdin
inserts these numbers into a linked list
prints the linked list
removes all numbers that occur more than once in the list
prints the resulting linked list
You should demonstrate to your tutor that you have completed Stage 1 of the assignment. Recall that this involves implementing the following commands:
A - Add image from file L - List of images P - Print current image
Download a few test images to the working directory and demonstrate to your tutor that the above commands work as expected. You are not required to submit any code for this exercise. However, you MUST demonstrate this during the lab to obtain the 2 marks for this exercise.
We have created some scripts that can automatically run your program against some tests. To run these tests you can execute the dry run program with an argument that corresponds to the lab and week, i.e. lab10 for this week. It expects to find all the programs to be submitted as part of this lab in the current directory. You can use dry run as follows:
prompt$ ~cs1921/bin/dryrun lab10 |
or specific tests (e.g. test #2) as follows:
prompt$ ~cs1921/bin/dryrun lab10 2 |