Introduction
这次需要代写的Python作业是解Blackout Math问题，也就是算数挖空，类似于九宫格游戏，不过多了运算符号，而且是挖数字而不是填数字。
Ploblem
Blackout Math is a puzzle in which you are given an incorrect arithmetic
equation, such as this one:
288 / 24 × 6 = 18 × 13 × 8
To solve the puzzle, figure out which two squares must be blacked out to
create a correct equation. Blacked out squares are simply skipped over when
reading the new equation. Note that you can choose to black out an operation —
for example, if you black out the last multiplication sign, the right side
would read 18 x 138. You are not allowed to black out the equal sign!
In this particular instance of the puzzle, the answer is as follows:
288 / 4 × 6 = 18 × 3 × 8
as both sides of the equation now evaluate to 432.
Here is another puzzle for you to try:
168 / 24 + 8 = 11 × 3 - 16
In this project, you will develop a program that reads in Blackout Math
puzzles from a file and determines their solutions.
Building your solution
Once your solution is complete, it will work as follows:
Open up a file of Blackout Math puzzles
For each puzzle:
For each possible pair of characters in the puzzle
Determine the string that results from deleting those characters
Compute the value of each side of the equation
If the two sides have the same value, success!
—|—
However, it will be easier to build your solution from the inside out — that
is, first create a function that computes the value of one side of one
equation, then use that to build a checker for a single puzzle, and so on.
Here we will give you some hints for how to complete this process.
Computing the value of an expression
Consider the following string: 5 × 2 + 3 – going from left to right, your
program will have to check whether each character represents a digit or an
operation, and keep a running total of the current value of the expression.
Also note that when you come to a number, you have to remember what the last
character was – knowing only that the current character is a 3 only helps if
you know that you were supposed to add it to the previous value of the
expression! The Python function isdigit will be helpful for this process. To
get started, write a skeleton of a compute function that takes a string and
goes through it character by character, converting the numbers to ints and
printing “add”, “subtract”, “multiply” or “divide” for each operation as they
are encountered.
Now, consider the expression 5 + 2 × 3 – if we parse this string from left to
right (as we would usually process it in a loop), we will get 21, but
according to the standard order of operations, we should do the multiplication
first, then the addition, to get 11. In effect, when going left-to-right, we
need to delay the addition until the multiplication has been completed. One
way to do that is to save the addition on a stack, then pop it off the stack
and execute it once the multiplication has finished. You also need to save the
numbers themselves on a separate stack until they are needed. Of course, if
you have multiple additions or subtractions in a row, then you need to only
save the last one, so when you see a second addition or subtraction, you need
to compute the result of the first before saving the result and the most
recent operation.
If we have parentheses as well, this also can be easily handled with a stack,
again essentially forcing the contents of the parentheses to happen first.
The pseudocode for handling order-of-operations (for just the four standard
operations plus parentheses) using a pair of stacks is as follows:
Determine what the next item in the string is, call this X
If X is a number, push it onto the number stack
If X is any of the four arithmetic operations:
While the top of the operation stack is equal or higher precedence to X:
Pop the top two numbers from the number stack and one operation from the operation stack
Apply the operation that you just popped, push the result onto the number stack
Push X onto the operation stack
If X is (, push it onto the operation stack
If X is ),
While the top of the operation stack is not ‘(‘:
Pop the top two numbers from the number stack and the top operation from the operation stack
Apply the operation that you just popped, push the result onto the number stack
Pop off the (
Once you reach the end of the input, while the stacks are not empty:
Pop the top two numbers from the number stack and the top operation from the operation stack
Apply the operation that you just popped, push the result onto the number stack
—|—
The final value of the expression will be on the number stack
To get a feel for how and why this works, trace this pseudocode for the input
2 + 5 × (6 - 3) - 6 by noting what is in each stack after reading each
character.
Finally, consider the string 5 × 12 + 3 – in this case, when you come to a
number, you cannot count on it being immediately used. Instead, you have to
continue building up the value of the current number until you read an
operation, then you can incorporate that into the expression. Figure out what
happens when the 1 is read by your function, then the 2, and finally the +.
Modify your compute function to handle the case of multi-digit numbers. As
above, trace the correct execution on paper and then test the code on a few
different cases.
Error handling
In many cases in this course, we do not worry about handling errors in input
as they are not critical to the problem at hand. However, in this case, we can
expect “errors” to occur when parsing. This is because we will be deleting
arbitrary characters from the puzzle. For example, when trying to solve our
first example 288 / 24 × 6=18 × 13 × 8 we might try deleting the 6, leaving a
left side of 288 / 24×. We know right away that this is not a possible
solution to the puzzle, but our compute function must still handle this
gracefully. Luckily, the stack-based algorithm will handle most of these cases
easily – if we get to the end of the input and have anything other than one
number and no operators left, there was erroneous input. Other error cases
that you may discover can also be dealt with via the parsing algorithm itself.
Testing whether an equation is correct
Once we can evaluate a single expression, it is simple to compute whether two
sides of an equation are equal. You may find the Python functions find (with
slicing) or split useful to locate the equal sign in your equation (if it
still has one!). Write a function called test that takes in a string and uses
your compute function to decide if the string represents the correct solution
to a Blackout Math puzzle.
Computing all possible pairs of characters
To solve a Blackout Math puzzle, you have to find the two squares to black
out, or in our case, two characters to remove from the string. For a computer,
the simplest thing to do is simply to test all possible pairs of characters.
Note that although the two examples in this writeup are the same length, not
all Blackout Math puzzles will be.
Write a function solve that takes in a full Blackout Math puzzle as a string
and loops through all possible pairs of characters. For each pair of
characters, create the string that results when those two characters are
removed, and use your evaluate function to see which of those represents the
solution! This is a good time to make sure that your error handling works, as
this loop will send many malformed equations to your evaluate function –
consider how compute will report errors, and how evaluate will handle them.
Remember, that the two characters that are removed COULD be on the same side
of the equals sign.
Using a binary tree to compute all possible solutions
Now that you have done this for all possible combinations of two blacked out
characters, you need to now do it for any arbitrary number of blacked out
characters.
To do this you are required to use a binary tree. The tree will be structured
such that all leaf nodes of the tree are all possible combinations of blacked
out characters.
The left child of the tree will be the equation with the current character
blacked out. The right child will be the equation with the current character
not blacked out.
To construct the tree you will consider one character at a time in the
equation. You will make two children, one with the current value blacked out
and one with the value not blacked out. Each level of the tree will represent
all possible combinations of a new character character being added to the
statement.
Your function for making the tree will be recursive in nature, as recursion is
the easiest way to process a binary tree.
Psuedocode for making the tree:
def makeTree( equation, value ):
if the equation is empty, we have reached the leaves of this branch:
set left and right children to None
otherwise:
we need to create the left and right children:
- left will be a recursive call to make tree with:
- the first character removed from the equation
- the same value
- right will be a recursive call to make tree with:
- the equation with the first character removed
- the first character of the equation appended to the value
make a binary tree node with the left, right, and current value
return the binary tree node
—|—
In the case of the tree presented above, there are no valid solutions. These
trees can get large. There are actually 2 n possible leaf nodes, where n is
the length of the equation. For example, the equation 3 + 2 / 5 = 5 + 3 × 2
will have 2 11 possible leaf nodes. That’s 2048 leaf nodes!
To process the equations for a given number of blacked out squares, supplied
by the user, you will be required to traverse the tree looking for leaf nodes.
These are the steps to find valid blacked out equations:
- Traverse the tree to find all leaf nodes
- When you find a leaf node, check to see if it has the proper number of blacked out characters:
(a) If it does, determine if it is a valid equation:
i. If it is, evaluate the equation and print the result
ii. If it is not, ignore the equation
(b) If it does not, ignore the node
You will use your work from prior sections to evaluate the equations when you
reach them.
Testing
As you develop your solution, make sure to thoroughly test each function as
well as the overall solution. For the compute function, it probably makes
sense to test simple expressions first, then more complex ones (including
parentheses), and finally ones that will cause errors of various kinds.
For the overall solution, you should test some different puzzles including
some of your own creation (making a puzzle isn’t that hard!). Make sure that
your code works for all the puzzles – but we will not test with any puzzle
that does not have a solution. Note that some puzzles, such as the one given
at the top of this assignment, do not rely on order of operations, so can be
used for testing whether or not you have implemented that algorithm.
Implementation details
You must follow the following naming conventions. This will make the testing
and grading of your project more efficient. Points will be deducted if this
naming convention is not followed.
You may make any helper functions that you wish, but these must be present.
Each file must also contain:
if name == “main“:
main()
—|—
This will run the main when the given file is run and not when others are run.
Blackout
Your code should read in a series of Blackout Math puzzles from a file. Your
main file should be named blackout.py and should take in the following input:
- the name of the file with the puzzles in it.
It should then read in the lines of this file (one puzzle per line) and print
the puzzle and its solution for each one.
Overall structure of your solution:
- blackout.py: This file should contain the following methods:
(a) compute(s): This function computes the value of the string ‘s’, which
represents either the left or right side of an equation. It takes a string as
a parameter and returns a numeric value, or None if the equation is not
valid.”
(b) evaluate(s): This function will test a string representing an entire
equation to determine if it is valid. If the equation is syntactically valid,
and the left and right sides are equal, then this function will return True.
Otherwise, it returns False.”
(c) solve(s): This function will solve a given puzzle, represented by the
string s. It will black out two squares at a time, passing each possible
combination to the evaluate function. It should return the first valid
solution it finds, or None if not valid solution exists.
(d) main(): This function is the main function for the first part of blackout.
It should prompt for and read the file one line at a time and submit each
line, or puzzle, to be solved one at a time. It should print out the puzzle
and the solution when it is found.
(e) compute tests(): This function will test your compute function. Ensure you
have enough tests to cover the various possible cases you can encounter.
Printing the test results in a verbose manner is sufficient.
(f) evaluate tests(): This function will test your test function. Ensure you
have enough tests to cover the various possible cases you can encounter.
Printing the test results in a verbose manner is sufficient.
(g) solve tests(): This function will test your solve function. Ensure you
have enough tests to cover the various possible cases you can encounter.
Printing test results in a verbose manner is sufficient.
Blackout Tree
Your code should read in a series of Blackout Math puzzles from a file. Your
main file for this section should be named blackout tree.py and should take in
the following input:
- The name of the file with the puzzles in it.
- The number of squares to black out.
It should then read in the lines of this file (one puzzle per line) and print
the puzzle and its solution(s) for each one.
- blackout tree.py: This file should contain the following methods:
(a) make tree(s): This function makes the binary tree from the string s, s is
a puzzle string. It must use the BinaryTree and BnaryTreeNode classes from
lecture. It takes in a string representing a puzzle, and returns a binary tree
who’s leaf nodes are all of the possible blacked out combinations.
(b) solve tree(bt, number): This function will solve the given binary tree
puzzle, bt, with the given number of blacked out square, number. It will find
all leaf nodes and call evaluate(s) from blackout.py on any leaf node value
that has the requested blacked out squares. It will print any solutions it
finds, similar to solve(s) in blackout.py. If there are no valid solutions you
should output a message stating that fact.
(c) main(): This function is the main function for the blackout tree section
of the project. It should prompt the user for the file containing the puzzles
and the number of blacked out squares to look for. It should print the puzzle
and call make tree to create the tree. Then solve tree to print the valid
solutions for the tree.
(d) test make tree(): This function should test your make tree function.
Ensure you test various different kind of trees.You will have to create
expected Binary Trees using the BinaryTree and BinaryTreeNode classes to
compare to.
