evalpfexp2.c (2825B)
1 /* Exercise 12.14 */ 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <string.h> 6 #include <ctype.h> 7 8 struct stack_t { 9 int n; 10 struct stack_t *next; 11 }; 12 typedef struct stack_t Stack; 13 14 /* 15 * Prototypes 16 */ 17 void push(Stack **stackp, char value); 18 char pop(Stack **stackp); 19 char isempty(Stack *stackp); 20 int calculate(int op1, int op2, char operator); 21 int evalpfexp(char *expr); 22 int isoper(char c); 23 24 /* main function */ 25 int main(void) 26 { 27 char string[] = { "12 13 + 5 * 8 4 / -" }; 28 29 printf("%s = %d\n", string, evalpfexp(string)); 30 31 return 0; 32 } /* E0F main */ 33 34 /* 35 * Push a value in top of the stack 36 */ 37 void push(Stack **stackp, char value) 38 { 39 Stack *newnode; 40 41 if( (newnode = malloc( sizeof(Stack) )) == NULL ) { 42 printf("push(): cannot allocate the memory\n"); 43 return; 44 } 45 newnode->n = value; 46 newnode->next = NULL; 47 48 newnode->next = *stackp, 49 *stackp = newnode; 50 51 } /* eof push() */ 52 53 /* 54 * Pop a value from top of the stack 55 */ 56 char pop(Stack **stackp) 57 { 58 Stack *tstackp; /* temporary stack pointer for free(3) */ 59 int ret = ( *stackp )->n; 60 61 tstackp = *stackp; 62 *stackp = ( *stackp )->next; 63 64 free(tstackp); 65 66 return ret; 67 } /* eof pop() */ 68 69 /* 70 * Determine if the stack is empty this is a "predicate function" 71 */ 72 char isempty(Stack *stackp) 73 { 74 if( stackp == NULL ) 75 return 1; 76 77 return 0; 78 } /* eof isempty() */ 79 80 /* 81 * Calculate the value of expression "op1 operator op2" 82 */ 83 int calculate(int op1, int op2, char operator) 84 { 85 int i; 86 87 switch(operator) { 88 case '+': 89 return op1 + op2; 90 case '-': 91 return op1 - op2; 92 case '*': 93 return op1 * op2; 94 case '/': 95 if( !op2 ) 96 return 0; 97 else 98 return op1 / op2; 99 case '^': 100 for(i = op2, op2 = op1; i > 1; i--) { 101 op1 *= op2; 102 } 103 104 return op1; 105 case '%': 106 return op1 % op2; 107 } 108 109 return -1; 110 } /* eof calculate() */ 111 112 /* 113 * Check if 'c' is a valid operator 114 */ 115 int isoper(char c) 116 { 117 switch(c) { 118 case '+': 119 case '-': 120 case '*': 121 case '/': 122 case '^': 123 case '%': 124 break; 125 default: 126 return 0; 127 } 128 129 return 1; 130 } /* eof isoper() */ 131 132 /* 133 * Evalutate the expression in reverse polish notation 134 */ 135 int evalpfexp(char *expr) 136 { 137 Stack *stackp; 138 int i = -1; 139 int x, y; 140 141 expr[ (int)strlen(expr) + 1 ] = '\0'; 142 143 while( expr[++i] != '\0' ) { 144 if( isdigit((int)expr[i]) ) { 145 x = y = 1; 146 147 /* set y */ 148 for( ; isdigit((int)expr[i + x]) && expr[i + x] != '\0'; ++x, y *= 10) 149 ; /* empty body */ 150 151 for(x = 0; isdigit((int)expr[i]) && expr[i] != '\0'; y /= 10, i++) { 152 x += (expr[i] - '0') * y; 153 } 154 155 push(&stackp, x); 156 } 157 else if( isoper(expr[i]) ) { 158 x = pop(&stackp); 159 y = pop(&stackp); 160 161 push(&stackp, calculate(y, x, expr[i])); 162 } 163 } 164 165 return pop(&stackp); 166 167 } /* eof evalpfexp() */ 168