Program #1
To convert Infix expression to Prefix and Postfix form using Stack
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>
#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 Prototypes*/
void Initialize (void);
void SetExpression (char *);
char PopFromStack (void );
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();
SetExpression (input) ;
if(ch=='1') /*Infix->Prefix*/
{
strrev ( s );
ConvertToPrefix ( ) ;
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 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 ) == '(' )/*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 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++ ;
}
END OF PROGRAM #1
PROGRAM #2
/*Expression tree: Creation, Conversion and Evaluation.*/
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<math.h>
#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=Evaluate(root);
printf("\nExpression Evaluated to: %d", z);
Delete_Tree(root);
getch();
}
struct node* CreateExpTreePostfix(char* str)
{
struct node* nleft, * nright, * nodeptr;
while (*str)
{
nodeptr = (struct node *) malloc(sizeof(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(sizeof(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 traversed */
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 = Evaluate(sr -> left_child) ;
y = Evaluate(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; break;
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
全文完。
作者：Pradeep P. Chandiramani.
联系方式：pradeepchandiramani@yahoo.co.in
译者：liudows
联系方式：mysea000@163.com
