CMPS 4143

Programming Assignment-5

[To get the full credit of your programming assignment, find the problem-solving steps and

documentation guidelines listed in ‘Programming Assignments’ section in D2L. You are

supposed to submit a zip file (don’t use winrar to zip) that should contain a documentation

file like a docx file and your codes with proper programming extensions like .java or .py.

Make sure all of your code is compliable or no runtime error. TA will not grade if your code

is not runnable and you will get a zero; Sometimes your grade determines based on how

good you can describe/explain the code to TA and Instructor]

1. (35 points) A stack data structure has following functionalities like empty(), size(), top(),

push() and pop(). See the lecture slides for the details (how it works, complexity, etc.) I

have shown you in the class how to implement a stack using a list data structure. You

need to implement the stack with Linkedlist data structure in python. Implement the

stack means, all of the stack functionalities including the construction of stacks should

present on your code.

2. (30 points) Given the expression as string str, find the duplicate parenthesis from the

expression. Your program will output whether or not finding the duplicates, that is true of

false

Input type: An expression in string; Output type: A boolean value True or False

Example 1:

Input: str = ‘((x+y))+z’

Output: True

Example 2:

Input: strs = (x+y)

Output: False

Example 3:

Input: strs = ‘((x+y)+((z)))’

Output: True

3. (35 points) Write a python code to find the average from a stream. The input of this

program will receive a stream of numbers and a window size to find the moving average

of all the numbers in the sliding window. Write your code in OOP style and solve the

program with queue and or stack data structure.

Input type: Window Size as integer and a stream contains numbers as list;

Output type: A list of float values denoting the moving averages

Example 1:

Input: Window Size = 3; Stream = [1, 10, 3, 5]

Output: [1.0, 5.5, 4.67, 6.0]

Explanation:

1

st iteration -> 1/1 -> 1.0

2

nd iteration -> (1+10)/2 -> 5.5

3

rd iteration -> (1+10+3)/3 -> 4.67

4

th iteration -> (10+3+5)/3 -> 6.0

Example 2:

Input: Window Size = 2; Stream = [1, 10, 3, 5]

Output: [1.0, 5.5, 6.5, 4.0]

Explanation:

1

st iteration -> 1/1 -> 1.0

2

nd iteration -> (1+10)/2 -> 5.5

3

rd iteration -> (10+3)/2 -> 6.5

4

th iteration -> (3+5)/2 -> 4.0

CMPS 4143

# CMPS 4143 Programming Assignment-5

Original price was: $35.00.$30.00Current price is: $30.00.