Write a program to read random strings from a user, consisting of any number of (...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Write a program to read random strings from a user, consisting of any number of "(" and ")" in any combination, and determine whether they contain balanced parentheses until the user wishes to end the program. A string with balanced parentheses is one where each "(" is paired with a ")". For instance, the string "()((())))" has balanced parentheses, but the strings "(", "", "(0", "))(" and "()(0))(0)" do not have balanced parentheses. Given the data structures from the course material, there are two ways you can implement a technique for checking balanced parentheses. 1. Implement a class that uses a stack to determine if a string has balanced parentheses 2. Implement a class that uses queues to determine if a string has balanced parentheses (Hint: two queues can be used to simulate a stack's behavior). Instead of using arrays for the underlying structures of stacks and queues, use linked list representations that do not use built-in list classes. The program may be implemented either in Python, Java, or C++. The program implemented in either language MUST be well-commented, i.e. use block comments for describing each method in a class and give some lines of comments to explain statements. Programs with very few comments (as in just commenting on one of two methods only) or no comments at all will receive a small penalty. If you implement the program in Python, you must write a Class Queue, a Class Stack, a Class Node, a Class Linked List, and a Class StackParenthesesChecker. class Stack(object): __linked List=... __top= ... # constructor for stack class def_init_(self): # code goes here # push item onto stack def push(self,x): # code goes here #pops item from top of stack def pop(self): # code goes here (should return item from top of stack or None if stack is empty) # returns Boolean of whether stack is currently empty def isEmpty(self): # code goes here # returns Boolean of whether stack is currently full def isFull(self): #code goes here #clears the stack def clear(self): #code goes here # looks at the top item of the stack without removing it def peek(self): # code goes here class Queue (object): __._linkedList=... _front=... _rear = # constructor for Queue class def_init_(self): #code goes her # adds item to front of queue def enqueue(self, x): #code goes here # removes item from rear of queue def dequeue(self): #code goes here (should return item from end of queue or None if queue is empty) # returns Boolean of whether queue is currently empty def isEmpty(self): # code goes here # returns Boolean of whether queue is currently full def isFull(self): #code goes here #clears the queue def clear(self): #code goes here #looks at the item at the end of the queue without removing it def poll(self): # code goes here class Linked List (object): _head=None __tail= None _capacity=0 _size=0 # constructor for LinkedList class def __init__(self): # code goes her # add item x to list at index i def add(self, i, x): #code goes here # remove item at index i from the list def remove(self, i): #code goes here (should return item from list or None if item is not in the list) class Node(object): _data = None ___prev = None _next = None # constructor for Node class def__init_(self): #code goes here class StackParenthesesChecker(object): ___stack = ... # constructor for StackParenthesesChecker class def __init__(self): #code goes here # Check if string s has balanced parenthesis def isBalanced(self, s): # code goes here class QueueParenthesesChecker(object): __queue1 = ... __queue2 =... # constructor for QueueParenthesesChecker class def_init__(self): # code goes here # Check if string s has balanced parenthesis def isBalanced(self, s): # code goes here For implementing interface INode, the expected implementing class should be a doubly-linked node, as in the Python version. INode provides only the getter method for next. The implemented Node class will also require getters and setters for a prev attribute, and you will need to cast in your linked list implementation to access the method. Just as in the Python version, two ParenthesesChecker implementing classes must be implemented. Setters and getters are not written for stacks or queues in the interface due to that information only being in context of the class. So, when setting the data structures in the main method, class casting must be used as well to connect the queues to QueueParenthesesChecker and the stack with StackParenthesesChecker. Create several string examples to check functionality of your program. Please see Testing Phase below. Implementation Phase You must work on the assignment individually. If any external source code or information from a website is applied to your implementation, you MUST acknowledge the source with comments in your code. Testing Phase In Python: main.py file... # add import statements here def main(): checker1 = StackParenthesesChecker() checker2 = QueueParenthesesChecker() stack Stack() queue1= Queue() queue2 Queue() setAttribute(stack, '_Stack_linkedList', LinkedList()) setAttribute(queue1, '_Queue_linkedList', LinkedList()) # more setting statements here userString = None # a loop to ask input via console for new string to check with both checkers While user wants to continue program: userString = get user string via console // add more code here to set up checkers and their data structures If checker1.isBalanced (userString) and checker2.isBalanced (userString)): print("The input string %s has balanced parentheses.", userString) Else: print('The input string %s does not have balanced parentheses.', userString) # get user continuation of program via console If name=__main__': main() Expected Output: Accurate determination of balanced parentheses in input strings, for both string checking techniques. The if-statement where the methods are called for checking balance determines whether checks for both techniques are equivalent. Write a program to read random strings from a user, consisting of any number of "(" and ")" in any combination, and determine whether they contain balanced parentheses until the user wishes to end the program. A string with balanced parentheses is one where each "(" is paired with a ")". For instance, the string "()((())))" has balanced parentheses, but the strings "(", "", "(0", "))(" and "()(0))(0)" do not have balanced parentheses. Given the data structures from the course material, there are two ways you can implement a technique for checking balanced parentheses. 1. Implement a class that uses a stack to determine if a string has balanced parentheses 2. Implement a class that uses queues to determine if a string has balanced parentheses (Hint: two queues can be used to simulate a stack's behavior). Instead of using arrays for the underlying structures of stacks and queues, use linked list representations that do not use built-in list classes. The program may be implemented either in Python, Java, or C++. The program implemented in either language MUST be well-commented, i.e. use block comments for describing each method in a class and give some lines of comments to explain statements. Programs with very few comments (as in just commenting on one of two methods only) or no comments at all will receive a small penalty. If you implement the program in Python, you must write a Class Queue, a Class Stack, a Class Node, a Class Linked List, and a Class StackParenthesesChecker. class Stack(object): __linked List=... __top= ... # constructor for stack class def_init_(self): # code goes here # push item onto stack def push(self,x): # code goes here #pops item from top of stack def pop(self): # code goes here (should return item from top of stack or None if stack is empty) # returns Boolean of whether stack is currently empty def isEmpty(self): # code goes here # returns Boolean of whether stack is currently full def isFull(self): #code goes here #clears the stack def clear(self): #code goes here # looks at the top item of the stack without removing it def peek(self): # code goes here class Queue (object): __._linkedList=... _front=... _rear = # constructor for Queue class def_init_(self): #code goes her # adds item to front of queue def enqueue(self, x): #code goes here # removes item from rear of queue def dequeue(self): #code goes here (should return item from end of queue or None if queue is empty) # returns Boolean of whether queue is currently empty def isEmpty(self): # code goes here # returns Boolean of whether queue is currently full def isFull(self): #code goes here #clears the queue def clear(self): #code goes here #looks at the item at the end of the queue without removing it def poll(self): # code goes here class Linked List (object): _head=None __tail= None _capacity=0 _size=0 # constructor for LinkedList class def __init__(self): # code goes her # add item x to list at index i def add(self, i, x): #code goes here # remove item at index i from the list def remove(self, i): #code goes here (should return item from list or None if item is not in the list) class Node(object): _data = None ___prev = None _next = None # constructor for Node class def__init_(self): #code goes here class StackParenthesesChecker(object): ___stack = ... # constructor for StackParenthesesChecker class def __init__(self): #code goes here # Check if string s has balanced parenthesis def isBalanced(self, s): # code goes here class QueueParenthesesChecker(object): __queue1 = ... __queue2 =... # constructor for QueueParenthesesChecker class def_init__(self): # code goes here # Check if string s has balanced parenthesis def isBalanced(self, s): # code goes here For implementing interface INode, the expected implementing class should be a doubly-linked node, as in the Python version. INode provides only the getter method for next. The implemented Node class will also require getters and setters for a prev attribute, and you will need to cast in your linked list implementation to access the method. Just as in the Python version, two ParenthesesChecker implementing classes must be implemented. Setters and getters are not written for stacks or queues in the interface due to that information only being in context of the class. So, when setting the data structures in the main method, class casting must be used as well to connect the queues to QueueParenthesesChecker and the stack with StackParenthesesChecker. Create several string examples to check functionality of your program. Please see Testing Phase below. Implementation Phase You must work on the assignment individually. If any external source code or information from a website is applied to your implementation, you MUST acknowledge the source with comments in your code. Testing Phase In Python: main.py file... # add import statements here def main(): checker1 = StackParenthesesChecker() checker2 = QueueParenthesesChecker() stack Stack() queue1= Queue() queue2 Queue() setAttribute(stack, '_Stack_linkedList', LinkedList()) setAttribute(queue1, '_Queue_linkedList', LinkedList()) # more setting statements here userString = None # a loop to ask input via console for new string to check with both checkers While user wants to continue program: userString = get user string via console // add more code here to set up checkers and their data structures If checker1.isBalanced (userString) and checker2.isBalanced (userString)): print("The input string %s has balanced parentheses.", userString) Else: print('The input string %s does not have balanced parentheses.', userString) # get user continuation of program via console If name=__main__': main() Expected Output: Accurate determination of balanced parentheses in input strings, for both string checking techniques. The if-statement where the methods are called for checking balance determines whether checks for both techniques are equivalent.
Expert Answer:
Answer rating: 100% (QA)
Answer class Node def initself data selfdata data selfnext None class LinkedLis... View the full answer
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these programming questions
-
Direct labor-hours required to support estimated production Machine-hours required to support estimated production Fixed manufacturing overhead cost Variable manufacturing overhead cost per direct...
-
write a abstract on this paper ? Introduction Governments require money to run their operations and pay civil servants who ensure that services to the population are delivered. The money that states...
-
Case Study: Quick Fix Dental Practice Technology requirements Application must be built using Visual Studio 2019 or Visual Studio 2017, professional or enterprise. The community edition is not...
-
What is the discount yield, bond equivalent yield, and effective annual return on a $ 5 million commercial paper issue that currently sells at 98.625 percent of its face value and is 136 days from...
-
If x2 + y2 + 25 and dy/dt = 6, find dx/dt when y = 4.
-
Convert 14.7 miles (mi) into kilometers (km) using the following conversion: 1.61 km = 1 mi (round answer to 2 decimal places) 14.7 mi = km.
-
Mr. A. Gaylord manages a pension fund and believes that his stock selection ability is excellent. However, he is worried because the market could go down. He considers entering an equity swap where...
-
Myles Etter and Crystal Santori are partners who share in the income equally and have capital balances of $210,000 and $62,500, respectively. Etter, with the consent of Santori, sells one-third of...
-
a) Explain the concepts of horizontal equity and vertical equity in the context of taxation. b) Explain the difference between tax deductions and tax credits. c) Are deductions or credits more....
-
When buying or leasing a new car, one of the factors that customers consider is the type of fuel it uses. Some people prefer vehicles that use diesel fuel, while others favor vehicles that use...
-
The Golden Oranges Nursery, which provides facilities for pre-school children on a commercial basis, is preparing its cash budget for next year. A profile of the estimated revenues and expenses for...
-
Some companies now use incentives for current employees when new hires are socially linked to them and thus their social sites served as a source of internal referrals. What are the pros and cons of...
-
The things that might lead a person to quit might not be the same things that lead a person to stay with an organization. For example, another job offer or the tendency to always be looking for new...
-
Reread the Managers Notebook, High-Priced CEOs: Are They Worth It? Develop a list of arguments in favor of the position of Prof. Desai (that CEO pay is irrational) and a list of arguments in favor...
-
A serious barrier to employment of people with disabilities continues to be a perception problem. Managers and coworkers lack knowledge, awareness, and comfort in working with employees with...
-
This exercise asks you to explore your attitudes concerning illegal immigrants in the workplace. a. Would you work for an employer who makes it a point to hire illegal immigrants? Why or why not? b....
-
Write down the nth Riemann sum for the following integrals. (a) (b) S r2 x dx, sin(2x)dx for n = 4. for n = 6.
-
Use this circle graph to answer following Exercises. 1. What fraction of areas maintained by the National Park Service are designated as National Recreation Areas? 2. What fraction of areas...
-
The following additional information is available for the Dr. Ivan and Irene Incisor family. The Incisors own a rental beach house in Hawaii. The beach house was rented for the full year during 2012...
-
Carl and Jenny adopt a Russian orphan. The adoption takes 2 years and two trips to Russia and is final in 2012. They pay $6,000 in 2011 and $7,500 in 2012 of qualified adoption expenses, and have AGI...
-
Your supervisor has asked you to research the following situation concerning Owen and Lisa Cordoncillo. Owen and Lisa are brother and sister. In May 2012, Owen and Lisa exchange business pickup...
-
A 60 kg runner in a sprint moves at 11 m/s. A 60 kg cheetah in a sprint moves at 33 m/s. By what factor does the kinetic energy of the cheetah exceed that of the human runner?
-
The opposite of a wind turbine is an electric fan: The electric energy that powers the fan is converted to the kinetic energy of moving air. A fan is putting 1.0 J of kinetic energy into the air...
-
A fielder tosses a 0.15 kg baseball at 32 m/s at a 30 angle to the horizontal. What is the balls kinetic energy at the start of its motion? What is the kinetic energy at the highest point of its arc?
Study smarter with the SolutionInn App