1. Show how a stack can be used to evaluate a postfix expression with the help of this example. 632-5*+1^7+

For evaluating a postfix expression, a stack is used to store operands. Whenever an operator is found, two top most operands are popped and operated on.

If we take the example
632-5*+1^7+

When the expression is scanned,
6,3 and 2 are pushed to the stack.
- is encountered.
3 and 2 are popped out.
3-2 is done and
the result 1 is pushed to stack
Next 5 is pushed to stack
* is encountered
5 and 1 are popped
5*1 = 5 is pushed back
+ encountered
5 nd 6 are popped out
6+5=11 is pushed back
1 is pushed to stack
^ is obtained
1 and 11 are popped
11^1 = 11 is pushed to stack
Next 7 is pushed to stack
Lastly + is encountered ,
7 and 11 are popped
11+7 =18 is pushed to stack.

18 is popped out and is our answer

Note
1) We use fgets instead of scanf because we have to use spaces as separator
2) We must compile the program with flag -lm for math library
gcc youfile.c -lm

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#define ERRCODE 12345
#define DIVBYZERO 23456
struct node
{
    double n1;
    struct node *next;
};
typedef struct node *NODEPTR;
NODEPTR createnode(double num)
{
    NODEPTR newnode = (NODEPTR) malloc(sizeof(struct node));
    newnode->n1 = num;
    newnode->next = NULL;
}

NODEPTR  push(double num,NODEPTR top)
{
   NODEPTR newnode = createnode(num);
   newnode->next = top;
   top = newnode;
   return top;
}

double pop(NODEPTR * top)
{
   if(top==NULL)
	return ERRCODE;
   NODEPTR temp = *top;
   *top =(*top)->next;
   double val = temp->n1;
   free(temp);
   return val;
}

int is_operator(char ch)
{
    switch(ch)
    {
	case '+':
	case '-':
	case '/':
	case '*':
	case '^':
		return 1;
        default : return 0;
    }
}
 
double evaluate(char *postfix)
{
     char ch;
     double ans,n1,n2;
     NODEPTR top = NULL;
     while(ch =*postfix++)
     {
        if(isdigit(ch))
        {
          double n = ch-48;
          top = push(n,top);
        }
        else if(is_operator(ch))
       {
           n1 = pop(&top);
           if(n1==ERRCODE)
              return ERRCODE;
           n2 = pop(&top);
           if(n2 ==ERRCODE)
              return ERRCODE;
          switch(ch)
          {
            case '+': ans = n1+n2; 
                    break;
            case '-': ans = n2 - n1;
  	  break;
            case '*': ans = n1*n2;
                 break;
           case '/': if(n1!=0)
                   ans = n2/n1;
                else
                   return DIVBYZERO;	 
                break;
          case '^':ans = pow(n2,n1);
	  break;
          }
          top = push(ans,top);
      }
    }
    ans = pop(&top);
    return ans;
}
    
   
int main()
{
   char postfix[30];
   double ans;
   printf("Enter postfix expression (leave space between values):");
   fgets(postfix,29,stdin);
   ans = evaluate(postfix);
   printf("The value of expression is %f",ans);
   return 0;
}

2. Convert the following expressions into prefix and postfix. A+B*C-D/E*H (A+B^C^D)*(E+F/D)

Infix Expression
A+B*C-D/E*H
(A+B^C^D)*(E+F/D)

Postfix expression
ABC*+DE/H*-
ABC^D^+EFD/+*

Prefix expression
+A -*BC */DEH
*+A ^^BCD +E/FD

3. What is stack data structure? Write push, pop, isEmpty and isFull functions for a stack using array implementation

Stack is a linear data structure where elements are added to only one end - top of stack and they can only be removed from top of stack.
Stack data structure is used for function calls by operating systems.

Stack should be used whenever you need to reverse the order of input.

Stack data structure has 3 functions - push, pop and isempty.

push adds an element at the top of the stack.
pop removes an element from top of stack.

Both these operations have constant complexity viz O(1).

A stack can be implemented using an array or a linked list.

