Abhi
BAN USERUse stack to solve it.
When ever an opening bracket encountered push it into stack and
when a closing bracket is encountered pop the top element from stack.
perform a check to match opening and corresponding closing bracket.
in the end there stack should be empty for a correct string
#include <stdio.h>
char* funCompressString(char *s);
void int_to_char(char *,int *,int);
int main()
{
char *mString="aaabbbrrccggtttttttttttttttttttsssssssssssss";
char *result;
printf("\nOriginal String - <%s>",mString);
result=fnCompressString(mString);
printf("\nCompressed String - <%s>\n",result);
}
char* fnCompressedString(char *s)
{
char *p=s,*q;
int i = 0, j=0;
q=(char *)malloc((strlen(s))+1);
while(*s != '\0')
{
if(*p==*s)
i++;
else
{
if(i==1)
{
q[j++]=*p;
p=s;
}
else
{
q[j++]=*p;
int_to_char(q,&j,i);
p=s;
i=1;
}
}
s++;
}
q[j++]=*p;
if(i>1)
int_to_char(q,&j,i);
q[j]='\0';
return q;
}
void int_to_char(char *ipString, int *base,int ipNum)
{
int a=ipNum,b;
int revNum=0;
if(ipNum <10)
{
ipString[(*base)++]=ipNum+'0';
}
else
{
while(a>0)
{
b=a%10;
revNum= revNum?(revNum*10+b):b;
a=a/10;
}
while(revNum>0)
{
ipString[(*base)++]=revNum%10+'0';
revNum=revNum/10;
}
}
}
Perform merge sort
- Abhi January 25, 2013