#include"stdio.h"#include "stdlib.h"#define ERROR 99999#define LFTE_BRACE 5#define RIGHT_BRACE 6#define END 7float calc_two(char sybol,float number1,float number2);/*------------------------------------*/typedef struct NODE{ float data; struct NODE *next;}sign_data;/*-------------------------------------进栈函数push_stack()---------------------------------------*/int push_stack(float data,sign_data** data_top){ sign_data* p=NULL; p = (void *)malloc(sizeof(sign_data)); if(p==NULL) return 0; (*p).data = data;//把要送入的数据给节点 (*p).next = (*data_top);//节点的指针指向 (*data_top) = p; return 1;}/*----------------------------------------出栈函数pop_stack()-----------------------------------------*/float pop_stack(sign_data **data_top){ sign_data pop_data; if(*data_top==NULL) return 0; pop_data.data = (*data_top)->data; pop_data.next = (*data_top)->next; free(*data_top); *data_top = pop_data.next; return pop_data.data;}typedef struct oper{ char symbol[2]; int number;}symbol_data;
symbol_data express_sign[]={ {{' ',' ' },0}, {{'+','/0'},1}, {{'-','/0'},2}, {{'*','/0'},3}, {{'/','/0'},4}, {{'(','/0'},5}, {{')','/0'},6}, {{'/0','/0'},7},};
/*----------------------------------------------------优先级的设计:优先级分为:当前优先级和栈顶优先级只有当当前的优先级小于栈顶的优先级才能够进行出栈的操作-------------------------------------------------------*/int fr_pri[] = {0,2,2,3,3,4,1,1};//当前的优先级int bre_pri[]= {0,2,2,3,3,1,4,1};//栈顶的优先级
int get_token(char *express,int *postion,float *data);
float calc(char *express){ float data=0.0;//用来存储返回的数字 int postion=0; float reasult; sign_data *number_top;//用来存储数字 sign_data *symbol_top;//用来存储运算符号 float symbol; float data1; float data2; //char *express="4+4+((4+8)*9-230)"; int c=0; unsigned int flag=1;
/*------------------------------ 首先是左括号进栈 --------------------------------*/ push_stack(LFTE_BRACE,&symbol_top);
//while(express[postion]!='/0') while(flag==1) { c = get_token(express,&postion,&data); if(c==0) { push_stack(data,&number_top); } /*------------------------------------------- 这是获取的是符号的情况,我们获取的是符号的编号 符号进栈的条件是: 比栈顶的符号的优先级要高 符号出栈的条件是: 当前符号的优先级比栈顶符号优先级要高,那么 符号就可以出栈 ----------------------------------------------*/ else { if(fr_pri[c] > bre_pri[(int)symbol_top->data]) { push_stack((float)c,&symbol_top);//如果当前的优先级大于运算符号栈顶的优先级那么就压入堆栈。 } else { /*------------------------------------------------------------------------------ 条件语句是:判断当前符号的优先级要比符号栈顶的优先级要低，并且符号栈顶的元素不是( 这里最好要用while循环， --------------------------------------------------------------------------------*/ while((fr_pri[c] <= bre_pri[(int)symbol_top->data])&&(symbol_top->data!=5)) { data2=pop_stack(&number_top);
data1=pop_stack(&number_top);
symbol = pop_stack(&symbol_top);
reasult = calc_two(express_sign[(int)symbol].symbol[0] ,data1,data2);
push_stack(reasult,&number_top); } /*------------------------------------------------------- 对括号的处理:删除左括号:如果栈顶是'('当前的符号是')'那么就要删除栈顶的( ---------------------------------------------------------*/ if(symbol_top->data==LFTE_BRACE&&(c==RIGHT_BRACE)) { pop_stack(&symbol_top); } /*--------------------------------------------------------------- 对当前符号的处理:如果当前的符号不是右括号那么这个符号就要进栈 -----------------------------------------------------------------*/ if(c!=RIGHT_BRACE&&c!=END) { push_stack((float)c,&symbol_top); } /*-------------------------------------------------------------- 对结果的处理:当栈顶元素是(,当前的符号是/0表示的是计算的结果 ----------------------------------------------------------------*/ if((int)symbol_top->data==5&&c==7) { return pop_stack(&number_top); flag=0; } } } } return ERROR;}/*-----------------------------------------------------------------函数名称:int get_token(char *express,int *postion,int *data)函数的功能:获取在express里面的符号和数字函数的返回值: 0表示的是从express里面获取的是数字并且存放到变量data里面 !0表示的运算符号的标号，他的标号是从1开始的--------------------------------------------------------------------*/int get_token(char *express,int *postion,float *data){ unsigned int i; if((express[*postion]<'0')||(express[*postion]>'9')) { for(i=1;i<8;i++) { if(express[*postion]==express_sign[i].symbol[0]) { *postion = (*postion)+1; return express_sign[i].number; } } } else { float number_data=0.0; while(1) { number_data=express[*postion] -'0'+ number_data; *postion=(*postion)+1; if((express[*postion]>='0')&&(express[*postion]<='9')) { number_data=number_data*10; } else { *data = number_data; return 0; } } } return ERROR;}/*---------------------------------实际的运算过程-----------------------------------*/float calc_two(char sybol,float number1,float number2){ float result; switch(sybol) { case '+': result = number1 + number2; break; case '-':result = number1 - number2; break; case '*': result = number1 * number2; break; case '/': result = number1/number2; break; } return result;}/*-------------------------------用来测试进栈和出栈的函数--------------------------------*/ceshi_main(){ sign_data *number; unsigned int i; for(i=0;i<20;i++) { push_stack((float)i,&number); } while(i!=0) { (float)i=pop_stack(&number); printf("%d",i); } }main(){ char express[100]; printf("请输入要计算的多项式表达式:"); gets(express); printf("%f",calc(express));}