For array implementation -
push function checks if the stack is full. If not, it adds a value at array[top] after incrementing top.

pop function checks if the stack is empty. If it is not empty, then the value at top of stack is returned and top is decremented.

We can send top and array as two separate parametes to all the above functions.

But for the sake of convenience, array and top are stored together in a structure in our code.

#include<stdio.h>
#define MAX 30
struct stack
{
    int arr[MAX];
    int top;
};
void push(struct stack *s, int val)
{
   if( is_full(s))
      printf("Stack overflow");
   else
   {
      (s->top)++;
      s->arr[s->top]=val;
   }
    
}
int is_empty(struct stack *s)
{
    return s->top==-1;
}
int is_full(struct stack *s)
{
    return s->top>=MAX;
}
int pop(struct stack *s)
{
    int val = -1;
    if(is_empty(s))
      printf("Stack empty");
    else
     {
        int t = s->arr[s->top];
        s->top--;
        val = t;
      }
    return val;
}
    
int main()
{
    struct stack s1;
    s1.top = -1;
    int option;
    while(1)
    {
       printf("Enter 1- push 2-pop 3 - exit:");
       scanf("%d",&option);
       if(option==3)
          break;
       else if(option==1)
      {
          int num;
          printf("Enter value to push:");
          scanf("%d",&num);
          push(&s1,num);
        }
        else if(option==2)
       {
           int num;
           num = pop(&s1);
           if(num!=-1)
              printf("value popped is %d\n",num); 
        }   
    }
    return 0;
}

4. Write an algorithm to convert an infix expression into postfix. And also write code for this.

This is how we can solve this question

Create an empty stack called opstack for keeping operators. Create an empty array for output.

Scan the token list from left to right.
If the token is an operand, append it to the end of the output string.
If the token is a left parenthesis, push it on the opstack.
If the token is a right parenthesis,
pop the opstack until the corresponding left parenthesis is removed.
Append each operator popped out to the end of the output string.
If the token is an operator,
remove any operators in stack with >=precedence and append to the output string.
push token on the opstack.

When the input expression has been completely processed as mentioned above,
check the opstack.
Remove any operators still on the stack and
append to the end of the output string.

The stack library is not included in the solution. So while compiling include stack implementation file. Some thing like this

gcc infixtopostfix.c stacklib.c

#include<stdio.h>
#include"stack.h"
int is_operator(char ch)
{
   switch(ch)
   {
      case '+':
      case '-':
      case '/':
      case '*':
      case '%':
      case '^':
                return 1;
      default : return 0;
   }
}
int priority(char ch)
{
 switch(ch)
   {
      case '+':
      case '-':return 1;
      case '/':
      case '*':
      case '%':return 2;
      case '^':return 3;
                 
      default : return 0;
   }
}

void convert(char *input, char *output)
{
   struct stack s1;
   s1.top = -1;
   while(*input)
   {
   char ch = *input++;
   char ch2;
   if(ch=='(')
      push(&s1,ch);
   else if(ch==')')
   {
       while(!is_empty(&s1)  && ( (ch=pop(&s1))!='('))
          *output++ = ch;
    }
    else 
    if(is_operator(ch))
    {
       while(!is_empty(&s1)  &&  priority(peek(&s1))>=priority(ch))
          *output++ = pop(&s1);
       push(&s1,ch);
     }
     else
       *output++ = ch;
    }
    while(!is_empty(&s1))
       *output++ = pop(&s1);
    *output = 0;
}               
int main()
{
   char infix[40],postfix[40];
   printf("Enter infix expression:");
   scanf("%s",infix);
   convert(infix,postfix);
   printf("the postfix expression is %s\n",postfix);
   return 0;
}
/*stack implementation not shown */

5. Explain how a stack can be implemented using a linked list. Write C functions for push, pop, isempty for this method.

Stack abstract data type has 3 functions - push, pop and isempty.

push adds an element at the top of the stack.
pop removes an element from top of stack.

To implement stack using linked list, push should add an element to the begining of linked list. and pop should remove the element from begining of linked list.

