topostfix.c (3637B)
1 /* Exercise 12.12 */ 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <ctype.h> 6 #include <string.h> 7 8 #define BUF 50 9 10 struct stack_t { 11 char c; 12 struct stack_t *next; 13 }; 14 typedef struct stack_t Stack; 15 16 /* 17 * Prototypes 18 */ 19 int isoper(char c); 20 int precedence(char op1, char op2); 21 void push(Stack **stackp, char value); 22 char pop(Stack **stackp); 23 char stacktop(Stack *stackp); 24 char isempty(Stack *stackp); 25 void topostfix(char infix[], char postfix[]); 26 27 /* main function */ 28 int main(void) 29 { 30 char string1[BUF] = { 0 }; 31 char string2[BUF] = { 0 }; 32 33 printf("Insert an expression: "); 34 fgets(string1, BUF, stdin); 35 36 topostfix(string1, string2); 37 38 printf("To polish infix notation: %s\n", string2); 39 40 return 0; 41 } /* E0F main */ 42 43 /* 44 * Check if 'c' is a valid operator 45 */ 46 int isoper(char c) 47 { 48 switch(c) { 49 case '+': 50 case '-': 51 case '*': 52 case '/': 53 case '^': 54 case '%': 55 return 1; 56 } 57 58 return 0; 59 } /* eof isoper() */ 60 61 /* 62 * Determine if the priority of op1 is less then, equal to 63 * or greter then op2 and return respectively, -1, 0 and 1. 64 */ 65 int precedence(char op1, char op2) 66 { 67 int x = 2; 68 char *p = &op1; 69 70 while( x-- ) { 71 if( !x ) 72 p = &op2; 73 74 switch( *p ) { 75 case '%': 76 case '/': 77 case '*': 78 *p = '1'; 79 break; 80 case '-': 81 case '+': 82 *p = '2'; 83 break; 84 case '^': 85 *p = '3'; 86 break; 87 default: 88 return -1; 89 } 90 91 } 92 93 x = (op1 - '0') - (op2 - '0'); 94 95 if( x > 0 ) 96 return 1; 97 else if( x < 0 ) 98 return -1; 99 100 return 0; 101 } /* eof precedence() */ 102 103 /* 104 * Push a value in top of the stack 105 */ 106 void push(Stack **stackp, char value) 107 { 108 Stack *newnode; 109 110 if( (newnode = malloc( sizeof(Stack) )) == NULL ) { 111 printf("push(): cannot allocate the memory\n"); 112 return; 113 } 114 115 newnode->c = value; 116 newnode->next = *stackp, 117 118 *stackp = newnode; 119 120 } /* eof push() */ 121 122 /* 123 * Pop a value from top of the stack 124 */ 125 char pop(Stack **stackp) 126 { 127 Stack *tstackp; /* temporary stack pointer for free(3) */ 128 char ret = ( *stackp )->c; 129 130 tstackp = *stackp; 131 *stackp = ( *stackp )->next; 132 133 free(tstackp); 134 135 return ret; 136 } /* eof pop() */ 137 138 /* 139 * As pop() but don't extract the value from top of stack 140 * This is a "predicate function" 141 */ 142 char stacktop(Stack *stackp) 143 { 144 return stackp->c; 145 } /* eof stacktop() */ 146 147 /* 148 * Determine if the stack is empty 149 * This is a "predicate function" 150 */ 151 char isempty(Stack *stackp) 152 { 153 if( stackp == NULL ) 154 return 1; 155 156 return 0; 157 } /* eof isempty() */ 158 159 /* 160 * Convert from infix format to reverse polish suffix 161 * E.g.: 162 * 163 * The expression (1 + 5) * 9 - 2 / 6 164 * is equivalent to 1 5 + 9 * 2 6 / - 165 * 166 */ 167 void topostfix(char infix[], char postfix[]) 168 { 169 Stack *stackp = NULL; 170 int i = 0, j = 0; 171 172 push(&stackp, '('); 173 infix[ (int)strlen(infix) ] = ')'; 174 infix[ (int)strlen(infix) ] = '\0'; 175 176 while( ! isempty(stackp) ) { 177 if( isspace( (int)infix[i] ) ) ; /* ignore the blank spaces */ 178 179 else if( isdigit((int)infix[i]) ) { 180 postfix[j++] = infix[i]; 181 } 182 else if( infix[i] == '(' ) { 183 push(&stackp, '('); 184 } 185 else if( isoper(infix[i]) ) { 186 postfix[j++] = ' '; 187 188 while( precedence(infix[i], stacktop(stackp)) != -1 ) { 189 postfix[j++] = pop(&stackp); 190 } 191 192 push(&stackp, infix[i]); 193 postfix[j++] = ' '; 194 } 195 else if( infix[i] == ')' ) { 196 postfix[j++] = ' '; 197 while( stacktop(stackp) != '(' && isoper(stacktop(stackp)) ) { 198 postfix[j++] = pop(&stackp); 199 } 200 pop(&stackp); /* remove the '(' from the stack */ 201 } 202 203 ++i; 204 } 205 } /* eof topostfix() */ 206