Can anyone help solve those question in C++. Actually those question is base on
ID: 3773816 • Letter: C
Question
Can anyone help solve those question in C++. Actually those question is base on data structure.
1.Write a program that reads in a sequence of characters, and determines whether its parentheses, brakets, and braces are balancedand properly nested.
2.Write a program that uses two queues to implements a stack.
3.Both the stack and queue discussed in the class have capacity limit. Modify both ADTs to include an additional operation expand2() which is to expand the stack or queue into twice the current size. Test your new classes.
4. A double-ended queue is a generalization of queue in which elements can be added or deleted from both front and rear ends. Write a template class to implement the double-ended queue ADT with at least the following operations: constructor, destructor, IsEmpty, IsFull, AddFront, AddRear, DeleteFront, DeleteRear, CheckFront, CheckRear, Reverse.
Explanation / Answer
Answer 1 :
#include<stdio.h>
#include<stdlib.h>
#define bool int
struct sNode
{
char data;
struct sNode *next;
};
void push(struct sNode** top_ref, int new_data);
int pop(struct sNode** top_ref);
bool isPairMatch(char char1, char char2)
{
if (char1 == '(' && char1 == ')')
return 1;
else if (char1 == '{' && char1 == '}')
return 1;
else if (char1 == '[' && char1 == ']')
return 1;
else
return 0;
}
bool isBalanced(char exp[])
{
int i = 0;
struct sNode *stack = NULL;
while (exp[i])
{
if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
push(&stack, exp[i]);
if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
{
if (stack == NULL)
return 0;
else if ( !isPairMatch(pop(&stack), exp[i]) )
return 0;
}
i++;
}
if (stack == NULL)
return 1;
else
return 0;
}
int main()
{
char exp[100] = "{()}[]";
if (isBalanced(exp))
printf(" input character sequence is Balanced ");
else
printf(" input character sequence is not Balanced ");
return 0;
}
void push(struct sNode** top_ref, int new_data)
{
struct sNode* new_node =
(struct sNode*) malloc(sizeof(struct sNode));
if (new_node == NULL)
{
printf("Stack overflow ");
getchar();
exit(0);
}
new_node->data = new_data;
new_node->next = (*top_ref);
(*top_ref) = new_node;
}
int pop(struct sNode** top_ref)
{
char res;
struct sNode *top;
if (*top_ref == NULL)
{
printf("Stack overflow ");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}
Answer 2 :
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
int info;
struct node *next;
}node;
// structure for queue
typedef struct queue
{
struct node *front,*rear;
}queue;
// function for creating new node
node *new_node(int data)
{
node *ptr=(node *)malloc(sizeof(node));
ptr->info=data;
ptr->next=NULL;
return ptr;
}
// function to initialize queue
queue* create_queue()
{
queue* q =(queue *)malloc(sizeof(queue));
q->front=q->rear=NULL;
return q;
}
// structure for stack
typedef struct stack
{
struct queue *queue1;
struct queue *queue2;
}stack;
// function for initializing stack
stack* create_stack()
{
stack *s=(stack *)malloc(sizeof(stack));
s->queue1=create_queue();
s->queue2=create_queue();
return s;
}
// function for enqueue
void enqueue(queue *q,int data)
{
node *temp=new_node(data);
if(q->rear==NULL)
{
q->front=q->rear=temp;
return;
}
q->rear->next=temp;
q->rear=temp;
}
// function for dequeue
int dequeue(queue *q)
{
if(q->front==NULL)
return 0;
node* temp=q->front;
q->front=q->front->next;
if(q->front==NULL)
q->rear=NULL;
return temp->info;
}
// function for pushing elements
void push(stack *s,int x)
{
enqueue(s->queue1,x);
}
// function to pop elements
int pop(stack *s)
{
int x;
if(s->queue1==NULL && s->queue2==NULL)
return 0;
while(s->queue1->front->next!=NULL)
{
x=dequeue(s->queue1);
enqueue(s->queue2,x);
}
int m = s->queue1->front->info;
queue* temp= s->queue1;
s->queue1 = s->queue2;
s->queue2 = temp;
return m;
}
int main()
{
stack *s=create_stack();
push(s,1);
push(s,2);
push(s,3);
push(s,5);
push(s,6);
push(s,8);
printf(" popped element= %d",pop(s));
push(s,9);
push(s,10);
printf(" popped element= %d",pop(s));
printf(" popped element= %d",pop(s));
getch();
return 0;
}