Description
This first assignment will focus on coding in Python, applying knowledge students should already have about programming with functions and arrays or Python lists. When the assignment is complete, there will in fact be some indirect recursion, but that needs not complicate the assignment, if each function is allowed to assume that all other functions are implemented correctly.
Problem Description
Several years of experience in algebra probably yields a consistent interpretation of the expression
12 – 2 * 5 + 3
Most would expect that the multiplication would be the first operation, followed by a subtraction, and then an addition, yielding a value of 5. Performing those three operations in any other order would yield very different results.
When a programmer places such an expression into a program, they would expect it to perform the same series of operations. The interpreter or compiler making sense of the expression then must be able to construct the correct meaning of the input. Often one will hear of this behavior called parsing. This assignment will evaluate such an expression.
A closer look at the Parsing Algorithm
Suppose you were told to evaluate this input without a pencil and paper:
3 – 2 + 1 + 5 * 2 – 3 * 4 + 0 / 5 + 1 * 2 * 3
Would you make an effort to memorize the entire input sequence before starting? Would you you scan through the input once to find all the * and / operators, and attempt to remember all of the products along with the + and – operations?
The instructor thinks not. And the simplest computer algorithms are the ones that closely model how real people solve problems. The instructor thinks the following analysis would be most intuitive:
subtract 3 – 2, then add 1, then add 5*2, then add 3*4,
then add 0/5, then add 1*2*3
This algorithm can be represented as a single loop that adds and subtracts, as long as it assumes that it can find the appropriate values to work with — which would be a separate sub-problem to solve.
The pseudocode for parsing a sum expression would therefore look something like this:
to evaluate a sum expression (series of zero or more additions and subtractions):
evaluate a product expression (zero or more multiplications and divisions)
while the next token is a + or – operator
evaluate the product expression that follows the operator
perform the addition or subtraction
There would be a separate function to evaluate a product expression that would have a very similar structure, finding values to multiply (or divide)
Assignment Specifications
The input for this assignment will arrive as an instantiated Python list consisting of tokens, where each token is either an integer numeral or an operator. An additional symbol (such as a semicolon) will appear at the end of the list to mark the end of the input.
The Python list has a great deal in common with the idea of an array, and this assignment will treat it as such. One will be able to use an integer subscript to examine each element of the list, just as one could examine consecutive array elements. The next assignment will use a different approach to visit the elements of the list.
Python Implementation Details
Since arrays are the data structure most students taking this course would be familiar with, this assignment will treat the data as an array with a subscript variable moving forward through the data. It can be seen that this subscript must increase while the data is being examined, and each function must be able to update it.
Unfortunately, Python does not allow integer parameters to be modified, in the way as many other languages (like C++) . Any attempt to increment the integer would simply make a local variable refer to a differ, without changing the original copy.
But, as will have been shown in lecture, one can get around this by taking advantage of Python’s multiple-assignment operations and similarly have a function return the new subscript along with the value that it computes for the expression.
Here is a quotation from the instructor’s solution, as it appeared at the time that this assignment file was created:
(in a file titled infix1.py)
def eval_infix_sum(expr, pos):
“””evaluate a sum expression (zero or more additions and subtractions)
expr Python string list complete expression to be evaluated
pos integer subscript to current token
“””
…. implementation of algorithm above
return ans, pos # return result and updated subscript
def eval_infix_product(expr, pos):
“””evaluate a product expression (zero or more multiplications/divisions)
“””
# NOTE: This must be extended to support parenthesized sub-expressions)
def eval_infix_factor( expr, pos ):
“””evaluate a factor (number or parenthesized sub-expression)
return int(expr[pos]), pos+1 # convert string to int, and move past
# the following functions are defined to supply a ‘friendlier’ interface to the clients,
# which will later also be used to provide some degree of implementation hiding.
def eval_infix_list(expr):
“””evaluate an expression represented as a list of strings
ans, discard = eval_infix_sum( expr, 0 ) # start subscript at 0, then forget it
return ans
def eval_infix(expr):
“””evaluate an expression represented as a single space-separated string
return eval_infix_list(expr.split() + [ “;”]) # make a list, and append semicolon
Recommended Solution
This is one approach to solving this homework but there are other approaches also:
Define eval_infix_product to do nothing more than call the eval_infix_factor above, and implement the suggested algorithm for eval_infix_sum.
Test for an expression whose only operators are + and -.
Implement eval_infix_product using a similar algorithm to the one provided.
Test for expressions using any combination of +, -, *, /.
Modify eval_infix_factor to support parentheses. When this function is called, expr[pos] will always be either a ( character or a number, so it should be easy to choose which is the case. The ( would then be followed by a complete expression which is then followed by a ) character.
Note: There is already a function defined to evaluate the expression within the parentheses.
Additional Homework Specifications
Correctness is Expected
The actual test cases that will be used to evaluate your submission will not be provided in advance. All students are expected to have their implement solutions that are complete and correct, given correct and reasonable input.
One may assume:
evaluate_infix_list will receive a correct infix expression, consisting of individual tokens, and followed by an additional symbol for end of input
the operands and operators will describe a correctly formed expression with no syntax errors
all operators for this assignment are in the set { +, -, *, /, %}
the minus sign will only appear as a subtraction symbol, and not as a unary negation operator
all of the numeric values will be positive integers (subtraction may create negative values)
all divisions using / will come out evenly without any fraction or remainder
the provided expression does not require dividing by zero
One may NOT assume:
numeric values consist of exactly one numeric digit (see 12 above)
that there will always be a sum or multiplication operator (see 12 above)
that the terminating symbol is a semicolon (it may be anything not part of the expression)
that operators cannot appear more than once in the expression (e.g. 12 – 4 – 3)
that parentheses may only appear once in the expression (they may even be nested)
Following the Specification Details is Expected
Often the code written for one assignment will be reused or adapted for a later assignment. The given specifications are designed to facilitate compatibility between each phase; straying far from them will only complicate matters and add additional work.
Also, since the test code the TA’s will be using will be making specific assumptions about the interface to your code, so failure to match the interface will interfere with grading.
For example, the testing code will call the eval_infix function above (because that makes it much easier to test). It will assume that there is a function with exactly that name that takes one string parameter — if you change the name or the number or type of parameters, then your solution will not be called, and your output will fail.
The test code also assumes that the file is named infix1.py, but it is possible for the grader to assign that file name when downloading your solution (with just a little effort)
Incidentally, the documentation above does state that the input will be a series of space-separated tokens. That will be true for this assignment. The next homework will be removing that assumption, and accept input like “2+3”.
Following the Recommended Algorithms is Encouraged
It was recommended above to have one function handle addition and subtraction, another to handle multiplication and division, and another to handle factors. There are indeed other ways to parse the input correctly, but this is the approach that will most facilitate later assignments.
If you attempt to do all of your parsing with a single function, not only will operator precedence complicate your problem here, but will also complicate later assignments that involve additional operators of different precedence, and even operators that do not expect exactly two operands.
Also, the algorithm above allows the parser to scan the input sequentially from beginning to end, without backtracking or skipping around or copying segments of the input to new variables. Any solution that involves those sorts of operations will run into extreme difficulty even in the very next assignment.
Unit Testing
A good habit to get into, especially for Python programming, is to include your own test cases directly into the program file. This can be done by placing some extra code at the bottom of the file that specifically test the functions implemented within that same file.
For example, the instructor’s solution at this time of writing currently has the following at the very bottom:
if __name__ == “__main__”:
print ( eval_infix(“15 “) )
print ( eval_infix( “2 + 3 ” ) )
print ( eval_infix( ” 2 * 3 + 1 ” ) )
print ( eval_infix( ” 2 + 3 * 1″ ) )
print ( eval_infix( ” 1 + ( 2 + 10 * 3 ) * 10 ” ) )
The advantage of these unit tests will be come more evident later in the course when the homework assignment will be split across many program files. If each file has its own set of test cases completely testing its own code, it will be much easier to identify which program file contains bugs.
Submission and Evaluation
In general, homework scoring will be something like:
10%
readability (how easy was it to read to grade?)
30%
implementation (does source code look right?)
10%
executability (how far does it go before crashing?)
50%
correctness (how much does it do correctly?)
And, as stated before, actual test cases will not be provided, so students are encouraged to test as well as they can.
Assignments all have due dates, but will be accepted until nearly a week later, with a lateness penalty assessed per weekday. It is important to note the distinction between the official due date and the final deadline.
Multiple submissions are accepted, but only a small finite number will be examined. If more than one submission is on time, only the latest will count (assuming it is the best). If there are multiple late submissions, only the earliest and latest will be examined.
Take care not to erase, overwrite, or lose any homework submission before you receive a score for it. If something unusual happens that interferes with your submission, it may be necessary to reconstruct what it was that you intended to turn in, and anything that has a last-modified date later than the final deadline cannot be easily evaluated.
Extra Credit Option
Support the exponentiation operator
The ** symbol in Python stands for exponentiation.
For example, 2 ** 3 computes two to the third power, and yields 8.
This operator is of higher precedence than multiplication and division — but is also special in that it associates from right to left. That is:
2 ** 3 ** 2 == 2 ** ( 3 ** 2 ) , not ( 2 ** 3 ) ** 2
Full credit will be given to the simplest solution, which requires no ad