Program # 1
To Convert Infix Expression to Prefix and Postfix Form Using Stack
#include
#include
#include
#include
#define max 50
Char Output [max];
Char stack [max];
CHAR INPUT [MAX];
Char * s, * t; / * Pointers to Input and output strings * /
Char ch; / * choice * /
INT top; / * stack top * /
Int L; / * Length of infix string * /
/ * Function protoypes * /
Void Initialize (Void);
Void setExpression (char *);
Char popfromstack;
Void PushonStack (char);
INT Priority (char);
Void ConvertTopRefix (Void);
Void ConvertTopostfix (Void);
void main ()
{
CLRSCR ();
INITIALIZE ();
Printf ("/ NENTER AN Expression in Infix Form:");
Gets (Input);
Printf ("/ nspecify output expression type, 1) prefix 2) postfix");
CH = GetCh ();
STEXPRESSION (INPUT);
IF (CH == '1') / * infix-> prefix * /
{
Strrev (s);
CONVERTTTTOPREFIX ();
Strrev (OUTPUT);
Printf ("/ NThe Prefix Expression IS:");
}
Else
{
Converttopostfix ();
Printf ("/ NTHE Postfix Expression IS:");
}
PUTS (OUTPUT);
Getch ();
}
Void Initialize (void)
{
TOP = -1; / * make stack empty * /
STRCPY (OUTPUT, "");
STRCPY (stack, ");
L = 0;
}
Void setExpression (Char * STR)
{
s = STR;
l = strlen (s);
* (OUTPUT L) = '/ 0';
T = OUTPUT;
}
/ * Adds Operator to the stack * /
Void PushonStack (Char C)
{
IF (TOP == max - 1)
Printf ("/ nstack is full./N");
Else
{
TOP ;
Stack [TOP] = C;
}
}
/ * POPS an Operator from the stack * /
Char popfromstack (void)
{
IF (TOP == -1) / * Stack is Empty * /
Return -1; Else
{
Char item = stack [top];
Top -;
Return Item;
}
}
/ * returns the priotity of the operator * /
Int Priority (Char C)
{
IF (c == '^') return 3; / * Exponential Operator * /
IF (c == '*' || c == '/' || c == '%') return 2;
ELSE IF (c == ' ' || c == '-') Return 1;
Else Return 0;
}
/ * Converts the Infix Expression to Prefix Form * /
Void ConvertTopRefix (Void)
{
CHAR OPR;
While (* (s))
{
/ * SKIP White Spaces, if any * /
IF (* (s) == '|| * (s) ==' / t ')
{
S ;
CONTINUE;
}
IF (isdigit (* (s)) || isalpha (* (*
s))))))))) / * Operands * /
{
While (isdigit (* (s)) || Isalpha (*
(s))))))))))))
{
* (t) = * (s);
S ;
T ;
}
}
IF (* (s) == ')') / * Closing Parenthes * /
{
PushonStack (* (s));
S ;
}
IF (* (s) == '*' || * (s) == ' ' || * (s)
== '/' || * (s) == '%' || * (s) == '-' || * (s)
== '^')
{
IF (Top! = -1)
{
OPR = POPFromstack ();
While (Priority (OPR)>
priority (* (s)))))
{
* (t) = opr;
T ;
OPR =
Popfromstack ();
}
PushonStack (OPR);
PushonStack (* (s));
}
Else PushonStack (* (s));
S ;
}
IF (* (s) == '(') / * Opening Parenthesis * /
{
OPR = POPFromstack ();
While (OPR! = ')')
{
* (t) = opr;
T ;
OPR = POPFromstack ();
}
S ;
}
}
While (top! = -1) / * while stack is not empty * / {
OPR = POPFromstack ();
* (t) = opr;
T ;
}
T ;
}
/ * Converts the infix expr. to postfix form * /
Void ConvertTopostfix (Void)
{
CHAR OPR;
While (* (s))
{/ * SKIP White Spaces, if any * /
IF (* (s) == '|| * (s) ==' / t ')
{
S ;
CONTINUE;
}
IF (isdigit (* (s)) || isalpha (* (*
s))))))))) / * Operands * /
{
While (isdigit (* (s)) || Isalpha (*
(s))))))))))))
{
* (t) = * (s);
S ;
T ;
}
}
IF (* (s) == '(') / * Opening Parenthesis * /
{
PushonStack (* (s));
S ;
}
IF (* (s) == '*' || * (s) == ' ' || * (s)
== '/' || * (s) == '%' || * (s) == '-' || * (s)
== '^')
{
IF (Top! = -1)
{
OPR = POPFromstack ();
While (Priority (opr)> =
priority (* (s)))))
{
* (t) = opr;
T ;
OPR =
Popfromstack ();
}
PushonStack (OPR);
PushonStack (* (s));
}
Else PushonStack (* (s));
S ;
}
IF (* (s) == ')') / * Closing Parenthes * /
{
OPR = POPFromstack ();
While (OPR! = '(')
{
* (t) = opr;
T ;
OPR = POPFromstack ();
}
S ;
}
}
While (top! = -1) / * while stack is not empty * /
{
OPR = POPFromstack ();
* (t) = opr;
T ;
}
T ;
}
End of program # 1
Program # 2
/ * Expression Tree: Creation, Conversion and Eveation. * /
#include
#include
#include
#include
#define max 50
Struct Node
{
Struct Node * Left_Child;
Char x;
Struct Node * right_child;
} * stack [50];
INT TOP = -1;
Struct Node * CreateExptreePostfix (char *);
Struct Node * CreateExptreePrefix (char *);
Void Preorder (struct node * sr);
Void inorder (struct node * sr);
Void PostOrder (struct node * sr);
Int Evaluate (struct node * sr);
Void Push (struct node **, struct node *);
Struct Node * POP (struct node **);
Void delete_tree (struct node *);
Main ()
{
Struct node * root;
Char Str [50];
Int z;
CHAR CH;
CLRSCR ();
Printf ("INPUT Expression IS: / N1) prefix / n2) postfix");
CH = GetChe ();
IF (CH == '1')
{
Printf ("/ NENTER Prefix Expression:");
Gets (STR);
Root = CreateExptreePrefix (STR);
}
Else
{
Printf ("/ NENTER Postfix Expression:");
Gets (STR);
Root = CreateExptreePostfix (STR);
}
Printf ("/ NPREFIX Exp.:");
Preorder (root);
Printf ("/ ninfix exp.:");
Inorder (root);
Printf ("/ NPOSTFIX EXP.:");
Postorder (root);
z = evata (root);
Printf ("/ next", z);
Delete_tree (root);
Getch ();
}
Struct Node * CreateExptreePostfix (Char * STR)
{
Struct Node * NLEFT, * NRIGHT, * NODEPTR
While (* STR)
{
Nodeptr = (struct node *) malloc (Struct Node);
Nodeptr-> x = * STR;
IF (* str == ' ' || * str == '-' || * Str == '/' ||
* Str == '*' || * Str == '^')
{
NRIGHT = POP (Stack);
NLEFT = POP (STACK);
Nodeptr-> LEFT_CHILD = NLEFT;
Nodeptr-> Right_Child = NRIGHT;
}
Else
{
Nodeptr-> LEFT_CHILD = NULL;
Nodeptr-> Right_Child = NULL;
}
Push (stack, nodeptr);
Str ;
Return Pop (stack);
}
Struct Node * CreateExptreePrefix (Char * STR)
{
Struct Node * NLEFT, * NRIGHT, * NODEPTR
Strrev (STR);
While (* STR)
{
Nodeptr = (struct node *) malloc (Struct Node);
Nodeptr-> x = * STR;
IF (* str == ' ' || * str == '-' || * str == '/' || * STR
== '*' || * Str == '^')
{
NLEFT = POP (STACK);
NRIGHT = POP (Stack);
Nodeptr-> LEFT_CHILD = NLEFT;
Nodeptr-> Right_Child = NRIGHT;
}
Else
{
Nodeptr-> LEFT_CHILD = NULL;
Nodeptr-> Right_Child = NULL;
}
Push (stack, nodeptr);
Str ;
}
Return Pop (stack);
}
Void inorder (struct node * sr)
{
IF (SR! = null)
{
Inorder (SR -> LEFT_CHILD);
/ * Print The Data of the Node Whose Left Child Is Null or the Path
Has already been travesed * /
Printf ("% C", SR -> x);
inorder (sr -> right_child);
}
}
Void Preorder (struct node * sr)
{
IF (SR! = null)
{
/ * Print the data of a node * /
Printf ("% C", SR -> x);
/ * Traverse Till Left Child Is Not Null * /
Preorder (SR -> LEFT_CHILD);
/ * Traverse Till Right Child Is Not Null * /
Preorder (SR -> Right_Child);
}
}
Void PostOrder (struct node * sr)
{
IF (SR! = null)
{
PostORDER (SR -> LEFT_CHILD);
PostORDER (SR -> Right_Child);
Printf ("% C", SR -> x);
}
}
Void Push (struct node ** stack, struct node * ptr)
{
IF (TOP == max - 1)
Printf ("/ nstack is full./N");
Else
{
TOP ;
Stack [TOP] = PTR;
}
}
/ * POPS an Operator from the stack * /
Struct Node * POP (struct node ** stack)
{
IF (TOP == -1)
{
Printf ("Stack IS Empty / N");
Return -1;
}
Else
{
Struct Node * PTR = stack [top];
Top -;
Return PTR;
}
}
Int Evaluate (struct node * sr)
{
INT X, Y, Z;
IF (SR! = null)
{
IF (SR-> x == ' ' || SR-> x == '-' || SR-
> x == '/' || SR-> x == '*' || SR-> x == '^')
{
x = evAlate (SR -> LEFT_CHILD);
Y = evAlate (SR -> Right_Child);
Switch (SR-> X)
{
Case ' ': z = x y; Break;
Case '-': z = x-y; Break;
Case '*': z = x * y; Break;
Case '/': z = x / y;
Case '^': z = Pow (x, y); Break;
}
Return Z;
}
Return (SR -> X - 48);
}
}
Void delete_tree (struct node * root)
{
IF (root! = null)
{
DELETE_TREE (root-> left_child);
DELETE_TREE (root-> right_child);
Free (root);
}
}
End of program # 2
