表达式，转换和计算，用C语言描述－－Part4（源

作者：zhaozj
发表时间：2020-12-23 10:54
来源：未知

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