#
CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science

Homework 9 (Due Saturday, 28-Oct, at 8pm)

- This hw is SOLO. See the syllabus for details.
- Starter code: hw9.py
- You should make use of this week's linter: cs112_f17_week9_linter.py
- When you are ready, submit hw9.py to autolab. This week you may use up to 5 submissions. Only your last submission counts. Only your last submission will be graded.
**Do not use for or while this week.**

**Take the midsemester course survey**[10 pts] [manually graded]

**The survey is now available: you can find it here!**

We want your feedback on how the course is going, so we can keep trying to make it better. Therefore, we'd like you to answer some questions!

Note: this survey will be**anonymous**. When you complete the survey, you'll get a link to a different form where you can enter your andrewID to receive the homework credit. We will not be able to map your survey response to your andrewID.**recursive powerSum(n, k)**[10 pts] [autograded]

Write the function powerSum(n, k) that takes two possibly-negative integers n and k and returns the so-called power sum:

1**k + 2**k + ... + n**k

If n is negative, return 0. Similarly, if k is negative, return 0.**recursive isHappyNumber(n)**[15 pts] [autograded]

Write the function isHappyNumber from Hw2, but recursively. Note that you'll probably need to reimplement sumOfSquaresOfDigits as well...**recursive evalPrefixNotation(L)**[15 pts] [autograded]

Background: in so-called 'prefix notation', an arithmetic expression is listed with the operator first. So instead of writing '2 + 3' we would write '+ 2 3'. Actually, for this problem, we'll represent the expression in a list, so we'd write ['+', 2, 3]. Each value can itself be another full expression, so for example we could have:['+', 2, '*', 3, 4]

This would be the same as (2 + (3 * 4)), or 14. Again, we could have:['+', '*', 2, 3, '*', 4, 5]

This would be the same as ((2 * 3) + (4 * 5)), or 26. Look at the test function in the code for a few more examples.

With this in mind, write the function evalPrefixNotation(L) that takes a list L that contains a legal arithmetic expression in prefix notation, as just described, and returns the value that the expression evaluates to.

Your function only needs to work for '+', '-', and '*'.

Hint: this problem becomes drastically easier if you implement it**destructively**. Our sample solution used L.pop(0) to get the first element, for example. Evaluating the operands then becomes much simpler...**VendingMachine class**[50 pts] [autograded]

Write the VendingMachine class so that it passes testVendingMachineClass, and uses the OOP constructs we learned this week as appropriate.

**Hint**: Make sure you're representing money properly wherever it might appear in the string representation of a Vending Machine. The test cases shown here don't cover every possible case...

def testVendingMachineClass(): print("Testing Vending Machine class...", end="") # Vending machines have three main properties: # how many bottles they contain, the price of a bottle, and # how much money has been paid. A new vending machine starts with no # money paid. vm1 = VendingMachine(100, 125) assert(str(vm1) == "Vending Machine:<100 bottles; $1.25 each; $0 paid>") assert(vm1.isEmpty() == False) assert(vm1.getBottleCount() == 100) assert(vm1.stillOwe() == 125) # When the user inserts money, the machine returns a message about their # status and any change they need as a tuple. assert(vm1.insertMoney(20) == ("Still owe $1.05", 0)) assert(vm1.stillOwe() == 105) assert(vm1.getBottleCount() == 100) assert(vm1.insertMoney(5) == ("Still owe $1", 0)) # When the user has paid enough money, they get a bottle and # the money owed resets. assert(vm1.insertMoney(100) == ("Got a bottle!", 0)) assert(vm1.getBottleCount() == 99) assert(vm1.stillOwe() == 125) assert(str(vm1) == "Vending Machine:<99 bottles; $1.25 each; $0 paid>") # If the user pays too much money, they get their change back with the # bottle. assert(vm1.insertMoney(500) == ("Got a bottle!", 375)) assert(vm1.getBottleCount() == 98) assert(vm1.stillOwe() == 125) # Machines can become empty vm2 = VendingMachine(1, 120) assert(str(vm2) == "Vending Machine:<1 bottle; $1.20 each; $0 paid>") assert(vm2.isEmpty() == False) assert(vm2.insertMoney(120) == ("Got a bottle!", 0)) assert(vm2.getBottleCount() == 0) assert(vm2.isEmpty() == True) # Once a machine is empty, it should not accept money until it is restocked. assert(str(vm2) == "Vending Machine:<0 bottles; $1.20 each; $0 paid>") assert(vm2.insertMoney(25) == ("Machine is empty", 25)) assert(vm2.insertMoney(120) == ("Machine is empty", 120)) assert(vm2.stillOwe() == 120) vm2.stockMachine(20) # Does not return anything assert(vm2.getBottleCount() == 20) assert(vm2.isEmpty() == False) assert(str(vm2) == "Vending Machine:<20 bottles; $1.20 each; $0 paid>") assert(vm2.insertMoney(25) == ("Still owe $0.95", 0)) assert(vm2.stillOwe() == 95) vm2.stockMachine(20) assert(vm2.getBottleCount() == 40) # We should be able to test machines for basic functionality vm3 = VendingMachine(50, 100) vm4 = VendingMachine(50, 100) vm5 = VendingMachine(20, 100) vm6 = VendingMachine(50, 200) vm7 = "Vending Machine" assert(vm3 == vm4) assert(vm3 != vm5) assert(vm3 != vm6) assert(vm3 != vm7) # should not crash! s = set() assert(vm3 not in s) s.add(vm4) assert(vm3 in s) s.remove(vm4) assert(vm3 not in s) assert(vm4.insertMoney(50) == ("Still owe $0.50", 0)) assert(vm3 != vm4) print("Done!")