QuestionQuestion

Instructions:
- Download the starter code file from the HW3 Assignment. Do not change the function names or given started code on your script.
- A doctest is provided as an example of code functionality. Getting the same result as the doctest does not guarantee full credit. You are responsible for debugging and testing your code with enough data, you can share ideas and testing code during your recitation class. As a reminder, Gradescope should not be used to debug and test code!
- Each function must return the output
- Do not include test code outside any function in the upload. Printing unwanted or ill- formatted data to output will cause the test cases to fail. Remove all your testing code before uploading your file (You can also remove the doctest). Do not include the input() function in your submission.
- Examples of functionality are given in the starter code. Your code should return None when an expression was not validated.
• push(item) adds a new Node with value=item to the top of the stack. It needs the item and returns nothing.
• pop() removes the top Node from the stack. It needs no parameters and returns the value of the Node removed from the stack. Modifies the stack.
• peek() returns the value of the top Node from the stack but does not remove it. It needs no parameters. The stack is not modified.
• isEmpty() tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
• len(stack_object) returns the number of items on the stack. It needs no parameters and returns an integer.
- You are responsible for debugging and testing your code with enough data, you can share testing code on Piazza.

Goal:
✓ Part I: In the Module 5 video lectures, we discussed the abstract data structure Stack. A stack is a collection of items where items are added to and removed from the top (LIFO). Use the Node class (an object with a data field and a pointer to the next element) to implement the stack data structure with the following operations:

You are not allowed to use any other data structures to copy the elements of the Stack for manipulating purposes. You are not allowed to use the built-in stack tool from Python, or to use a Python list to simulate a stack. Your stack must be implemented with a Linked List, in other words, create nodes and use the next attribute to link the items in the stack (the procedure for this is given in the video lectures)

EXAMPLE
>>> x=Stack()
>>> x.pop()
>>> x.push(2)
>>> x.push(4)
>>> x.push(6)
>>> x
Top:Node(6)
Stack:
6
4
2
>>> x.pop()
6
>>> x
Top:Node(4)
Stack:
4
2
>>> len(x)
2
>>> x.isEmpty()
False
>>> x.push(15)
>>> x
Top:Node(15)
Stack:
15
4
2
>>> x.peek()
15
>>> x
Top:Node(15)
Stack:
15
4
2

Tips:
- Make sure you update the top pointer according to the operation performed
- Starter code contains the special methods __str__ and __repr__, use them to ensure the stack operations are updating the elements in the stack correctly. You are not allowed to modify them
- When a method is asking to return the value of a node, make sure you are returning node.value and not a Node object

✓ Part 2: An arithmetic expression can be written in three different but equivalent notations: infix, prefix and postfix (Check the Module 6 video lectures for more on postfix notation). Postfix is a notation for writing arithmetic expressions in which the operands appear before their operators (a+b is ab+). In postfix expressions, there are no precedence rules to learn, and parentheses are never needed. Because of this simplicity, some popular hand-held calculators use postfix notation to avoid the complications of the multiple parentheses required in nontrivial infix expressions. In the starter code, there is a class called Calculator. This class takes no arguments and initializes Calculator object with an attribute called expr set to None. This attribute is then set to a non-empty string that represents an arithmetic expression in infix notation.

class Calculator:
    def __init__(self):
       self.__expr = None

This arithmetic expression might include numeric values, five arithmetic operators (+, -, /, * and ^), parentheses and extra spaces. Examples of such expression are ' -4.75 * 5 - 2.01 / (3 * 7) + 2 ^ 5' and '4.75+5-2.01*5'. Methods in this class will scan the expression from left to right, following PEMDAS rules. This means, we will first perform exponents, division and multiplication in the order they occur from left to right, and finally addition and subtraction

This class includes 3 methods that you must implement:
• [15 pts] isNumber(txt), where txt is a non-empty string. It returns a boolean value. True if txt is a string convertible to float, otherwise False. Note that ' -25.22222 ' is a string convertible to float but ' -22 33 ' and '122 . 45' are not. Hint: An easy way to check if str to float is possible is with a try-except block

isNumber('Hello') returns False
isNumber(' 2658.5 ') returns True isNumber(' 2 8 ') returns False

• [45 pts] _getPostfix(expr): where expr is a non-empty string. This method takes an arithmetic expression in infix notation (string) and returns a string that contains expr in postfix notation (see doctest in starter code for string formatting).

