Question Details

(Solved) class Peekable: """An iterator with the ability to examine a value without advancement""" def...


 

The homework to work on is Homework 2, but Homework 2 is based on Homework 1, so I included those instructions to ease the process. I also included a code I have that doesn't work. All that needs to be done is look at the code I have provided and edit it so it actually works. And in the attachment, there is also the peekable.py file, this dude talks about. He likes it when you follow his template/outline, so the best way to solve it is to follow what he says to do. The class just started, so we haven't covered much other than classes, lists, etc... Very basic. Anything fancy like eval() or tokenize won't be accepted. Please help. 


Homework 1
20 January 2017

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:

  1. 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 -.
  2. Implement eval_infix_product using a similar algorithm to the one provided.Test for expressions using any combination of +, -, *, /.
  3. 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 additional functions or loops.

Homework 2

3 Feb 2017

This assignment will focus on the abstraction of iterators, using them to parse the input for the assignment. Part of the assignment will implement an iterator to examine the input data, and another will make use of that iterator to parse the given expression in producing an outcome.

Problem Description

The previous assignment assumes its input includes spaces between every token in an expression, but many programmers tend not to use so many spaces, if the expression is unambiguous. For example, both of the following expressions would be considered to be equivalent:

     1 + 2 * 3                               1 + 2*3 

If the expression on the right was provided as input to the first homework assignment, the lack of spaces would cause the "2*3" to be interpreted as a single token, so it would not perform any multiplication, and might not make any sense of the token at all.

Of course, it is a simple concept to imagine adding functionality to take a full character string, and then to create a new version that has all the spaces included. However, that requires both the time to create that new version, but also the memory to hold it. Any programmer intending for maximal efficiency and minimal time should like to eliminate that extra step.

In fact, the previous homework itself had an intermediate step creating a new variable -- it took a single character string, and created a list of shorter character strings, and then used a subscript variable to visit each element of that list.

This goal of this assignment is to eliminate all of those middle steps and to interpret the numeric expression directly from the original character string, without taking any time to allocate new lists or arrays.

Identifying Tokens

The first phase of this project is to take the input string and divide it up into tokens (individual numbers and operators). The goal here is to let a caller ask for each token in turn and to supply it on demand.

The simplest approach is one presented in a recitation assignment that only requires implementing a single function -- a generator that yields one token at a time as it finds it in the input string.

Here is an intentionally incomplete illustration from the instructor's solution, as it stands at this time of writing:

(in newsplit.py) def new_split_iter( expr )       """divide a character string into individual tokens, which need not be separated by spaces (but can be!)    also, the results are returned in a manner similar to iterator instead of a new data structure    """       expr = expr + ";"                # append new symbol to mark end of data, for simplicity       pos = 0                             # begin at first character position in the list       while expr[pos] != ";"         # repeat until the end of the input is found                   ----  to be filled in by the student, using yield as necessary 

You may identify whether an individual character is a numeric digit via expr[pos].isdigit() There are similar functions isalpha for letters and isalnum for alphanumerics (letters or digits).

Where Python iterators fall short

To qualify as an iterator in Python, it is sufficient to support two operations: 
-- get started (usually through a call to iter()) 
-- obtain the next element, (through an explicit or implicit call for next())

Unfortunately, this is insufficient for the parser in this assignment. Consider the example "1 + 2 * 3". The function that parses products will use the 'next' operation to obtain the plus sign, and determine that it is not a multiplication operator, returning control to the function that parses sums. But if that function were to ask for the 'next' symbol, it would move forward to the 2 and not see the plus sign. One could consider having every function pass its last scanned symbol to its caller, but that would likely make the interface look very clumsy.

The better solution, in the instructor's opinion, is to extend the definition of the iterator to allow it to examine data without moving forward. In fact, other programmers believe the same thing -- there is a package online that adds a great deal more functionality to the default language's iteration. In fact, the instructor's solution was based partly on seeing the proposed interface to the more powerful iterator (but without seeing any of the implementation).

The file peekable.py is provided free for this course and for student use within the course. It is expected to never be modified by the students or submitted in solutions. This example follows the second model from the recitation for an iterator, but can apply its functionality to any other variety of iterator.

Assignment Specifications

The student submission will is to consist of two files: 
-- A completed newsplit.py based on what was given above, defining a function new_split_iter that accepts a character string, and continually uses the yield statement to return the individual tokens as character strings. 
-- A file named infix2.py that very much resembles the infix1.py from Homework 1. The primary difference is that the function parameters will no longer consist of a list and an integer subscript, but will instead receive all data through an iterator.

Here appear a very few select lines from the instructor's solution, as it appears at the time of this writing:

# import peek functionality for iterators # and maybe the splitter, if you need it from peekable import Peekable, peek from newsplit import new_split_iter def eval_infix_sum(iterator)    """evaluate sum expression (zero or more additions or subtractions), using an iterator"""      .....    code that no longer uses array subscripting def eval_infix_iter(iterator)    """evaluate an expression, given an iterator to its tokens"""     return eval_infix_sum(Peekable(iterator))      def eval_infix(expr)    """accept a character string, split it into tokens, then evaluate"""     return eval_infix_iter(new_split_iter(expr)) 