Isempty should check if the list is empty i.e. top is NULL.

All three operations take constant time - O(1)

#include<stdio.h>  
#include<stdlib.h>
#define ERROR -1000
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
   temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 NODEPTR push(NODEPTR top,int n)
 { 
     NODEPTR newnode = create_node(n);
     newnode->next = top;
     top = newnode;
     return top;
}
int isempty(NODEPTR top)
{
   return top==NULL;
}
int pop(NODEPTR *topPtr)
{
   if(isempty(*topPtr))
    return ERROR;
   int num = (*topPtr)->n;
   NODEPTR temp = *topPtr;
   *topPtr = (*topPtr)->next;
   free(temp);
   return num;
}

 int main()  
 {  
     NODEPTR top = NULL;
     NODEPTR nd; 
     while(1)
     {  
       int option,value; 
       printf("Enter 1- push 2- pop 3 - exit"); 
       scanf("%d",&option);
       if(option==3)
          break;
       switch(option)
       {
          case 1:  printf("new value to push=");  
            scanf("%d",&value);   
            top = push(top,value);
            break;
         case 2:  value = pop(&top);
           if(value==ERROR)
             printf("Stack empty\n");
           else
             printf("Value popped is %d\n",value);
        break; 
     }  
    }     
 }

6. Design a method to create two stacks in a single array so that either stack overflows until the memory is completely filled and a stack is never moved to another memory location. Write push1, push2, pop1, pop2, display1 and display2 functions for this in C.

We can implement first stack at the begining of array and second stack at the end of array. So that the two stacks grow in opposite directions.

Stacks are full only when the top values are next to each other and there is no place to grow.

As the second stack is growing in reverse direction, push() for second stack will decrement the top and pop() will increment the top.

#include<stdio.h>
#define MAX 5
struct two_stacks
{
    int arr[MAX];
    int top1,top2;
};
void push1(struct two_stacks *s, int val)
{
   if( is_full(s))
      printf("Stack overflow");
   else
   {
      (s->top1)++;
      s->arr[s->top1]=val;
   }    
}

void push2(struct two_stacks *s, int val)
{
   if( is_full(s))
      printf("Stack overflow");
   else
   {
      (s->top2)--;
      s->arr[s->top2]=val;
   }    
}
int is_empty1(struct two_stacks *s)
{
    return s->top1==-1;
}
 
int pop1(struct two_stacks *s)
{
    int val = -1;
    if(is_empty1(s))
      printf("Stack empty");
    else
     {
        int t = s->arr[s->top1];
        s->top1--;
        val = t;
      }
    return val;
}
  
int pop2(struct two_stacks *s)
{
    int val = -1;
    if(is_empty2(s))
      printf("Stack empty");
    else
     {
        int t = s->arr[s->top2];
        s->top2++;
        val = t;
      }
    return val;
}  
int is_empty2(struct two_stacks *s)
{
    return s->top2==MAX;
}
int is_full(struct two_stacks *s)
{
    return (s->top2-s->top1==1)?1:0;    
}
int main()
{
    struct two_stacks s;
    s.top1 = -1;
    s.top2 = MAX;    
    int option;
    while(1)
    {
      printf("Enter 1- push to s1, 2-pop from s1, 3- push to s2, 4-pop from s2,  5 - exit:");
      scanf("%d",&option);
        
      if(option==5)
          break;
      else if(option==1||option==3)
     {
         int num;
         printf("Enter value to push:");
         scanf("%d",&num);
        if(option==1) 
           push1(&s,num);
        else
           push2(&s,num);
       }
      else if(option==2||option==4)
     {
         int num;
         if(option==2)
           num = pop1(&s);
         else
           num = pop2(&s);
           if(num!=-1)
              printf("value popped is %d\n",num);	
        }             
    }
    return 0;
}

7. Write a function to convert a given postfix expression to infix expression.

To convert a postfix expression to infix expression, you should use a operand stack.

You should extract characters -
if operand, push it to stack.
If it is an operator,
pop 2 values from stack,
form an expression with this operator and the operands
push the result back to stack.
Repeat this until all the characters are extracted.