- All numbers in the string must be represented using its float format. The method isNumber could be extremely useful to determine whether the string between two operators is a valid number or not.

- You must use the Stack code from Part 1 to convert expr into a postfix expression, otherwise your code will not get credit. See the Notes at the end of the instructions for examples of how the stack could be used for this process

- If _getPostfix receives an invalid expression, it should return the None keyword.

Examples:

ofinvalidexpressionsare' 4* / 5','4 +',' ^45','(3.5+5 ', '3. 5 + 4'

• [20 pts] calculate: This property method takes the non-empty string self.__expr, an

arithmetic expression in infix notation, calls _getPostfix(expr) to obtain the postfix expression of

self.__expr and then uses a Stack (as described in the Stack video lecture from Module

5) to evaluate the obtained postfix expression. All values returned by calculator should be float if expr is a correct expression, otherwise it must return None.

Do not use exec or eval function
- . You will not receive credit if your program uses any of the two functions anywhere
- Note that you can write the code for this method without having an implementation for _getPostfix. The process for calculate is explained during the stack video lectures.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

#HW3
#Due Date:
########################################
#                                    
# Name:
# Collaboration Statement:            
#
########################################

class Node:
    def __init__(self, value):
       self.value = value
       self.next = None
   
    def __str__(self):
       return "Node({})".format(self.value)

    __repr__ = __str__
                        

#=============================================== Part I ==============================================

class Stack:
    '''
       >>> x=Stack()
       >>> x.pop()
       >>> x.push(2)
       >>> x.push(4)
       >>> x.push(6)
       >>> x
       Top:Node(6)
       Stack:
       6
       4
       2
       >>> x.pop()
       6
       >>> x
       Top:Node(4)
       Stack:
       4
       2
       >>> len(x)
       2
       >>> x.peek()
       4
    '''
    def __init__(self):
       # YOU ARE NOT ALLOWED TO MODIFY THE CONSTRUCTOR
       self.top = None
       self.count=0
   
    def __str__(self):
       # YOU ARE NOT ALLOWED TO MODIFY THE THIS METHOD
       temp=self.top
       out=[]
       while temp:
            out.append(str(temp.value))
            temp=temp.next
       out='\n'.join(out)
       return ('Top:{}\nStack:\n{}'.format(self.top,out))

    __repr__=__str__

    def isEmpty(self):
       # YOUR CODE STARTS HERE
       return self.top == None

    def __len__(self):
       # YOUR CODE STARTS HERE
       return self.count            

    def push(self,value):
       # YOUR CODE STARTS HERE
       newTop = Node(value)
       newTop.next = self.top
       self.top = newTop
       self.count += 1

   
    def pop(self):
       # YOUR CODE STARTS HERE
       if self.isEmpty():
            return None
      
       item = self.top.value
       self.top = self.top.next
       self.count -= 1
       return item
      

    def peek(self):
       # YOUR CODE STARTS HERE
       if (self.top == None):
            return None
       return self.top.value


#=============================================== Part II ==============================================

class Calculator:
    def __init__(self):
       self.__expr = None

    @property
    def getExpr(self):
       return self.__expr

    def setExpr(self, new_expr):
       if isinstance(new_expr, str) and len(new_expr.strip())>0:
            self.__expr=new_expr
       else:
            print('setExpr error: Invalid expression')
            return None


    def isNumber(self, txt):
       if not isinstance(txt,str) or len(txt.strip())==0:
            print("Argument error in isNumber")
            print(txt)
            return False
       # YOUR CODE STARTS HERE
      
       try:
            f = float(txt)
            return True
       except Exception as ex:
            return False

    def _tokenize(self, txt, operands):
       tokens = []
       token = ''

       txt = '(' + txt + ')'

       for c in txt:
            if (c in {'(',')'} or c in operands):
                if (c == '-' and (len(tokens) == 0 or tokens[-1] in operands or tokens[-1] == '(') and token.strip() == ''):
                   try:
                        if (self.support_negation):
                            pass
                   except Exception as ex:
                        return None

                   token += c
                   continue

                if (token.strip() == '' or self.isNumber(token)):
                   if token.strip() != '':
                        tokens.append(float(token))
                   token = ''
                   tokens.append(c)
                else:
                   return None
            else:...

By purchasing this solution you'll be able to access the following files:
Solution.py.

$25.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Python Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats