Week 10 Laboratory — Quacks, Recursion, Binary Search Trees

Note:

You can use dry run as usual:

prompt$ ~cs1921/bin/dryrun lab10


prompt$ ~cs1921/bin/dryrun lab10 2

Exercises

  1. (Quacks) 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.

    Your tasks:

    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

  2. (Recursion) In Lab 3, you wrote a program called countplus.c that prints a sequence of numbers. Modify the program to use recursion instead of iteration. Call the modified program recountplus.c. The usage is the same as before.

  3. (Recursion) Now modify recountplus.c to count backwards as well as forwards. Call the modified program recount.c. The direction of counting is determined by the sign of the command-line argument. You should use only one recursive function in the program. An example of counting backwards is:

     prompt$ ./recount -12
 0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11,-12

    You might find this exercise challenging.

  4. (Binary Search Trees) Write a program called sumTree.c that:
    Note: Copy data structures and functions from the BST program in the lecture (Week 9), tree.h and tree.c, as starting point, and write

    Examples of program execution are:

    prompt$ ./sumTree 2 1 3
	1
2
	3
Sum of nodes = 6


    prompt$ ./sumTree 8 4 6 2 7 5 3 1 12 10 9 14 13 11 15
			1
		2
			3
	4
			5
		6
			7
8
			9
		10
			11
	12
			13
		14
			15
Sum of nodes = 120


    prompt$ ./sumTree 6 5 4 3 2 1
					1
				2
			3
		4
	5
6
Sum of nodes = 21


    prompt$ ./sumTree 1 2 3 4 5 6
1
	2
		3
			4
				5
					6
Sum of nodes = 21


    prompt$ ./sumTree 5 6 7 1 2 3 4
	1
		2
			3
				4
5
	6
		7
Sum of nodes = 28


    prompt$ ./sumTree 7
7
Sum of nodes = 7

    If there are no arguments on the command line, then the program generates a usage error message: 

    prompt$ ./sumTree
Usage: ./sumTree integers ...

    If there is a non-numeric argument on the command line, the same usage error message is printed: 

    prompt$ ./sumTree 3 10 a
Usage: ./sumTree integers ...

    Note:

  5. (Assignment) You should demonstrate to your tutor that you have completed Stage 1 of the assignment. Recall that this involves

    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.

Submit the rest of your work using:


  give  cs1921  lab10  bracketsQ.c  recountplus.c  recount.c  sumTree.c