Finally pop out the content of stack - which is answer

Remember that postfix expression does not have brackets. That is why while forming expressions you should enclose it in paranthesis

#include<stdio.h>
#include<string.h>
#include<stdlib.h> 
struct node
{
    char str[30];
    struct node *next;
};
struct node *createnode(char *str)
{
    struct node *newnode = (struct node*) malloc(sizeof(struct node));
    strcpy(newnode->str,str);
    newnode->next = NULL;
}

struct node * push(char *str,struct node *top)
{
   struct node *newnode = createnode(str);
   newnode->next = top;
    top = newnode;
   return top;
}

char * pop(struct node ** top)
{
   static char str[30];
   if(*top==NULL)
    return NULL;
   struct node * temp = *top;
   *top =(*top)->next;
   strcpy(str,temp->str);
   
   free(temp);
   return str;
}

int is_operator(char ch)
{
    switch(ch)
    {
    case '+':
    case '-':
    case '/':
    case '*':
    case '^':
    return 1;
        default : return 0;
    }
}
 
char *concat(char *s1,char *s2,char ch)
{
   char *result = (char*)malloc(60);
   int i=1;
   result[0] = '(';
   while(*s1)
     result[i++]=*s1++;
   result[i++]=ch;
   while(*s2)
     result[i++]=*s2++;
   result[i++]=')';/*enclose in parantheses*/
   result[i]=0;
   return result;
}
int convert(char *postfix,char *infix)
{
     char ch;
     char oper1,oper2,opernew;
     char *expr1=(char*)malloc(30);
     char *expr2=(char*)malloc(30);
     char *expr3 = (char*)malloc(60);
     struct node *top = NULL;
     int iserr = 0;
     while(ch =*postfix++)
     {
      if(isdigit(ch) ||isalpha(ch))
      {
         char  str[] = {ch,0};
         top = push(str,top);
      }
      else if(is_operator(ch))
     {
        char* str = pop(&top);
        if(str==NULL)
        {
           printf("pop error");
           iserr=1;
           break;
        }        
        strcpy(expr1, str);         
        str = pop(&top);        
        if(str==NULL)
        {
         iserr = 1;
         printf("Error");
         break;
        }
        strcpy(expr2,str);
       strcpy(expr3, concat(expr2,expr1,ch));    
       top = push(expr3,top);
      }
    } 
    if(!iserr)
        strcpy(infix,pop(&top));
    else
        return 0;
}
    
   
int main()
{
   char postfix[30];char infix[30];
   double ans;
   printf("Enter postfix expression :");
   scanf("%s",postfix); 
   if(convert(postfix,infix))
   printf("The expression in infix is %s",infix);
   return 0;
}

8. Write a function to check if a given expression is having balanced brackets.

In any arithmetic expressions or program pieces, the brackets must match in type and order. That is - each opening bracket must have a corresponding closing bracket. And two pairs of different brackets can not interesect each other.

e.g
(a+[b*c]*d) - valid
(a+[b*c)*d] - invalid
(a+b+c - invalid
a+b)+c ( - invalid

To test whether a string has matching parantheses, we need to use a brackets stack.
1) scan each character
2) if the character is an opening bracket, push it to stack
3) If the character is a closing bracket, pop a bracket
if the popped opening bracket does not match the closing bracket return false
4) repeat steps 2 to 3 for each character
5) At the end of expression if stack is not empty return false
6) Else return true

#include<stdio.h>
#include<string.h>
#include<stdlib.h> 
#define ERRORCHAR 65
struct node
{
    char ch;
    struct node *next;
};
struct node *createnode(char ch)
{
    struct node *newnode = (struct node*) malloc(sizeof(struct node));
    newnode->ch = ch;
    newnode->next = NULL;
    return newnode;
}

int is_empty(struct node *top)
{
    return top==NULL;
}
struct node * push(char ch,struct node *top)
{
   struct node *newnode = createnode(ch);
   newnode->next = top;
   top = newnode;
   return top;
}

char pop(struct node ** top)
{
   char ch;
   if(*top==NULL)
	return ERRORCHAR;
   struct node * temp = *top;
   *top =(*top)->next;
   ch = temp->ch;
   
   free(temp);
   return ch;
}

int is_opening_bracket(char ch)
{
    switch(ch)
    {
        case '(':
        case '[':
        case '{':
	   return 1;
        default : return 0;
    }
}

int is_closing_bracket(char ch)
{
    switch(ch)
    {
        case ')':
        case ']':
        case '}': 
	    return 1;
        default : return 0;
    }
} 
 
int is_matching_bracket(struct node **top,char ch)
{
    char ch2 = pop(top);
    if(ch2!=ERRORCHAR)
    {
        if(ch2=='(' && ch==')' )
           return 1;
        if(ch2=='[' && ch==']' )
           return 1;
       if(ch2=='{' && ch=='}' )
           return 1;
     }
     return 0; 
} 
int is_balanced(char *expression)
{
     char ch;
      
     struct node *top = NULL;
     while(ch =*expression++)
     {
        if(is_opening_bracket(ch))
        {
            top = push(ch,top);
        }
        else if(is_closing_bracket(ch))
        {
            if(!is_matching_bracket(&top,ch))
            {
               return 0;           
             }
        }
     }
     return is_empty(top);
}    
   
int main()
{
   char expression[50]; 
   printf("Enter an expression :");
   scanf("%s",expression); 
   if(is_balanced(expression))
   {
        printf("The expression has balanced brackets");
   }
   else
   {
        printf("The expression has unbalanced brackets");
   }
   return 0;
}

9. Given two integer sequences, one of which is the push sequence of a stack, please check whether the other sequence is a corresponding pop sequence or not.

We know that stack is a last in first out (LIFO) data structure. Elements pushed first will pop out last. So basically a stack reverses input sequence.

So in this program we need not use a stack at all. We need to check if second sequence is reverse list of first sequence.

#include<stdio.h>
void read_array(int *arr,int n)
{
   int i;
   printf("Enter the elements of the array:");
   for (i=0;i<n;i++)
     scanf("%d",&arr[i]);
}
void write_array(int *arr,int n)
{
   int i;
   printf("The array is ");
   for (i=0;i<n;i++)
     printf("%d  ",arr[i]);
}
int is_pop_sequence(int *arr1,int *arr2,int n)
{
    int i,j;
    for(i=0,j=n-1;i<n;i++,j--)
      if(arr1[i]!=arr2[j])
         return 0;
    return 1;
}
int main()
{
    int arr1[20], arr2[20];
    int n;
    printf("Enter the length of sequence:");
    scanf("%d",&n);
    read_array(arr1,n);
    read_array(arr2,n);
    if(is_pop_sequence(arr1,arr2,n))
       printf("These two correspond to push and pop sequences");
    else
       printf("These are not push and pop sequences of same stack");

}

10. Write a recursive function to reverse a stack .

 #include<stdio.h>  
#include<stdlib.h>
#define ERROR -1000
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 void push(NODEPTR* topptr,int n)
 { 
     NODEPTR newnode = create_node(n);
     newnode->next = *topptr;
     *topptr = newnode; 
}
int isempty(NODEPTR top)
{
   return top==NULL;
}
int pop(NODEPTR *topPtr)
{
   if(isempty(*topPtr))
       return ERROR;
   int num = (*topPtr)->n;
   NODEPTR temp = *topPtr;
   *topPtr = (*topPtr)->next;
   free(temp);
   return num;
}

void bottom_insert(NODEPTR *topptr,int n)
{
  if(isempty(*topptr))
     push(topptr,n);
  else
    {
    int a = pop(topptr);
    bottom_insert(topptr,n);
    push(topptr,a);
    }
}

void reverse(NODEPTR *topptr)
{
  if(*topptr!=NULL)
  {
    int n= pop(topptr);
    reverse(topptr);
    bottom_insert(topptr,n);
  }

}
 int main()  
 {  
     NODEPTR top = NULL;
     NODEPTR nd;

     while(1)
     {  
       int option,value; 
       printf("Enter 1- push 2- pop 3 - reverse stack 4 - exit"); 
       scanf("%d",&option);
       if(option==4)
          break; 
       switch(option)
       {
           case 1:  printf("new value to push=");  
              scanf("%d",&value);  
              push(&top,value);
              break;
           case 2:  value = pop(&top);
             if(value==ERROR)
                 printf("Stack empty\n");
             else
                 printf("Value popped is %d\n",value);
             break; 
          case 3:  reverse(&top);
             break;
        }  
    }     
 }

11. Write a function to print next greater element for all elements in an array. If there is no NGE , it must print -1 for that element

Next greater element problem involves finding first element which appears after given element and is greater than given element. If there are no such elements, then program should give -1 for that value.
e.g.
If array is
30 88 12 96 45 3 12 10

Output should be

Next greater element for 30 =88
Next greater element for 12 =96
Next greater element for 88 =96
Next greater element for 3 =12
Next greater element for 10 is -1
Next greater element for 12 is -1
Next greater element for 45 is -1
Next greater element for 96 is -1

To write an efficient code, instead of writing O(n2) code, we can use this algorithm.

We traverse the array once.
1. If the stack is empty or the current element is smaller than top element of the stack, then push the current element on the stack.
2. If the current element is greater than top element of the stack, then this is the next greater element of the top element. Keep poping elements from the stack till a larger element than the current element is found on the stack or till the stack becomes empty. Push the current element on the stack.
3. Repeat steps 1 and 2 till the end of array is reached.
4. Finally pop remaining elements from the stack and print -1 for them.

#include<stdio.h>
#include"stackint.h"
void read_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       scanf("%d",&arr[i]);
     }
}
void print_array(int *arr,int sz)
{
     int i;
     for(i  =0;i<sz;i++)
     {
       printf("arr[%d]=",i);
       printf("%d   ",arr[i]);
     }
     printf("\n");
}
void next_greater_elements(int *arr,int n)
{
     STACK s1;
     int i;
     s1.top=-1;
     push(&s1,arr[0]); 
     for(i=1;i<n;i++)
     {
        while (!is_empty(&s1) && peek(&s1) < arr[i]) 
	{
                 printf("Next greater element for %d =%d\n" ,
	 	             + pop(&s1), arr[i]);
                }
 	push(&s1,arr[i]);  
     }
     while(!is_empty(&s1))
        printf("Next greater element for %d is -1\n",pop(&s1));
}
int main()
{
    int arr[50];
    int sz; 
    printf("Enter the size of array:"); 
    scanf("%d",&sz);
    read_array(arr,sz);
    print_array(arr,sz);
   
    next_greater_elements(arr,sz);
    return 0;
}

12. Implement a stack with min() function which returns the minimum value of a stack. All of push(), pop() and min() function must have time complexity of O(1)

This can be done with the help of auxilliary stack - let us call it minstack.

Whenever an element is pushed, if it is lesser than minimum, it is also pushed to minstack.

If not, the existing minimum is pushed again into minstack.

Whenever an element is popped, an element is also popped from minstack.

min() function will be just peeking the minstack to get minimum of stack

Hence all operations use time complexity of O(1)

  #include<stdio.h>  
#include<stdlib.h>
#define ERROR -1000
 struct node  
 {  
   int value;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->value= value;  
   return temp;  
 } 
 NODEPTR push(NODEPTR top,int val)
 { 
     NODEPTR newnode = create_node(val);
     newnode->next = top;
     top = newnode;
     return top;
}
int isempty(NODEPTR top)
{
   return top==NULL;
}
int pop(NODEPTR *topPtr)
{
   if(isempty(*topPtr))
       return ERROR;
   int num = (*topPtr)->value;
   NODEPTR temp = *topPtr;
   *topPtr = (*topPtr)->next;
   free(temp);
   return num;
}
int peek(NODEPTR nd)
{
   return nd->value;
}

void push1(NODEPTR*topptr,NODEPTR* mintopptr,int val)
{
     int minval =val;
     if(*mintopptr!=NULL)
        {
           int temp = peek(*mintopptr);
           if (temp<minval)
               minval = temp;
        }
     *topptr = push(*topptr,val);
     *mintopptr = push(*mintopptr,minval);
 }

 int pop1(NODEPTR* topptr,NODEPTR *mintopptr)
 {
   if(!isempty(*topptr))
   {
    pop(mintopptr);
    return pop(topptr);
   }else
       return ERROR;
 }
      
int findmin(NODEPTR mintop)
{
   if(mintop==NULL)
      return -1;
   return mintop->value;
}   
 


 int main()  
 {  
     NODEPTR top = NULL;
     NODEPTR nd;
     NODEPTR mintop=NULL;

     while(1)
     {  
       int option,value; 
       printf("Enter 1- push 2- pop 3 - exit 4- find minimum"); 
       scanf("%d",&option);
       if(option==3)
          break;
       switch(option)
       {
           case 1:  printf("new value to push=");  
       		    scanf("%d",&value);   
                    push1(&top,&mintop,value);
                    break;
           case 2:  value = pop1(&top,&mintop);
                    if(value==ERROR)
                         printf("Stack empty\n");
                    else
			 printf("Value popped is %d\n",value);
                    break; 
           case 4:  value=findmin(mintop);
                    if(value==-1)
                        printf("Stack empty\n");
                    else
                    printf("Minimum of stack is %d\n",value);
             
                    break;
        }  
    }     
 }

13. Write a program to reverse a string using stack.

To reverse a string you have to push all the characters of string to stack. Then pop these and copy them back to string.
1) push a character to stack
2) move to next character
3) repeat step 1 and 2 until end of string
4) pop a character from stack
5) save this character in string and increment index
6) repeat steps 4 and 5 as long as stack is not empty

The program uses stack library functions which are not shown.

void reverseString(char *str)
{
    struct stack s;
    s.top = -1;
    char ch;
    char *temp = str;
    while(ch=*str++)/*till '\0'*/
    {
       push(&s,ch);
    }
    str = temp;/*go to beg address*/
    while(!is_empty(&s))
      *str++ = pop(&s);      
}
int main()
{
    char str[50];
    printf("Enter a string");
    fgets(str,49,stdin);
    reverseString(str);
    printf("The reversed string is %s\n",str);
    return 0;
}

14. With the help of a stack, determine whether a given string is a palindrome.

A palindrome is a string which reads same forwards and backwards.

To check if the string is a palindrome, it can be pushed to stack. Next all the characters can be popped and compared with characters of original string. If they do not match, the string is not a palindrome.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 70
struct stack
{
    int arr[MAX];
    int top;
};
char pop(struct stack *s);
void push(struct stack *s, char val);
int is_palindrome(char *str)
{
     char *str2=str;
     struct stack s;
     s.top = -1;

     while(*str)
     {
        char ch = *str++;
        push(&s,ch);
     }
     while(*str2 && !is_empty(s))
     {
         char ch = pop(&s);
         if( *str2 !=ch)             
             return 0;
         str2++;
      }
      return 1;
}   
int is_full(struct stack *s)
{
    return s->top>=MAX;
}
void push(struct stack *s, char val)
{
   if( is_full(s))
      printf("Stack overflow");
   else
   {
	(s->top)++;
	s->arr[s->top]=val;
   }    
}
int is_empty(struct stack s)
{
    return s.top==-1;
}

char pop(struct stack *s)
{
    int val = -1;
    if(is_empty(*s))
      printf("Stack empty");
    else
     {
	int t = s->arr[s->top];
        s->top--;
        val = t;
      }
    return val;
} 

int main()
{
    char string[MAX];
    printf("Enter the string:");
    fgets(string,MAX-1,stdin);
    int l = strlen(string);/*fgets adds a new line char*/
    string[l-1]='\0';
    if(is_palindrome(string))
      printf("%s is a palindrome\n",string);
    else
      printf("%s is not a palindrome\n",string);
    return 0;
}

Stack Questions