public class MyStack<E> extends SingleLinkedList<E> implements StackInterface<E>

Question

public class MyStack<E> extends SingleLinkedList<E> implements StackInterface<E>{ ... insert code...}. Implement the MyStack to the interface 'StackInterface'. Use such a stack to support both the following tasks in one main method.

1. Check for balancing symbols in a cpp/cc file: (), {} and [].You can test your program with the following cases (reference answer: T, F, F):

( a + b * { c / [ d – e ] } ) * ( d –   [ e – f ] )

( a + b * { c / [ d – e } ] ) * ( d –   [ e – f ] )

( a + b * { c / [ d – e ] ] } ) * ( d –   [ e – f ] )

b. Given a given postfix expression, print out the result (the last double type number left in the stack). A sample is available here:

3 2 * 4 5 1 - / +

Explanation / Answer

a)

#include<stdio.h>
#include<stdlib.h>
#define bool int

/* structure of a stack node */
struct sNode
{
char data;
struct sNode *next;
};

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data);

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref);

/* Returns 1 if character1 and character2 are matching left
and right Parenthesis */
bool isMatchingPair(char character1, char character2)
{
if (character1 == '(' && character2 == ')')
return 1;
else if (character1 == '{' && character2 == '}')
return 1;
else if (character1 == '[' && character2 == ']')
return 1;
else
return 0;
}

/*Return 1 if expression has balanced Parenthesis */
bool areParenthesisBalanced(char exp[])
{
int i = 0;

/* Declare an empty character stack */
struct sNode *stack = NULL;

/* Traverse the given expression to check matching parenthesis */
while (exp[i])
{
/*If the exp[i] is a starting parenthesis then push it*/
if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
push(&stack, exp[i]);

/* If exp[i] is an ending parenthesis then pop from stack and
check if the popped parenthesis is a matching pair*/
if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
{

/*If we see an ending parenthesis without a pair then return false*/
if (stack == NULL)
return 0;

/* Pop the top element from stack, if it is not a pair
parenthesis of character then there is a mismatch.
This happens for expressions like {(}) */
else if ( !isMatchingPair(pop(&stack), exp[i]) )
return 0;
}
i++;
}
  
/* If there is something left in expression then there is a starting
parenthesis without a closing parenthesis */
if (stack == NULL)
return 1; /*balanced*/
else
return 0; /*not balanced*/
}

/* UTILITY FUNCTIONS */
/*driver program to test above functions*/
int main()
{
char exp[100];
printf(" enter the expression:");
gets(exp);
if (areParenthesisBalanced(exp))
printf(" Balanced ");
else
printf(" Not Balanced ");  
return 0;
}   

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
/* allocate node */
struct sNode* new_node =
(struct sNode*) malloc(sizeof(struct sNode));

if (new_node == NULL)
{
printf("Stack overflow n");
getchar();
exit(0);
}

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*top_ref);  

/* move the head to point to the new node */
(*top_ref) = new_node;
}

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
char res;
struct sNode *top;

/*If stack is empty then error */
if (*top_ref == NULL)
{
printf("Stack overflow n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}

b)

#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[] = "32*451-/+";
printf ("Value of %s is %d", exp, evaluatePostfix(exp));
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.