CMPSC-132: Programming and Computation II

CMPSC-132: Programming and Computation II
Fall 2019
Homework 3
Due Date: 11/03/2019, 11:59PM
100 pts + Extra Credit
Read the instructions carefully before starting the assignment. Make sure your code follows the
stated guidelines to ensure full credit for your work.
Instructions:
– This is a teamwork assignment. Each team should be working on their own. Only one
student (the team leader) must upload the submission, however, you must add the second
member of the team into the Gradescope submission. Watch how to submit group
submissions on Gradescope here: https://youtu.be/rue7p_kATLA (failing to do this will
result in your teammate receiving a 0 score in the assignment)
– Download the starter code file from the HW3 Assignment on Canvas. Do not change
the function names or given started code on your script.
– You are responsible for debugging and testing your code with enough data, you can share
testing code on Piazza.
Goal:
✓ Part 1: 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:
• 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 not allowed to use any other data structures to copy the elements of the Stack for
manipulating purposes.
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
– 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: As discussed in the Module 6 video lectures, an arithmetic expression can be written in
three different but equivalent notations: infix, prefix and postfix. 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 nonempty string that represents an arithmetic expression in infix notation.
class Calculator:
def __init__(self):
self.expr = None
This an 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’
This class includes 3 methods that you must implement:
• 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. An easy way to check if str to float is possible
is with a try-except block
isNumber(‘Hello’) returns False

isNumber(‘
isNumber(‘
2658.5
2
‘) returns True
8 ‘) returns False

