Implement MyArrayStack (constructor, push, pop, peek and isEmpty), MyLinkedStack
ID: 3725673 • Letter: I
Question
Implement MyArrayStack (constructor, push, pop, peek and isEmpty), MyLinkedStack (constructor, push, pop, peek and isEmpty) and MyLinkedQueue (constructor, offer, poll, peek and isEmpty), and write the following two program to test them.
For stack testing, write a program to check if a string has matching parenthesis such as “(())”, but not “)(“.
For stack testing, use it to “Evaluating Expressions”
Phase 1: Scanning the expression
The program scans the expression from left to right to extract operands, operators, and the parentheses.
1.1. If the extracted item is an operand, push it to operandStack.
1.2. If the extracted item is a + or - operator, process all the operators at the top of operatorStack and push the extracted operator to operatorStack.
1.3. If the extracted item is a * or / operator, process the * or / operators at the top of operatorStack and push the extracted operator to operatorStack.
1.4. If the extracted item is a ( symbol, push it to operatorStack.
1.5. If the extracted item is a ) symbol, repeatedly process the operators from the top of operatorStack until seeing the ( symbol on the stack.
Phase 2: Clearing the stack
Repeatedly process the operators from the top of operatorStack until operatorStack is empty.
Bonus: support for exponent ^ and use HashMap for counting keyword occurrence in a Java program.
Explanation / Answer
Hi I have implemented MyArrayStack.Please repost for other class implementation. Question is long.
/**
* 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"));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.