Programming Homework Help

2 Stacks: Character Matching

Consider the following Java interface for stacks:

public interface Stack<T>{

public
T pop();
//
returns the top element

// and removes it from the stack

public
T top();
//
returns top element without
removal

public
void push(T item); // adds
an item to the top

public
boolean isEmpty(); // returns
true if stack is empty

}

Write a non-recursive Java metho d with the signature:

public static boolean matchTest(String cand);

that returns

true

if and only if

cand

is

balanced

in its characters. A string is balanced in

its characters if:

1.

it is empty

2.

it has the form

a xs a

where the

xs

consists of zero or more strings that are balanced

in their characters.

Thus, the following strings:

abbcdeedca

aa

112211

12233441

are all balanced in their characters.

matchTest

must

use a

Stack

to carry out its task