Regular Expressions

Q1: Calculator Ops

Write a regular expression that parses strings written in the 61A Calculator language and returns any expressions which have two numeric operands, leaving out the parentheses around them.

We need to write a regular expression to match a pattern - (operand operator1 operator2). The operands consist of +, -, *, /. We can use [] here. Don’t forget to put a \ in front of - to escape it.

Q2: Roman Numerals

Write a regular expression that finds any string of letters that resemble a Roman numeral and aren’t part of another word. A Roman numeral is made up of the letters I, V, X, L, C, D, M and is at least one letter long.

For the purposes of this problem, don’t worry about whether or not a Roman numeral is valid. For example, “VIIIII” is not a Roman numeral, but it is fine if your regex matches it.

Context

Problem 1

Important: Your code for this part should go in buffer.py.

Your job in this part is to implement the current and pop_first methods of the Buffer class.

current should return the current token of the current line we’re on in the Buffer instance without removing it. If there are no more tokens in the current line, then current should move onto the next valid line, and return the first token of this line. If there are no more tokens left to return from the entire source (we’ve reached the end of all input lines), then current should return None (this logic is already provided for you in the except StopIteration block).

Q1: My Filter

Write a procedure my-filter, which takes a predicate func and a list lst, and returns a new list containing only elements of the list that satisfy the predicate. The output should contain the elements in the same order that they appeared in the original list.

Note: Make sure that you are not just calling the built-in filter function in Scheme - we are asking you to re-implement this!

Q1: Thane of Cadr

Define the procedures cadr and caddr, which return the second and third elements of a list, respectively. If you would like a quick refresher on scheme syntax consider looking at Lab 10 Scheme Refresher.

We need to implement the function c???r. To have a better understanding of this notation, you should look from back to the front in ???. For example, the cadr function will call cdr then call car on the input.

OOP

Q1: Vending Machine

In this question you’ll create a vending machine that only outputs a single product and provides change when needed.

Create a class called VendingMachine that represents a vending machine for some product. A Vending Machineobject returns strings describing its interactions. Remember to match exactly the strings in the doctests – including punctuation and spacing!

Fill in the VendingMachine class, adding attributes and methods as appropriate, such that its behavior matches the following doctests:

Coding Questions

Q2: Over or Under

Define a procedure over-or-under which takes in a number num1 and a number num2 and returns the following:

• -1 if num1 is less than num2
• 0 if num1 is equal to num2
• 1 if num1 is greater than num2

Challenge: Implement this in 2 different ways using if and cond!

text

(define (over-or-under num1 num2)
  'YOUR-CODE-HERE
)

The problem itself is not difficult. We just need to get used to the grammar of the scheme language. If we want to indicate the conditional branches, we may use:

Recursion and Tree Recursion

Q1: Subsequences

A subsequence of a sequence S is a subset of elements from S, in the same order they appear in S. Consider the list [1, 2, 3]. Here are a few of it’s subsequences [], [1, 3], [2], and [1, 2, 3].

Write a function that takes in a list and returns all possible subsequences of that list. The subsequences should be returned as a list of lists, where each nested list is a subsequence of the original input.

Q2: Convert Link

Write a function convert_link that takes in a linked list and returns the sequence as a Python list. You may assume that the input list is shallow; that is none of the elements is another linked list.

Try to find both an iterative and recursive solution for this problem!

It is easy to solve this problem iteratively. All we have to do is to make a list to store these nodes we have visited while we iterating this linklist.

Accounts

Q2: Retirement

Add a time_to_retire method to the Account class. This method takes in an amount and returns how many years the holder would need to wait in order for the current balance to grow to at least amount, assuming that the bank adds balance times the interest rate to the total balance at the end of every year.

The description tells us that: We will add our balance every year, so when may we retire? Both the math and code are simple.

Q1: Generate Permutations

Given a sequence of unique elements, a permutation of the sequence is a list containing the elements of the sequence in some arbitrary order. For example, [2, 1, 3], [1, 3, 2], and [3, 2, 1] are some of the permutations of the sequence [1, 2, 3].

Implement gen_perms, a generator function that takes in a sequence seq and returns a generator that yields all permutations of seq. For this question, assume that seq will not be empty.

Mutability

Write a function which takes in a list lst, an argument entry, and another argument elem. This function will check through each item in lst to see if it is equal to entry. Upon finding an item equal to entry, the function should modify the list by placing elem into lst right after the item. At the end of the function, the modified list should be returned.

See the doctests for examples on how this function is utilized.