Question

What java program would you write to solve the following problems and why does it work? Please also comment on other students’ code at least three times. 1) Implement MyArrayStack (constructor, push, pop, peek and isEmpty), and MyLinkedQueue with both next and previous pointers (constructor, enqueuer/offer, dequeuer/poll, peek and isEmpty), and write the following two program to test them. You must use MyArrayList or MyLinkedList for the implementation. 2) For stack testing, write a program to check if a string has matching parenthesis such as “(())”, but not “)(“. 3) For stack testing, use it to “Evaluating Expressions” using the algorithm given in the class.

What java program would you write to solve the following problems and why does it work? Please also comment on other students’ code at least three times. 1) Add support for exponent ~ for the problem in the previous question. 2) An animal shelter, which holds only dogs and cats, operates on a strictly "first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog, and dequeueCat. You may use the myLinkedlist data structure you created in previous discussion question. 3) You have an integer and you can flip exactly one bit from a O to a 1. Write code to find the length of the longest sequence of 1 s you could create. EXAMPLE Input: 1775 (or: 11011101111) Output: 8.

Answer 1

ANSWER:

SOURCE CODE:

/**

* Stack implementation

*/

public class MyArrayStack<T> {

private int stackSize;

private T[] stackArr;

private int top;

/**

* constructor to create stack with size

* @param size

*/

public MyArrayStack(int size) {

this.stackSize = size;

this.stackArr = (T[]) new Object[stackSize];

this.top = -1;

}

/**

* This method adds new entry to the top

* of the stack

* @param entry

* @throws Exception

*/

public void push(T entry){

if(this.full()){

System.out.println(("Stack is full. Increasing the capacity."));

}

// System.out.println("Adding: "+entry);

this.stackArr[++top] = entry;

}

/**

* This method removes an entry from the

* top of the stack.

* @return

* @throws Exception

*/

public T pop() throws Exception {

if(this.empty()){

throw new Exception("Stack is empty. Can not remove element.");

}

T entry = this.stackArr[top--];

// System.out.println("Removed entry: "+entry);

return entry;

}

/**

* This method returns top of the stack

* without removing it.

* @return

*/

public T peek() {

return stackArr[top];

}

/**

* This method returns true if the stack is

* empty

* @return

*/

public boolean empty() {

return (top == -1);

}

/**

* This method returns true if the stack is full

* @return

*/

public boolean full() {

return (top == stackSize - 1);

}

}

############ Evaluate #######

public class Evaluate {

public static int evaluate(String expression) throws Exception

{

char[] tokens = expression.toCharArray();

// Stack for numbers: 'values'

MyArrayStack<Integer> values = new MyArrayStack<Integer>(100);

// Stack for Operators: 'ops'

MyArrayStack<Character> ops = new MyArrayStack<Character>(100);

for (int i = 0; i < tokens.length; i++)

{

// Current token is a whitespace, skip it

if (tokens[i] == ' ')

continue;

// Current token is a number, push it to stack for numbers

if (tokens[i] >= '0' && tokens[i] <= '9')

{

StringBuffer sbuf = new StringBuffer();

// There may be more than one digits in number

while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')

sbuf.append(tokens[i++]);

values.push(Integer.parseInt(sbuf.toString()));

}

// Current token is an opening brace, push it to 'ops'

else if (tokens[i] == '(')

ops.push(tokens[i]);

// Closing brace encountered, solve entire brace

else if (tokens[i] == ')')

{

while (ops.peek() != '(')

values.push(applyOp(ops.pop(), values.pop(), values.pop()));

ops.pop();

}

// Current token is an operator.

else if (tokens[i] == '+' || tokens[i] == '-' ||

tokens[i] == '*' || tokens[i] == '/')

{

// While top of 'ops' has same or greater precedence to current

// token, which is an operator. Apply operator on top of 'ops'

// to top two elements in values stack

while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))

values.push(applyOp(ops.pop(), values.pop(), values.pop()));

// Push current token to 'ops'.

ops.push(tokens[i]);

}

}

// Entire expression has been parsed at this point, apply remaining

// ops to remaining values

while (!ops.empty())

values.push(applyOp(ops.pop(), values.pop(), values.pop()));

// Top of 'values' contains result, return it

return values.pop();

}

// Returns true if 'op2' has higher or same precedence as 'op1',

// otherwise returns false.

public static boolean hasPrecedence(char op1, char op2)

{

if (op2 == '(' || op2 == ')')

return false;

if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))

return false;

else

return true;

}

// A utility method to apply an operator 'op' on operands 'a'

// and 'b'. Return the result.

public static int applyOp(char op, int b, int a)

{

switch (op)

{

case '+':

return a + b;

case '-':

return a - b;

case '*':

return a * b;

case '/':

if (b == 0)

throw new

UnsupportedOperationException("Cannot divide by zero");

return a / b;

}

return 0;

}

// Driver method to test above methods

public static void main(String[] args) throws Exception

{

System.out.println(evaluate("10 + 2 * 6"));

System.out.println(evaluate("100 * 2 + 12"));

System.out.println(evaluate("100 * ( 2 + 12 )"));

System.out.println(evaluate("100 * ( 2 + 12 ) / 14"));

}

}