Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSCI 3136: Assignment 7

Summer 2022

Write Scheme programs to accomplish each of the following. You may not use loops or any built-in procedure name that ends with ‘!’.  Do not use the display procedure. Submit your results, on Brightspace, as a single file named “a7.scm”. Your submissions should obey good programming style (e.g., comments, indentation, use of whitespace).

1. [20 marks] Postfix expressions are incredibly easy to evaluate using a stack. To solve an expression, there are three things to know as you read a post-fix expression from left to right:

1. If you see a number, push it on the stack.

2. If you see an operator, pop the stack (twice) and apply the operator to what you just popped and then push the result.

3. When you reach the end of the expression there should be one thing on the stack – the solution.

(postfix ‘(1 2 + 3 *)) → 9

(postfix ‘(3 4 5 + +)) → 12

You will need to use the eval function to apply the operator. Ensure you test your code on a wide variety of expressions.

2. A family tree can be represented by a list. For example:

(define myfamily ‘(“Cat” “Dog” (“Mug” “Hug” (“Boo”)) (“Shoe”)))

Each level of the list represents a different generation. The first two elements of a list are the parents and any sub-lists that follow are children and future generations. The example above represents the tree:

a. [10 marks] Write a predicate to test immediate parental relationships:

(parent myfamily “Boo” “Shoe”) → #f

(parent myfamily “Mug” “Cat”) → #t

b. [10 marks] Write a function to determine how many offspring someone has:

(offspring myfamily “Dog”) → (“Mug” “Hug” “Shoe” “Boo”)

c. [10 marks] write a function to flatten a family tree and return a sorted list of family members. You will be given half marks if you flatten the list, but don’t sort it.

(flatten myfamily) → (“Boo” “Cat” “Dog” “Hug” “Mug” “Shoe”)

Expect us to test your code thoroughly on more than these trivial examples. Do not expect to get full marks simply for getting your code to work – clarity, style, and understanding of functional programming will also be considered.