Using Java Coding!! 1. Extend the queue ADT to include the following operations:
ID: 3862682 • Letter: U
Question
Using Java Coding!!
1. Extend the queue ADT to include the following operations:
last that will return the rear element of the queue (which shall not be deleted from the queue)
length that will return the number of elements on the queue.
enqueueN that will enqueue an array of N elements on the queue
dequeueN that will dequeue and return an array of N elements from the queue
Write an implementation for each operation and compute their time complexity in Big-O notation (no justification is needed).
2. Extend the queue ADT to include an operation called searchqueue that searches for an item on the queue and returns its position. Write a program for the new function and compute its time complexity in Big-O notation (no justification is needed).
the Question is : Implement a program that can input an expression in postfix notation (see Exercise
C-6.19) and output its value.
C-6.19 Postfix notation is an unambiguousway of writing an arithmetic expressionwithout
parentheses. It is defined so that if “(exp1)op(exp2)” is a normal fully parenthesized
expression whose operation is op, the postfix version of this is “pexp1
pexp2 op”, where pexp1 is the postfix version of exp1 and pexp2 is the postfix version
of exp2. The postfix version of a single number or variable is just that number
or variable. So, for example, the postfix version of “((5+2) (83))/4” is “5
2 + 8 3 4 /”. Describe a nonrecursive way of evaluating an expression in
postfix notation.
Explanation / Answer
Program to evaluate value of a postfix expression:
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
// Stack type
struct Stack
{
int top;
unsigned capacity;
int* array;
};
// Stack Operations
struct Stack* createStack( unsigned capacity )
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
if (!stack) return NULL;
stack->top = -1;
stack->capacity = capacity;
stack->array = (int*) malloc(stack->capacity * sizeof(int));
if (!stack->array) return NULL;
return stack;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1 ;
}
char peek(struct Stack* stack)
{
return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--] ;
return '$';
}
void push(struct Stack* stack, char op)
{
stack->array[++stack->top] = op;
}
// The main function that returns value of a given postfix expression
int evaluatePostfix(char* exp)
{
// Create a stack of capacity equal to expression size
struct Stack* stack = createStack(strlen(exp));
int i;
// See if stack was created successfully
if (!stack) return -1;
// Scan all characters one by one
for (i = 0;exp[i];++i)
{
// If the scanned character is an operand (number here),
// push it to the stack.
if (isdigit(exp[i]))
push(stack, exp[i] - '0');
// If the scanned character is an operator, pop two
// elements from stack apply the operator
else
{
int val1 = pop(stack);
int val2 = pop(stack);
switch (exp[i])
{
case '+': push(stack, val2 + val1); break;
case '-': push(stack, val2 - val1); break;
case '*': push(stack, val2 * val1); break;
case '/': push(stack, val2/val1); break;
}
}
}
return pop(stack);
}
// Driver program to test above functions
int main()
{
char exp[] = "231*+9-";
printf ("Value of %s is %d", exp, evaluatePostfix(exp));
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.