Specification Details

You may assume:

  • Correctly formed expressions consisting of integers and operators
  • All digits within an integer are adjacent ("12" is valid, but "1 2" is not)
  • All operators are single characters (accepting "//" is not required)
  • There will be no division by zero operation in given expressions

You may not assume:

  • anything about how many spaces appear between tokens (may be 0, 1, or more)
  • anything about how many space characters appear at beginning and end of input
  • anything about how many tokens may appear within a given input string
  • any assumptions disallowed in the previous assignment about expressions

Suggested Order of Solution

Since Python already provides a sort of iteration for free, you might start with the infix2.py part of this assignment. It can then be tested with code like:

     print( eval_infix_iter( iter(["2","+',"3"])) ) 

And once that works for lists of separated tokens, you can focus on the newsplit.py that does the separating.

Unit Testing

Another feature of the Python language that has no equivalent in C++ is the ability to embed test code within each file, which may be used to test the functionality of that file. It includes a conditional test that determines whether that file is being run by itself (for testing) or is being used in a larger project.

Here is a portion of the instructor's infix2.py, following the code shown above:

if __name__ == "__main__":     print ( eval_infix_iter( iter(["2","+","3"])) )     print ( eval_infix("15 ") )     print ( eval_infix( " 2 * 3 + 1  " ) )     print ( eval_infix( " 2 + 3 * 1" ) ) 

If the Python environment is told to run infix2.py directly, it will attempt these print statements. On the other hand, the Python environment is told to run some other file, this code is skipped.

Along the same lines, here is a test statement in the instructor's newsplit.py testing the iterator's results:

    print (list( new_split_iter( "3+4 * 5" ))) 

Grading and Evaluation

The TA's will be testing your submission using a separate file that consists of lines like  these:

from infix2 import eval_infix_iter from newsplit import new_split_iter def test(expr):     print (expr, '=', eval_infix_iter(new_split_iter(expr))) test("15")

There will be of course several test cases not shown here, but this will show how everything interacts. A character string expr is provided to the function new_split_iter that returns an iterator to be used by the parsing function from Homework 1, as adapted for an iterator. The print function simply displays the input string and the calculated result.

Planning Ahead

Later in this course, we will use this same program file to recognize variable names and relational operators.

A few relational operators have two characters: {"<=", ">=", "!=", "=="}. That does violate the assumption I said you could make earlier for this assignment, but if you can support them now, you won't have to do it later. A handy note here is that the second character in all of these is always '='.

Extra Credit Option

Support the unary minus (negation) operator.

This symbol would be a separate token which may be the first symbol in the input, or the first in a parenthesized sub-expression. For example, the following would be a valid expression, evaluating to +9

     - 3 * ( - 5 + 2 )

If you supported exponentiation in Homework 1, it should be noted that "-3 ** 2" is equal to -9, and not +9. Since there is no requirement to have newsplit.py support the ** operator, tests for this may bypass that splitting phase.

Full credit will be given to the simplest implementations, appearing in only one place in the program, and also disallowing consecutive operators, as in

    2 + - 3        # not a valid input.    should be 2 + ( - 3 )


Code that doesn't work 

from peekable import Peekable, peek

from new_split import new_split_iter

def new_split_iter( expr ):

     expr = expr + ";"              

     pos = 0                            

     while expr[pos] != ";":       

       yield ";"                            

   

def eval_infix_sum(expr, pos):

    ans, pos = eval_infix_product(expr, pos)       

    oper = expr[pos]

    while oper == '+' or oper == '-':                 

       other, pos = eval_infix_product(expr, pos+1)

       if oper == '+':

           ans = ans + other                       

       else:

           ans = ans - other

       oper = expr[pos]

    return ans, pos

def eval_infix_product(expr, pos):

    ans, pos = eval_infix_factor(expr, pos)        

    oper = expr[pos]

    while oper == '*' or oper == '/' or oper == '%':

       other, pos = eval_infix_factor(expr, pos+1)  

       if oper == '*':

           ans = ans * other                         

       elif oper == '/':

           ans = ans // other                    

       else:

           ans = ans % other

       oper = expr[pos]

    return ans, pos

def eval_infix_factor(expr, pos):

    if expr[pos] == '(':                           

       ans, pos = eval_infix_sum(expr, pos+1)

       return ans, pos+1                            

    else:

       return int(expr[pos]), pos+1

def eval_infix_list( expr ):

    ans, discard = eval_infix_sum( expr, 0 )   

    return ans

def eval_infix( expr ):

      return eval_infix_list(new_split_iter(expr))

def new_split_iter( expr ):

     expr = expr + ";"               

     pos = 0                            

     while expr[pos] != ";":      

       yield ";"                            

    

START_FOR_SYMBOLS = {'+': 0,

                    '*': 1,

                    '/':1,

                    '-':0

                    }

OP_FOR_SYMBOL = {'+': op.add,

                '*': op.mul,

                '/': op.truediv,

                '-': op.sub

                }


def innermost_parens(text):

    if not '(' in text and not ')' in text:

       return text

    open_ = text.index('(')

    close_ = text.rindex(')')

    return innermost_parens(text[open_+1:close_])


def infix_eval(expr):

    a, oper, b = expr.split()

    return OP_FOR_SYMBOL[oper](float(a),float(b))

def  eval_infix_sum(iterator):

    ans = eval_infix_product(iterator)

    while peek(iterator) == '+' or peek(iterator) == '-':

       operation = next(iterator)

       updateAns = eval_infix_product(iterator)

    if operation == '+':

       ans += updateAns

    elif operation == '-':

       ans -= updateAns

    return ans


def eval_infix_product(iterator):

    ans = eval_infix_factor(iterator)

    while peek(iterator) == '*' or peek(iterator) == '/':

       operation = next(iterator)

       updateAns = eval_infix_factor(iterator)

    if operation == '*':

       ans *= updateAns

    elif operation == '/':

       ans /= updateAns

    return ans

def eval_infix_factor(iterator):

    if peek(iterator) == '(':

       ans = eval_infix_sum(iterator)

def full_eval(expr, eval_type):

    if len(expr.split(' ')) == 1:

       return float(expr)

    inn = innermost_parens(expr)

    new_expr = expr.replace('('+str(inn)+')',str(eval_type(inn)))

    return full_eval(new_expr, eval_type)

def interface():

    evaller = lambda expr: full_eval(expr, infix_eval)

    while True:

       result = evaller(input('> '))

       print(result)

def innermost_parens(text):   

    start = 0

    end = len(text)

    for (i, c) in enumerate(text):

       if c == '(':

           start = i

       if c == ')':

           end = i + 1

           break

    return text[start:end]


def full_eval(expr, eval_type):

    while len(expr.split()) != 1:

       inn = innermost_parens(expr)

       result = eval_type(inn.strip('(').strip(')').strip())

       expr = expr.replace(inn, str(result))

    return float(expr)

if __name__ == "__main__":

    doctest.testmod()

    interface()












class Peekable:
&quot;&quot;&quot;An iterator with the ability to examine a value without advancement&quot;&quot;&quot;
def __init__(self, iterator):
&quot;&quot;&quot;Take an existing iterator and add peek functionality
iterator
-- the previous 'ordinary iterator
&quot;&quot;&quot;
self._iterator = iterator;
self._peeked = None
# the following two methods meet the protocol for iterators def __iter__(self):
return self
def __next__(self):
&quot;&quot;&quot;return the next element of the data (as would be expected)
no advancement occurs if that element has already been peeked at
&quot;&quot;&quot;
if self._peeked is None:
self._peeked = next(self._iterator)
ans = self._peeked
self._peeked = None
# we don't yet see what comes next
return ans
def peek(self):
&quot;&quot;&quot;peek at the next element of the data
only advancing if that next item has not yet been peeked at
&quot;&quot;&quot;
if self._peeked is None:
try:
self._peeked = next(self._iterator)
except StopIteration:
self._peeked = None
return self._peeked
# this function is defined just to allow similarity to next()
def peek(x):
return x.peek()
if __name__ == &quot;__main__&quot;:
i = Peekable(iter([1,2,3,4,5]))
print( peek(i) )
# peek at the 1
print( peek(i) )
# and again
print( next(i) )
# should also be the 1 we were looking at
print( next(i) )
# move on and return 2
print( next(i) )
# move on and return 3
print( peek(i) )
# peek at the 4
print( next(i) )
# which is still there before this advances
print( list(Peekable(iter([1,2,3,4,5]))) )
# still iterates normallly

 


Solution details:
STATUS
Answered
QUALITY
Approved
ANSWER RATING

This question was answered on: Sep 05, 2019

PRICE: $18

Solution~000200036354.zip (25.37 KB)

Buy this answer for only: $18

This attachment is locked

We have a ready expert answer for this paper which you can use for in-depth understanding, research editing or paraphrasing. You can buy it or order for a fresh, original and plagiarism-free solution (Deadline assured. Flexible pricing. TurnItIn Report provided)

Pay using PayPal (No PayPal account Required) or your credit card . All your purchases are securely protected by .
SiteLock

About this Question

STATUS

Answered

QUALITY

Approved

DATE ANSWERED

Sep 05, 2019

EXPERT

Tutor

ANSWER RATING

GET INSTANT HELP/h4>

We have top-notch tutors who can do your essay/homework for you at a reasonable cost and then you can simply use that essay as a template to build your own arguments.

You can also use these solutions:

  • As a reference for in-depth understanding of the subject.
  • As a source of ideas / reasoning for your own research (if properly referenced)
  • For editing and paraphrasing (check your institution's definition of plagiarism and recommended paraphrase).
This we believe is a better way of understanding a problem and makes use of the efficiency of time of the student.

NEW ASSIGNMENT HELP?

Order New Solution. Quick Turnaround

Click on the button below in order to Order for a New, Original and High-Quality Essay Solutions. New orders are original solutions and precise to your writing instruction requirements. Place a New Order using the button below.

WE GUARANTEE, THAT YOUR PAPER WILL BE WRITTEN FROM SCRATCH AND WITHIN YOUR SET DEADLINE.

Order Now