给定字符串型的算术表达式，实现中缀转后缀并运算得出结果；
1 #ifndef STACK_H_INCLUDED 2 #define STACK_H_INCLUDED 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include"stack.h" 6 #define SIZE 100 7 #define TYPE char 8 typedef struct Node* pNode; 9 typedef struct Node node; 10 typedef pNode Stack; 11 12 char postfix[SIZE]; 13 14 struct Node 15 { 16 TYPE data; 17 struct Node* next; 18 }; 19 int isEmpty(Stack s); 20 void Pop(Stack s); 21 void Push(Stack s,TYPE element); 22 TYPE Top_of_stack(Stack s); 23 Stack CreatStack(); 24 void makeEmpty(Stack s); 25 26 Stack CreatStack() 27 { 28 Stack s=(Stack)malloc(sizeof(node)); 29 s->next=NULL; 30 makeEmpty(s); 31 return s; 32 } 33 void makeEmpty(Stack s) 34 { 35 if(s==NULL) 36 printf("you need creat a stack at first"); 37 while(!isEmpty(s)) 38 Pop(s); 39 } 40 int isEmpty(Stack s) 41 { 42 return s->next==NULL; 43 } 44 void Pop(Stack s) 45 { 46 if(isEmpty(s)) 47 printf("Stack is empty"); 48 else 49 { 50 pNode temp=s->next; 51 s->next=s->next->next; 52 free(temp); 53 } 54 55 } 56 void Push(Stack s,TYPE element) 57 { 58 pNode temp=(Stack)malloc(sizeof(node)); 59 if(temp) 60 { 61 temp->data=element; 62 temp->next=s->next; 63 s->next=temp; 64 } 65 } 66 TYPE Top_of_stack(Stack s) 67 { 68 if(isEmpty(s)) 69 { 70 printf("Stack is empty"); 71 return 0; 72 } 73 else 74 return s->next->data; 75 } 76 77 78 #endif // STACK_H_INCLUDED
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include"stack.h" 4 #define SIZE 100 5 6 char postfix[SIZE]; 7 8 // if op > instack push else pop; 9 // return the priority of operator of expression minus 10 //that of stack 栈外优先级减去栈内优先级 11 int priority(char op_of_expression,char ch_in_stack) 12 { 13 int op=0; 14 int ch=0; 15 if(op_of_expression=='+'||op_of_expression=='-') 16 op=1; 17 else if(op_of_expression=='*'||op_of_expression=='/') 18 op=2; 19 else if(op_of_expression=='(') 20 op=3; 21 else 22 printf("wrong operator"); 23 24 if(ch_in_stack=='+'||ch_in_stack=='-') 25 ch=1; 26 else if(ch_in_stack=='*'||ch_in_stack=='/') 27 ch=2; 28 else if(ch_in_stack=='(') 29 ch=0; 30 else 31 printf("wrong operator"); 32 33 return op-ch; 34 } 35 int isOperator(char ch) 36 { 37 switch (ch) 38 { 39 case'+': 40 case'-': 41 case'*': 42 case'/': 43 case'(': 44 case')': 45 return 1; 46 break; 47 default: 48 return 0; 49 break; 50 } 51 } 52 void Infix_to_Pofix(char* s) 53 { 54 int index=0; 55 56 char ch; 57 Stack stack=CreatStack(); 58 makeEmpty(stack); 59 while((ch=*s)!=' ') 60 { 61 if(!isOperator(ch)) 62 { 63 postfix[index++]=ch; 64 s++; 65 if(isOperator(*s)||*s==' ') 66 postfix[index++]='_'; 67 } 68 else 69 { 70 if(isEmpty(stack)) 71 { 72 Push(stack,ch); 73 s++; 74 continue; 75 } 76 else 77 { 78 if(ch==')') 79 { 80 while(!isEmpty(stack)&&Top_of_stack(stack)!='(') 81 { 82 postfix[index++]=Top_of_stack(stack); 83 Pop(stack); 84 } 85 Pop(stack); 86 s++; 87 continue; 88 } 89 else if(priority(ch,Top_of_stack(stack))>0) 90 { 91 Push(stack,ch); 92 s++; 93 continue; 94 } 95 else 96 { 97 while(!isEmpty(stack)&&priority(ch,Top_of_stack(stack))<=0) 98 { 99 postfix[index++]=Top_of_stack(stack); 100 Pop(stack); 101 } 102 Push(stack,ch); 103 s++; 104 continue; 105 } 106 // else if(priority(ch,Tops)) 107 } 108 } 109 110 } 111 while(!isEmpty(stack)) 112 { 113 postfix[index++]=Top_of_stack(stack); 114 Pop(stack); 115 } 116 //postfix[index++]=' '; 117 } 118 119 int compute(char *str) 120 { 121 #undef TYPE 122 #define TYPE int 123 Stack s=CreatStack(); 124 makeEmpty(s); 125 int temp_int; 126 while((*str)!=' ') 127 { 128 129 if(isdigit(*str)) 130 { 131 Push(s,(int)atof(str)); 132 //printf("ss%d",(int)atof(str)); 133 while(((*str)!='_')) 134 { 135 str++; 136 } 137 str++; 138 } 139 else if(isOperator((*str))) 140 { 141 switch(*str) 142 { 143 case'*': 144 temp_int=Top_of_stack(s); 145 Pop(s); 146 //printf("%d ",Top_of_stack(s)); 147 temp_int*=Top_of_stack(s); 148 Pop(s); 149 Push(s,temp_int); 150 //printf("%d ",Top_of_stack(s)); 151 break; 152 case'-': 153 temp_int=Top_of_stack(s); 154 Pop(s); 155 //printf("%d ",Top_of_stack(s)); 156 temp_int=Top_of_stack(s)-temp_int; 157 Pop(s); 158 Push(s,temp_int); 159 //printf("%d ",Top_of_stack(s)); 160 break; 161 case'/': 162 temp_int=Top_of_stack(s); 163 Pop(s); 164 //printf("%d ",Top_of_stack(s)); 165 temp_int=Top_of_stack(s)/temp_int; 166 Pop(s); 167 Push(s,temp_int); 168 //printf("%d ",Top_of_stack(s)); 169 break; 170 case'+': 171 temp_int=Top_of_stack(s); 172 Pop(s); 173 //printf("%d ",Top_of_stack(s)); 174 temp_int+=Top_of_stack(s); 175 Pop(s); 176 Push(s,temp_int); 177 //printf("%d ",Top_of_stack(s)); 178 break; 179 default: 180 printf("wrong"); 181 break; 182 } 183 str++; 184 } 185 186 } 187 return temp_int; 188 } 189 190 191 int main() 192 { 193 char ch[]="10+(3*6-8)/2"; 194 Infix_to_Pofix(ch); 195 printf("%s ",postfix); 196 //postfix="134.4"; 197 // printf("%d ",(int)atof("34_34*")); 198 printf("result：%d ",compute(postfix)); 199 200 201 202 return 0; 203 }