Homework 1 solution

Homework 1 2 Sept 2016
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 anaddition, 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 seriesof 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 iseither 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. Onewill 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 multipleassignment 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
You may place tests directly into the Infix.py file, after all of the functions. You can also surround your tests with the same if statement 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.