Lab 3 Solution

Description

Section Readings: 1.3, 1.4

Problem 1. (Matching Parentheses) Implement the static method match() in Parentheses that takes a string s as argument and uses a stack to determine whether its parenthe-ses are properly balanced, and returns true if they are and false otherwise. You may assume that s only consists of parentheses (curly, square, and round).

• java Parentheses [()]{}{[()()]()} <ctrl-d>

true

• java Parentheses [(])

<ctrl-d> false

Problem 2. (Kth String from the End) Write a Queue client KthString that takes a command-line argument k and prints the kth string from the end found on standard input, assuming that standard input has k or more strings.

• java KthString 42 < numbers.txt 236

Problem 3. (Min Max ) Implement the static methods min() and max() in MinMax that take a reference first to the rst node in a linked list of integer-valued items as argument and returns the minimum and the maximum values respectively.

• java MinMax < numbers.txt -289 700

Problem 4. (Equal Pairs) Implement the static method equalPairs() in EqualPairs that takes an array numbers of integer values and returns the number of equal pairs, calculated using a linearithmic algorithm. Hint: Use Arrays.sort() and the fact that the number of ways to select 2 items out of n is ⁿ₂ = n(n 1)=2.

• java EqualPairs

1212234333 <ctrl-d>

10

• java EqualPairs

1212234333077777 <ctrl-d>

20

CS210 Lab 3 Swami Iyer

Files to Submit:

1. Parentheses.java

2. KthString.java

3. MinMax.java

4. EqualPairs.java

Spring 2015 2 of 2