Problem 1

Use a stack to test for balanced parentheses, when scanning the following expressions. Only consider the parentheses [ , ] , ( , ) , { , } . Ignore the variables and operators.

You should read an integer N, which is the number of test cases. Each test case is placed on a separate line.

Sample input:

2

[ a + { b / ( c - d ) + e / (f + g ) } - h ]

[ a { b + [ c ( d + e ) - f ] + g }

Sample output:

true

false

Problem 2

To convert a number from decimal to binary, you simply divide by two until a quotient of zero is reached, then use the successive remainders in reverse order as the binary representation. Use a stack to store the remainder of the division and finally print the binary representation. The first line of input N is the number test cases.

Sample Input

5

0

3

5

7

10

Sample Output:

0

11

101

111

1010

Problem 3

Write a method equals that takes as parameters two stacks of integers and returns true if the two stacks are equal and that returns false otherwise. To be considered equal, the two stacks would have to store the same sequence of integer values in the same order. Your method is to examine the two stacks but must return them to their original state before terminating. You may use one stack as auxiliary storage. The first line of input contains the number of test cases N. After that, each test case will consist of two lines each representing a stack elements.

Sample input

2

1 2 3 4 5

1 2 3 4 5

1 2 3 4

5 6 7 8 9 10

Sample output:

true

false

Problem 5: BONUS Implementing a Stack as a Linked Data Structure

Write the interface StackInt<E> that declares the four methods below. Then, write a class LinkedStack<E> that implements the interface StackInt<E> as a linked list. In other words, your LinkedStack will be built as a LinkedList but will perform as a Stack (concerning pushing, popping and the other operations). You will have to create your own inner class Node<E> and implement the following methods:

? E push (E obj): to push an element at the top of the stack

? E pop(): to remove and return the element at the top of the stack

? E peek(): to return the element at the top of the stack without removing it

? boolean isEmpty(): to check if the stack is empty

For testing purposes, we will unify the class E. Consider E to be a class called City. The City class should have the following attributes and methods:

- private attribute: “name” of type String, representing the city’s name
- private attribute: “country” of type String, representing the country of the city
- a constructor that takes the name and country as parameters
- getters and setters
- toString method of the format: “city_name, countryName”. Example: “Beirut, Lebanon”

Sample Input:

StackBottom| Beirut, Lebanon| Saida, Lebanon| Cairo, Egypt | New York, United States | StackTop

Instructions:

1- Call the isEmpty() method and print “Empty” or “Not Empty” based on the result

2- Use the push method to push all of the elements as shown above

3- Call the peek() method and print the returned City

4- Call the pop() method and print the returned City

5- Call the peek() method and print the returned City

6- Call the isEmpty() method and print “Empty” or “Not Empty” based on the result.

Sample Output:

Empty

New York, United States

New York, United States

Cairo, Egypt

Not Empty

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of