IST homework
This first assignment will focus on coding in Python, applying knowledge students should already have about programming with functions and arrays. 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.
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 C++ 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.
Implementation Hints
One very simple method of parsing input is termed predictive parsing in which each function has an idea of what it expects to see next (or what alternatives it will encounter). For example, we would expect a numeric expression like the one above to include a series of values to be added or subtracted. Whether those values are explicit numbers (such as 12 and 3) or the results of other operations (such as 2*5) might sound like a complication, but that can just be addressed by some other function.
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
For the given example, the first product expression would simply be the value 12. This is followed by a minus sign, so the next product is evaluated to be 10, which is subtracted from 12 to yield 2. Since this is followed by a plus sign, the loop would repeat to evaluate and add the 3. No more operators appear, so the final result is 5.
The above specifications said that some other symbol would appear at the very end of the input. This specification is intended to make it very easy to examine the next token in the while loop condition without having to worry about going beyond the end of the actual data.
Python Implementation Details
Since C++ 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, so it seems that one would need to pass it as a reference parameter to each function, so that they can update it.
Unfortunately, Python does not allow you to pass integer variables by reference in that sense. Every integer parameter would be a reference to an immutable value, and any attempt to increment the integer would simply make it refer to a different value (without changing the function argument's reference).
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
How to test your code
• You may place tests directly into the Infix.py file, after all of the functions. You can also surround your tests with the same ifstatement that appeared in the sample.py from the first recitation.
The advantage of this approach is you only have to choose your test once, and it will be attempted every time to try to run that module.
• You can also call your functions directly from the Python shell. The recitation had a simple example of trying average( [3] ).
The advantage of this approach is that you can make up new tests on the fly to see what happens, without editing the code.
In either case, you can call any function as long as you give it the correct kinds of parameters. Most will want a list of strings and a subscript, like
eval_infix_product( [ "2","*","3",";" ], 0)
. The TA will be calling the function that expects a single space-spearated string, like
eval_infix( "2 * 3" )
This is probably the easier way to test withfrom the Python shell.
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:
• eval_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)
• 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 precednece 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.