ramytamer

infix to postfix

Jun 19th, 2014
277
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.32 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <ctype.h>
  5.  
  6. #define TYPE int
  7. #define STACKSIZE 100
  8.  
  9. typedef struct {
  10.     int top;
  11.     TYPE items[STACKSIZE];
  12. } Stack;
  13.  
  14. void initialize(Stack *s) {s->top=0;}
  15. void push(Stack *s,TYPE value) {s->items[s->top++]=value;}
  16. TYPE pop(Stack *s) {return s->items[--s->top];}
  17. TYPE peek(Stack *s) {return s->items[s->top-1];}
  18. int isfull(Stack *s) {return s->top<STACKSIZE?0:1 ;}
  19. int isempty(Stack *s) {return s->top==0?1:0;}
  20.  
  21. void error() {printf("error");exit(-1);}
  22.  
  23. int isoperator(char e)
  24. {
  25.  if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%') return 1;
  26.  return 0;
  27. }
  28.  
  29. int priority(char e)
  30. {
  31.  int pri = 0;
  32.  if(e == '*' || e == '/' || e =='%') pri = 2;
  33.  else  if(e == '+' || e == '-') pri = 1;
  34.  return pri;
  35. }
  36.  
  37. void infix2postfix(char* infix, char * postfix){
  38.     char *i,*p;
  39.     Stack X; char n1;
  40.     initialize(&X);
  41.     i = infix;
  42.     p = postfix; //&postfix[0];
  43.     while(*i){
  44.         while(*i == ' ' || *i == '\t')
  45.             i++;
  46.         if( isdigit(*i) || isalpha(*i) ) {
  47.             while( isdigit(*i) || isalpha(*i)){
  48.                 *p = *i;
  49.                 p++;
  50.                 i++;
  51.             }  
  52.             *p++ = ' ';
  53.         }
  54.         if( *i == '(' )
  55.             push(&X,*i++);
  56.         if( *i == ')'){
  57.             n1 = pop(&X);
  58.             while( n1 != '(' ){
  59.                 *p++ = n1;
  60.                 *p++ = ' ';
  61.                 n1 = pop(&X);
  62.             }
  63.             i++;
  64.         }
  65.         if( isoperator(*i) ){
  66.             if(isempty(&X))
  67.                 push(&X,*i);
  68.             else{
  69.                 n1 = pop(&X);
  70.                 while(priority(n1) >= priority(*i)){
  71.                     *p++ = n1;
  72.                     *p++ = ' ';
  73.                     n1 = pop(&X);
  74.                 }
  75.                 push(&X,n1);
  76.                 push(&X,*i);
  77.             }
  78.             i++;
  79.         }
  80.     }
  81.     while(!isempty(&X)){
  82.         n1 = pop(&X);
  83.         *p++ = n1;
  84.         *p++ = ' ';
  85.     }
  86.     *p = '\0';
  87. }
  88.  
  89.  
  90.  
  91.  
  92.  
  93. int main()
  94. {
  95.     Stack s; initialize(&s);
  96.     // Input: (((8 + 1) - (7 - 4)) / (11 - 9))
  97.     // Output: 8 1 + 7 4 - - 11 9 - /
  98.     char  inStr[100];
  99.     strcpy(inStr,"(((8 + 1) - (7 - 4)) / (11 - 9))");
  100.     char post[100];
  101.     infix2postfix(inStr,post);
  102.     printf("%s<-->%s\n",inStr,post);
  103.     strcpy(inStr,"a+b/c");
  104.     infix2postfix(inStr,post);
  105.     printf("%s<-->%s\n",inStr,post);
  106.     strcpy(inStr,"a/b+c");
  107.     infix2postfix(inStr,post);
  108.     printf("%s<-->%s\n",inStr,post);
  109.     return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment