Given stack have positive and negative integers, denoting different types of parentheses. The positive numbers xi denotes opening parentheses of type +x and negative number –x denotes closing parentheses of type xi. Open parentheses must be closed by the same type of parentheses. Open parentheses must be closed in the correct order, i.e., never close an open pair before its inner pair is closed (if it has an inner pair). Thus, [1,2,−2,−1]is balanced, while [1,2,−1,−2] is not balanced. You have to find out the length of the longest sub array that is balanced. Input: 5 1 -1 2 3 -2 Output: 2 Explanation The longest sub array that is balanced is (1,−1) (2,3,−2) is not balanced as (3) is not balanced.
Solution:
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
struct stack
{
int data[MAX],top;
}st;
void push(int t)
{
if(st.top == MAX-1)
{
printf("cannot
push --stack full");
return;
}
else
{
st.top++;
st.data[st.top]=t;
}
}
int pop()
{
int del;
if(st.top==-1)
{
//printf("cannot
delete as stack empty\n");
return;
}
del=st.data[st.top];
st.top--;
return del;
}
main()
{
int n,p,c=0,i;
st.top=-1;
printf("enter
a number enter 999 to exit");
while(n != 999 )
{
scanf("%d",&n);
if(n>0)
push(n);
else
if(n<0)
{
p=pop();
if(p+n
== 0)
c=c+2;
else
{
while(st.top>-1)
st.top--;
}
}
}
printf("length
of longest sub array=%d",c);
}
Output:
Python code of same q
ReplyDelete