题目:
第15题,完成计算器功能,输入计算式,输出结果
思路:
以前做过了,纯当练习了,中缀转后缀转出
方案:
中缀转后缀:次序读入,数字放入输出数组中,运算符查看运算符栈顶,若栈顶运算符高于或等于当前栈则弹入输出数组,将当前运算符压入栈。全部遍历结束后将运算符内所有剩余运算符弹入输出数组。
后缀转结果:次序读入,遇到数字压入结果栈,遇到运算符,弹出结果栈顶两个数字,进行运算,将结果压入栈。如此当遍历结束时,若之前中缀转换和后缀运算全部正确,则栈内应只剩最终结果,输出。
代码:
1、数字和运算符统一存储用结构体(其实用联合更好,不过有点懒……),以及中缀转后缀用栈节点
typedef struct Element { int mark;//表示当前元素是数还是操作符,1 表示数,-1表示操作符 float data; char op; }Element; typedef struct OpStack//中缀变后缀用的操作符暂存栈 { char op; struct OpStack *next; }OpStack;
2、中缀转后缀代码
1 Element *MidToPost(char *str) 2 { 3 Element *postorder=malloc(sizeof(Element)*MAX_LEN);//后缀存储数组 4 memset(postorder,0,sizeof(Element)*MAX_LEN); 5 6 OpStack *top=NULL; 7 int len=strlen(str); 8 int i=0;//字符串迭代器 9 float temp_num=0;//字符数字转换用临时存储 10 int post_pos=0;//后缀数组迭代器 11 int new_number_mark=0;//是否有了新的数字 12 int decimal_mark=0;//小数标记 13 char top_temp;//查看栈顶用临时缓存 14 for(i=0;i<=len-1;++i) 15 { 16 if(str[i]<=‘9‘&&str[i]>=‘0‘)//是个数字 17 { 18 temp_num=temp_num*10+str[i]-48;//存进去 19 new_number_mark=1;//有新数 20 decimal_mark*=10; 21 } 22 else if(str[i]==‘.‘)//啊哈,小数点 23 decimal_mark=1; 24 else//遇到了操作符 25 { 26 if(new_number_mark==1)//首先看此时是否已经有了数可以放在后缀数组中 27 { 28 postorder[post_pos].mark=1; 29 if(decimal_mark!=0)//是个小数 30 temp_num/=decimal_mark; 31 postorder[post_pos++].data=temp_num; 32 temp_num=0; 33 new_number_mark=0; 34 decimal_mark=0; 35 } 36 if(str[i]==‘+‘||str[i]==‘-‘) 37 { 38 while(top!=NULL&&OpStackTop(top)!=‘(‘)//遇到加减,把直到开头或左括号的所有操作符都放入数组 39 { 40 postorder[post_pos].mark=-1; 41 postorder[post_pos++].op=OpStackPop(&top); 42 } 43 OpStackPush(&top,str[i]); 44 } 45 else if(str[i]==‘*‘||str[i]==‘/‘) 46 { 47 while(top!=NULL&&((top_temp=OpStackTop(top))!=‘(‘&&top_temp!=‘+‘&&top_temp!=‘-‘))//遇到乘除,把直到开头或左括号或加减的操作符都放入数组 48 { 49 postorder[post_pos].mark=-1; 50 postorder[post_pos++].op=OpStackPop(&top); 51 } 52 OpStackPush(&top,str[i]); 53 } 54 else if(str[i]==‘(‘) 55 OpStackPush(&top,‘(‘); 56 else//只剩下右括号 57 { 58 while(OpStackTop(top)!=‘(‘)//把一直到左括号的操作符全放进去 59 { 60 postorder[post_pos].mark=-1; 61 postorder[post_pos++].op=OpStackPop(&top); 62 } 63 OpStackPop(&top);//把这个左括号也弹出去 64 } 65 } 66 } 67 if(new_number_mark==1)//还有个数 68 { 69 postorder[post_pos].mark=1; 70 if(decimal_mark!=0)//是个小数 71 temp_num/=decimal_mark; 72 postorder[post_pos++].data=temp_num; 73 temp_num=0; 74 new_number_mark=0; 75 decimal_mark=0; 76 } 77 while(top!=NULL)//读完后若操作符栈内还有剩余操作符,全部加入后缀 78 { 79 postorder[post_pos].mark=-1; 80 postorder[post_pos++].op=OpStackPop(&top); 81 } 82 return postorder; 83 }
3、计算结果用栈,这次主要float就好
typedef struct FloatStack { float number; struct FloatStack *next; }FloatStack;
4、后缀转结果代码
1 float PostToResult(Element *postorder) 2 { 3 //注意:以下不添加任何对后缀表达式的检测,如果后缀转换出错那么废定了 4 FloatStack *top=NULL; 5 int i=0; 6 float temp1,temp2; 7 while(postorder[i].mark!=0) 8 { 9 if(postorder[i].mark==1)//是个男孩!啊不,是个数…… 10 FloatStackPush(&top,postorder[i].data); 11 else//是个女孩!哎不是,是个操作符…… 12 { 13 temp2=FloatStackPop(&top); 14 temp1=FloatStackPop(&top);//我擦这顺序真特么重要啊! 15 if(postorder[i].op==‘+‘) 16 FloatStackPush(&top,temp1+temp2); 17 else if(postorder[i].op==‘-‘) 18 FloatStackPush(&top,temp1-temp2); 19 else if(postorder[i].op==‘*‘) 20 FloatStackPush(&top,temp1*temp2); 21 else 22 FloatStackPush(&top,temp1/temp2); 23 } 24 ++i; 25 } 26 float ret=FloatStackPop(&top); 27 printf("For test:ret=%f\n",ret); 28 return ret; 29 }