Week 6: Exercises

1. Xyz

What will this program print?

class Foo {
    public virtual int xyz() => 5;
}

class Bar : Foo {
    public override int xyz() => 10;
}

class Top {
    static void Main() {
        Bar b = new Bar();
        Foo f = b;
        Console.WriteLine(b.xyz());
        Console.WriteLine(f.xyz());
    }
}

2. Dictionary

Write a class SIDict that represents a dictionary from strings to integers. It should have the following members:

• SIDict() - create an empty SIDict

• an indexer that allows the user to get or set values by index

For example, your class could be used as follows:

SIDict d = new SIDict()
d["red"] = 4
d["blue"] = 5
d["red"] += 1
WriteLine(d["red"])

Use a linked list of key-value pairs.

3. Abstract Syntax Tree

Consider a simple programming language that we will call W. It has the following features:

• integer constants

• variables

• the integer operators +, -, *, /, %

• the boolean operators ==, !=, >, >=, <, <=

• assignment statements

• while statements

• a function print()

Here is a program in W that computes the sum of integers from 1 to 100:

x = 100
s = 0

while (x > 0) {
    s = s + x
    x = x - 1
}

print(s)

Here is a program that uses Euclid's algorithm to compute the GCD of two integers:

x = 1056
y = 668

while (y > 0) {
    t = x % y
    x = y
    y = t
}

print(t)

Variables can hold only integers, so boolean operators can be used only inside a 'while' condition. For example, 'x = y < z' is illegal. Arithmetic expressions may contain parentheses and may be nested. For example, 'x = (a + b) * (c + d)' is legal.

Design and write a set of C# classes that can hold an abstract syntax tree for a W program. There should be a class Program that represents an entire program.

4. Family Tree

Consider this class for representing a person:

class Person {
    public string name;

    public Person[] children;
}

Write a static method show(Person[] a) that takes an array of Person objects. Every Person in the array will have a unique name. For every person p in the array, it is guaranteed that p's children (if any) also appear somewhere in the array. The objects in the array might be in any order.

The method should print out the names of all people, one per line, in some order such that each person's name appears before the names of their children.