• postfix(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 postfix receives an invalid expression, it should return a string containing the word
‘error’ or the None keyword. Examples of invalid expressions are ‘ 4 * / 5’, ‘ 4
+ ‘, ‘ ^4 5’, ‘( 3.5 + 5 ‘, ‘3. 5 + 4’
• calculate(): This property method takes the non-empty string self.expr, an arithmetic
expression in infix notation, calls postfix(expr) to obtain the postfix expression of self.expr and
then uses a Stack as described in the Stack video lecture to evaluate the obtained postfix
expression. All values returned by calculator should be float, unless the expression is invalid.
– The function must return the computed value as float if expr is a correct formula, otherwise
it must return None or an error message.
– Do not use exec or eval function. You will not receive credit if your program uses any of
the two functions anywhere
Grading Notes:
– Supported operations are addition (+), subtraction (-), multiplication(*), division (/) and
exponentiation (^), note that exponentiation is ** in Python
– You can write other utility methods to generalize your code and assist you with string
processing and input validation, but don’t forget to document them.
– The grading script will feed 10 randomly chosen test inputs for each function. Three of them
will be inputs that should cause an error such as ‘4.2 * 5/ 2 + ^2’ or ‘4 * (5/ 2) +
^)2(‘, whose expected returned value and error message or the None keyword.
– Grading Percentage: The correctness of your code represents a fraction of your score, but other
items are also part of your final assignment score:
Correctness-Functionality – 70%
Format and Effort – 20% (comments, clarity, etc)
Submit Peer evaluation survey – 10% (release after due date)
– If calculator checks if the expression is valid before passing it to postfix, there is no need
to check it again in postfix, so you can ignore/remove the error message cases from the
postfix doctest and add them in calculator and viceversa
– You can define precedence of operators using a dictionary
Invalid expression for this assignment:
An error message (or None) should be returned when the expression:
– Contains non supported operators, for example ‘ 4 * $ 5’
– Contains two consecutive operators ‘ 4 * + 5’
– Has unbalanced parentheses ‘ )4 * 5(‘, ‘ (4 * 5)+(‘
– ‘3(5)’ is an invalid expression, valid multiplication will be denoted as ‘3*5’ or ‘3*(5)’
– ‘ 2 5’ is an invalid expression, so be careful if you are removing spaces using replace,
you could be transforming an invalid expression into a valid one. Useful tip: Remember that
strip() removes spaces at the beginning and at the end of a string, so calling ‘ 2 5
‘.strip()returns a new string ‘2 5’
Deliverables:
• Submit it to the HW3 Gradescope assignment before the due date
Notes
Infix to Postfix Review
3+4*5/6 to postfix?
Step 1: If not done, parenthesize the entirely infix expression according to the order of priority you
want. Since the given expression is not parenthesized, two examples are shown below:
(((3+4)*5)/6) and (3+((4*5)/6))
Step 2: Move each operator to its corresponding right parenthesis
(((3+4)*5)/6) ===> (((3 4) + 5) * 6)/
(3+((4*5)/6)) ===> (3 ((4 5) * 6) / ) +
Step 3: Remove all parentheses
(((3+4)*5)/6) ==> (((3 4) + 5) * 6)/ ==> 3 4 + 5 * 6 /
(3+((4*5)/6)) ==> (3 ((4 5) * 6) / ) + ==> 3 4 5 * 6 / +
(300+23)*(43-21)/(84+7) to postfix?
(((300+23)*(43-21))/(84+7)) ==> (((300 23) + (43 21) -)* (84 7)+)/
300 23 + 43 21 – * 84 7 + /
Tips for using the Stack to convert to postfix
Let’s consider an expression in infix notation:
expr= ‘2 * 5 + 3 ^ 2-1 +4’

pos 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
expr 2 * 5 + 3 ^ 2 + 1 + 4

postfix_expression ?

Current portion of expr Stack postfix_expression
2 2
* * 2
5 * 2 5
+ + 2 5 * + has lower precedence
than *
3 + 2 5 * 3
^ + ^ 2 5 * 3
2 + ^ 2 5 * 3 2
2 5 * 3 2 ^ + – has lower precedence
that ^ and equal
precedence than +.
12 5 * 3 2 ^ + 1
+ + 2 5 * 3 2 ^ + 1 – + has equal precedence
than -.
4 + 2 5 * 3 2 ^ + 1 – 4 End of expr reached
2 5 * 3 2 ^ + 1 – 4 +

Now, let’s consider an expression in infix notation with parentheses:
expr= ‘2* ((5 + 3)) /9’

pos 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
expr 2 * ( ( 5 + 3 ) ) / 9

Before starting any computations, does the expression has balanced parenthesis? No, return error
postfix_expression ?

Current portion of expr Stack postfix_expression
2 2
* * 2
( * ( 2
( * ( ( 2
5 * ( ( 2 5
+ * ( ( + 2 5
3 * ( ( + 2 5 3
) * ( 2 5 3 + inner expression
) * 2 5 3 + inner expression
/ / 2 5 3 + * / has equal precedence
than *.
9 / 2 5 3 + * 9 End of expr reached
2 5 3 + * 9 /

In general:
• If the item is a left parenthesis, push it on the stack
• If the item is a right parenthesis: discard it and pop from the stack until you encounter a
left parenthesis
• If the item is an operator and has higher precedence than the operator on the top of the
stack, push it on the stack
• If the item is an operator and has lower or equal precedence than the operator on the top
of the stack, pop from the stack until this is not true. Then, push the incoming operator on
the stack
** If you are attempting any of the extra credit opportunities, you must submit your code in
the HW3 – Extra Credit Gradescope assignment before the due date
The given examples just represent the expected output, not the syntax for using the function
EXTRA CREDIT #1: 30 pts, added regardless of the maximum 100
In the regular assignment, two consecutive operators return an error message

>>> postfix(‘
‘error’
2 * 5.4 + 3 ^ -2+1 +4 ‘)

>>> calculate(‘ 2 * 5 + 3 ^ -2+1 +4 ‘)
‘error’
Modify your code to support negation
>>> postfix(‘ 2 * 5 + 3 ^ -2+1 +4 ‘)
‘2.0 5.0 * 3.0 -2.0 ^ + 1.0 + 4.0 +’

>>> postfix(‘-2 * 5 + 3 ^ 2+1 +
‘-2.0 5.0 * 3.0 2.0 ^ + 1.0 + 4.0 +’
4′)

>>> postfix(‘-2 * -5 + 3 ^ 2+1 + 4’)
‘-2.0 -5.0 * 3.0 2.0 ^ + 1.0 + 4.0 +’

>>> postfix(‘2 * + 5 + 3 ^ 2
‘error’
+1 +4′)
>>> calculate(‘ 2 * 5
15.11111111111111
+ 3 ^ -2+1 +4 ‘)

>>> calculate(‘-2 * 5 + 3 ^ 2+1 + 4’)
4.0

>>> calculate(‘ -2 /
8.5
(-4) * (3 – 2*( 4- 2^3)) + 3′)

>>> calculate(‘2 + 3 * ( -2 +(-3) *(5^2 – 2*3^(-2) ) *(-4) ) * ( 2 /8 + 2*( 3 –
1/ 3) ) – 2/ 3^2′)
4948.611111111111
EXTRA CREDIT #2: 50 pts, added regardless of the maximum 100
In our regular assignment, ‘3(5)’ is an invalid expression, since valid multiplication is denoted
as ‘3*5’ or ‘3*(5)’. Modify your code to support the * omission. For example, ‘3(5)’ is treated
as ‘3*(5)’. You can create a method to add the missing stars in in self.expr before passing it to
postfix. You need to figure out the necessary and sufficient rules to add the missing *, for example,
if there is an operand followed by a “(“, then insert a *.
>>> calculate(‘ 3 ( 5 )- 15 + 85 (12) ‘)
1020.0

>>> calculate(‘
46.6666666667
(-2/6)+ (5(9.4)) ‘)

Leave a Reply

Your email address will not be published.