Programming 2, Summer 2022
Week 6: Notes

This week we learned about inheritance, including conversions between base and derived types, virtual methods, and abstract methods and classes. We also looked at the top-level 'object' class. You can read about these topics in chapter 7 of Essential C#.

tutorial programs

We solved these exercises in the 12:20 tutorial:

2. Write a class SIDict that represents a dictionary from strings to integers. Use a linked list of key-value pairs.

class Node {
    public string key;
    public int val;
    public Node? next;

    public Node(string key, int val, Node? next) {
        this.key = key; this.val = val; this.next = next;
    }
}

class SIDict {
    Node? head;

    public int this[string s] {
        get {
            for (Node? n = head; n != null; n = n.next)
                if (n.key == s)
                    return n.val;

            throw new Exception("key not found");
        }

        set {
            for (Node? n = head; n != null; n = n.next)
                if (n.key == s) {
                    n.val = value;
                    return;
                }
            head = new Node(s, value, head);
        }
    }
}

3. Consider a simple programming language that we will call W. Design and write a set of C# classes that can hold an abstract syntax tree for a W program.

abstract class Expr {
}

class IntExpr : Expr {
    int i;
}

class VarExpr : Expr {
    string var;
}

class OpExpr : Expr {
    string op;      // e.g. +, -, <=
    Expr left, right;
}

abstract class Stmt {
}

class Assignment : Stmt {
    string var;
    Expr expr;
}

class While : Stmt {
    Expr cond;
    Stmt[] body;
}

class Print : Stmt {
    Expr expr;
}

class Program {
    Stmt[] stmts;
}

4. 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. For every person p in the array, it is guaranteed that p's children (if any) also appear somewhere in the array. The method should print out the names of all people in some order such that each person's name appears before the names of their children.

class Person {
    public string name;
    public bool visited = false;

    public Person[] children;

    static void show(Person[] a) {
        Person[] sorted = new Person[a.Length];
        int i = 0;

        void visit(Person p) {
            if (!p.visited) {
                p.visited = true;
                foreach (Person q in p.children)
                    visit(q);
                sorted[i++] = p;
            }
        }

        foreach (Person p in a)
            visit(p);

        for (i = sorted.Length - 1; i >= 0 ; --i)
            Console.WriteLine(sorted[i].name);
    }
}