C实现将中缀算术式转换成后缀表达式

  1 #include "stdio.h"
  2 #include "stdlib.h"
  3 #include "ctype.h"
  4 #include "math.h"
  5 #include "string.h"
  6 
  7 struct stackNode{
  8     char data;
  9     int value;
 10     struct stackNode *nextPtr;
 11 };
 12 
 13 typedef struct stackNode StackNode;
 14 typedef StackNode *StackNodePtr;
 15 
 16 int isOperator(char c);
 17 void convertToPostfix(char infix[],char postfix[]);
 18 int precedence(char opt1,char opt2);
 19 void push(StackNodePtr *topPtr, char value);
 20 char pop(StackNodePtr *topPtr);
 21 void push2(StackNodePtr *topPtr, int value);
 22 int pop2(StackNodePtr *topPtr);
 23 char stackTop(StackNodePtr topPtr);
 24 int isEmpty(StackNodePtr topPtr);
 25 void printStack(StackNodePtr topPtr);
 26 int calculate(int val1, int val2, char opt);
 27 int evaluatePostfixExp(char postfix[]);
 28 
 29 int main(void)
 30 {
 31     int i=0;
 32     char ch;
 33     char infix[100];
 34     char postfix[100];
 35 
 36     printf("Enter the expression:
");
 37 
 38     while((ch = getchar()) != '
'){
 39         if(ch != ' '){
 40             if(isdigit(ch)){
 41                 infix[i++] = ch; 
 42             }
 43             else if(isOperator(ch)){
 44                 infix[i++] = ' ';
 45                 infix[i++] = ch; 
 46                 infix[i++] = ' ';
 47             }else if(ch == '('){
 48                     infix[i++] = ch; 
 49                     infix[i++] = ' ';
 50             }else{
 51                 infix[i++] = ' ';
 52                 infix[i++] = ch; 
 53             }
 54         }
 55     }
 56     infix[i] = ''; 
 57     
 58     printf("the infix:
%s
",infix);
 59     convertToPostfix(infix,postfix);
 60     printf("the postfix:
%s
",postfix);
 61 
 62     printf("result:%d
",evaluatePostfixExp(postfix));
 63     getchar();
 64     return 0;
 65 }
 66 
 67 /*是否为操作符*/
 68 int isOperator(char c)
 69 {
 70     switch(c){
 71         case '+':
 72         case '-':
 73         case '*':
 74         case '/':
 75         case '^':
 76             return 1;break;
 77         default:
 78             return 0;break;
 79     }
 80 }
 81 
 82 /*转换成后缀表达式*/
 83 void convertToPostfix(char infix[],char postfix[])
 84 {
 85     int i,j=0;
 86     char *strPtr;
 87     char popValue;
 88     StackNodePtr stackPtr =NULL;
 89 
 90     strPtr = strtok(infix, " ");
 91     while(strPtr){
 92         if(isdigit(strPtr[0])){
 93             if(j>0 ){
 94                 postfix[j++] = ' ';
 95             }
 96             while(*strPtr !=  ''){
 97                 postfix[j++] = *strPtr;
 98                 strPtr++;
 99             }
100         }else if(strPtr[0] == '('){
101             push(&stackPtr,'(');
102             printStack(stackPtr);
103         }else if(strPtr[0] == ')'){//遇到右括号，必须把对应左括号前的运算符都弹出
104             while((popValue = pop(&stackPtr)) != '(' ){
105                 postfix[j++] = ' ';
106                 postfix[j++] = popValue;
107                 printStack(stackPtr);
108             }
109         }else if(isOperator(strPtr[0])){
110             int flag = 1;
111             char tmpCH;
112             while(flag){//这里必须判断栈里是否还有运算符优先级比当前运算符高的
113                 tmpCH = stackTop(stackPtr);
114                 if(tmpCH == '(' || tmpCH == '0'){
115                     push(&stackPtr,strPtr[0]);
116                     printStack(stackPtr);
117                     flag = 0;
118                 }else{
119                     if(precedence(strPtr[0],tmpCH) > 0){
120                         postfix[j++] = ' ';
121                         postfix[j++] = pop(&stackPtr);
122                         printStack(stackPtr);
123                     }else{
124                         push(&stackPtr,strPtr[0]);
125                         printStack(stackPtr);
126                         flag = 0;
127                     }
128                 }
129             }
130         }
131         strPtr = strtok(NULL, " ");
132     }
133     while(!isEmpty(stackPtr)){//栈里如果还有运算符就弹出
134         postfix[j++] = ' ';
135         postfix[j++] = pop(&stackPtr);
136         printStack(stackPtr);
137     }
138 /*    for(i = 0; infix[i] != ''; i++){
139         if(isOperator(infix[i])){
140             char tmpCH = stackTop(stackPtr);
141             if(tmpCH == '(' || tmpCH == '0'){
142                 push(&stackPtr,infix[i]);
143                 printStack(stackPtr);
144             }else{
145                 if(precedence(infix[i],tmpCH) > 0){
146                     postfix[j++] = pop(&stackPtr);
147                     push(&stackPtr,infix[i]);
148                     printStack(stackPtr);
149                 }else{
150                     push(&stackPtr,infix[i]);
151                     printStack(stackPtr);
152                 }
153             }
154         }else if(infix[i] == '('){
155             push(&stackPtr,infix[i]);
156             printStack(stackPtr);
157         }else if(infix[i] == ')'){
158             while((popValue = pop(&stackPtr)) != '(' ){
159                 postfix[j++] = popValue;
160                 printStack(stackPtr);
161             }
162         }else if(isdigit(infix[i])){
163             postfix[j++] = infix[i];
164         }
165     }
166     while(!isEmpty(stackPtr)){
167         postfix[j++] = pop(&stackPtr);
168         printStack(stackPtr);
169     }
170     */
171     postfix[j] = '';
172 }
173 
174 /*优先级的判断*/
175 int precedence(char opt1,char opt2)
176 {
177     switch(opt1){
178         case '+':
179         case '-':if(opt2 == '+' || opt2 == '-'){
180                     return 0;
181                  }else{
182                     return 1;
183                  }
184                  break;
185         case '*':
186         case '/':
187         case '^':
188         case '%':if(opt2 == '+' || opt2 == '-'){
189                     return -1;
190                  }else{
191                     return 0;
192                  }
193                  break;
194         default:
195             printf("unvalid operator.
");
196             break;
197     }
198 }
199 
200 void push(StackNodePtr *topPtr, char value)
201 {
202     StackNodePtr newPtr;
203     newPtr = (StackNodePtr)malloc(sizeof(StackNode));
204     if(newPtr != NULL){
205         newPtr->data = value;
206         newPtr->nextPtr = *topPtr;
207         *topPtr = newPtr;    
208     }else{
209         printf("call for memeory is failed!
");
210     }
211 }
212 
213 void push2(StackNodePtr *topPtr, int value)
214 {
215     StackNodePtr newPtr;
216     newPtr = (StackNodePtr)malloc(sizeof(StackNode));
217     if(newPtr != NULL){
218         newPtr->value = value;
219         newPtr->nextPtr = *topPtr;
220         *topPtr = newPtr;    
221     }else{
222         printf("call for memeory is failed!
");
223     }
224 }
225 
226 char pop(StackNodePtr *topPtr)
227 {
228     char value;
229     StackNodePtr tmpPtr;
230     tmpPtr = *topPtr;
231     value = (*topPtr)->data;
232     *topPtr = (*topPtr)->nextPtr ; 
233     free(tmpPtr);
234     return value;
235 }
236 
237 int pop2(StackNodePtr *topPtr)
238 {
239     int value;
240     StackNodePtr tmpPtr;
241     tmpPtr = *topPtr;
242     value = (*topPtr)->value;
243     *topPtr = (*topPtr)->nextPtr ; 
244     free(tmpPtr);
245     return value;
246 }
247 
248 char stackTop(StackNodePtr topPtr)
249 {
250     if(!isEmpty(topPtr)){
251         return topPtr->data;
252     }else{
253         return '0';
254     }
255 }
256 
257 int isEmpty(StackNodePtr topPtr)
258 {
259     return topPtr==NULL;
260 }
261 
262 void printStack(StackNodePtr topPtr)
263 {
264     if(topPtr){
265         while(topPtr){
266             printf("%c",topPtr->data);
267             topPtr = topPtr ->nextPtr;
268         }
269         printf("NULL
");
270     }else{
271         printf("this stack is empty.
");
272     }
273 }
274 
275 int evaluatePostfixExp(char postfix[])
276 {
277     int i;
278     int val1,val2;
279     char *tokenPtr;
280     StackNodePtr stackPtr = NULL;
281 
282     tokenPtr = strtok(postfix, " ");
283 
284     while(tokenPtr){
285         if(isdigit(tokenPtr[0])){
286             push2(&stackPtr,atoi(tokenPtr));
287         }
288         if(isOperator(tokenPtr[0])){
289             val1 = pop2(&stackPtr) ;
290             val2 = pop2(&stackPtr) ;
291             push2(&stackPtr,calculate(val2,val1,tokenPtr[0]));
292         }
293         tokenPtr = strtok(NULL, " ");
294     }
295 /*    for(i=0; postfix[i] != ''; i++){
296         if(isdigit(postfix[i])){
297             push(&stackPtr,postfix[i]);
298         }
299         if(isOperator(postfix[i])){
300             val1 = pop(&stackPtr) - 48;
301             val2 = pop(&stackPtr) - 48;
302             push(&stackPtr,calculate(val2,val1,postfix[i]) +48);
303         }
304     }*/
305 
306     return pop2(&stackPtr);
307 }
308 
309 int calculate(int val1, int val2, char opt)
310 {
311     switch(opt){
312         case '+':
313             return val1 + val2;
314             break;
315         case '-':
316             return val1 - val2;
317             break;
318         case '*':
319             return val1*val2;
320             break;
321         case '/':
322             return val1/val2;
323             break;
324         case '^':
325             return (int)(pow((double)val1,val2));
326             break;
327         default:
328             printf("operator is error!
");
329     }
330     return 0;
331 }