Skip to main content

AnaGram-Data Structure


An anagram is a rearrangement of the letters in either a word or a phrase (using each letter exactly once in the word or phrase created). Ideally the anagram created relates in some (perhaps humorous) way to the original word or phrase. Such anagrams are described as cognate. The best anagrams are grammatically correct and use techniques such as abbreviating and to 'n' only minimally.

I have Developed an anagram program in VS 2010 using vc++, this program read one input string at a time and produce all anagrams of that string. Input string should include all unique chars not repeated one like "caat" . I have Developed this program using stack and queue data structure. 

This Program will give you basic idea of anagram, you may modify it as per your requirement.

#include
#include
#include
#include

#define MAX 10

using namespace std;

typedef struct
{
char arr[20];
int front;
int rear;
int count;

}Queue;
typedef struct 
{
int top;
char arr[100];
}Stack;
void createQueue(Queue *Q)
{
Q->front=-1;
Q->rear=-1;
Q->count=0;
}
void EnQueue(Queue *Q,char c)
{
if(Q->front==-1 && Q->rear==-1)
{
Q->arr[0]=c;
Q->rear=0;
Q->front=0;
Q->count++;
return;
}
Q->rear=(Q->rear+1)%MAX;
Q->arr[Q->rear]=c;
Q->count++;
}

char DeQueue(Queue *Q)
{
if(Q->count<=0)
{
return '0';
}

char c=Q->arr[Q->front];
Q->front=(Q->front+1)%MAX;
Q->count--;
return c;
}

int isEmpty(Queue *Q)
{
if(Q->count<=0)
return -1;
return 0;
}
char peekQueue(Queue *Q)
{
if(Q->count>0)
return Q->arr[Q->front];
else
return '0';
}
void createStack(Stack *stack)
{
stack->top=-1;
}
void push(Stack *stack,char ele)
{
if(stack->top==-1)
{
stack->arr[0]=ele;
stack->top=0;
}
else
stack->arr[++(stack->top)]=ele;
}
char pop(Stack *stack)
{
if(stack->top==-1) return -1;

return stack->arr[(stack->top)--];

}
float peek(Stack *stack)
{
if(stack->top==-1) return -1;

return stack->arr[stack->top];
}
int isEmpty(Stack *stack)
{
if(stack->top==-1)
return -1;
else
return 0;
}



void main()
{
ifstream ifile;
ifile.open("c:\\prog.txt", ios::in);
//char *input= new char;
string input;

if(ifile)
{
while(!ifile.eof())
{
ifile>>input;
}
}

Stack S;
createStack(&S);

Queue Q;
createQueue(&Q);

int fact=1;
for(int f=input.length();f>0;f--)
{
fact*=f;
}

char pivot;
char c1;
char temp;
int flag=0;
for(int x=0;x
{
for(int i=0;i
{//push all input in stack
push(&S,input[i]);
}

c1=pop(&S);
do
{
EnQueue(&Q,c1);
temp=c1;
if(isEmpty(&S))
{
flag=1;
break;
}
else
c1=pop(&S);
}while(c1>temp);

//if(!isEmpty(&S))
if(flag!=1)
{
pivot=c1;

//step 2:
temp=DeQueue(&Q);
while(temp
{
EnQueue(&Q,temp);
if(isEmpty(&Q))
break;
temp=DeQueue(&Q);
}
push(&S,temp);
EnQueue(&Q,pivot);

//step 3
temp=DeQueue(&Q);
while(temp>pivot)
{
EnQueue(&Q,temp);
if(isEmpty(&Q))
break;
temp=DeQueue(&Q);
}

push(&S,temp);

}//flag

//step 4
while(!isEmpty(&Q))
{
push(&S,DeQueue(&Q));
}

int j=input.length();
while(!isEmpty(&S))
{
input[--j]=pop(&S);
}

cout<<"\n"<
flag=0;

}//for

}


Labels:

Comments

Post a Comment

Popular posts from this blog

Font identifier and Unicode converter for Hindi

Font identifier and Unicode converter for Hindi Fonts are used to represent text in document. Fonts are mainly two kind non-Unicode and Unicode fonts. Complex scripts like Hindi and other Asian languages well represented in Unicode fonts. There are some other ways to write these languages for e.g we can use ASCII/ISCII codes to represent different characters of Hindi, but there are large numbers of characters in Hindi script as compared to English. Therefore, we always need multiple ASCII/ISCII encoded characters combination to represent a single character of Hindi Script. One major problem in these ASCII encoding based fonts is that we cannot easily transfer text from one system to another. The system must have these text fonts. There is hundreds of ASCII/ISCII encoding based fonts which are used to write Hindi text. New software systems are based on Unicode fonts.                   ...
Post a Comment
Read more

Binary Search Tree in ASP .Net

Binary Search Tree in ASP .Net To create Binary Search Tree(BST) in Asp.net application   first you need to create a Node class. Something like following : class Node {     public String data;     public int freq = 0;     public Node left, right;     public Node()     { }     public Node( String data)     {         this .data = data;         left = null ;         right = null ;     } } Next You need to create a class including different functions.Like class BinaryTreeImp {     Node root;     String outputfreq = "" ;     static int count = 0;     public BinaryTreeImp()     {      ...
Post a Comment
Read more

Hindi to Punjabi Machine Translation System

The Hindi To Punjabi Machine Translation System has been developed using Direct/Rule based Approach by Dr.Vishal Goyal and Dr. G.S Lehal. Various large size Lexicon resources  have been used to map Source and Target language words.  In general, if the two languages are structurally similar, in particular as regards lexical correspondences, morphology and word order, the case for abstract syntactic analysis seems less convincing. Since the present research work deals with a pair of closely related language, so the direct translation system is the obvious choice. The overall system architecture shown below, is adopted for Hindi to Punjabi Machine Translation System. The system is divided into three stages: Preprocessing, Translation Engine, and Post Processing stage. Following is the description of various steps of this architecture.  PreProcessing   The pre-processing stage is a collection of operations that are applied on input  data to make it pr...
1 comment
Read more