//对于标识符,赋值,需要自己处理了//只需要维护一个表就行了.//赋值运算符的优先级很低.#include
#include#include#includeenumIDENTIFER_TYPE{NUMBER,OPERATOR,LB,RB,END,ERROR};enumOPERATOR_TYPE{EXPR,ADD,SUB,MUL,DIV,ATOM};/*ATOM:给原子(数)赋一个优先级*/typedefstructtagNODE{inttype;doublevalue;intope;structtagNODE*left,*right,*parent;}NODE;/*词法
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
*/intg_type;doubleg_value;intg_ope;constchar*g_str;constchar*g_last_str;intGetNextToken(){staticcharbuff[32];inti=0,k;g_last_str=g_str;while(*g_str&&*g_str=='')++g_str;if(!*g_str)returng_type=END;if(isdigit(*g_str)){while(isdigit(*g_str))buff[i++]=*g_str++;buff[i]=0;g_value=atof((constchar*)buff);returng_type=NUMBER;}switch(*g_str++){case'+':g_ope=ADD;returng_type=OPERATOR;case'-':g_ope=SUB;returng_type=OPERATOR;case'*':g_ope=MUL;returng_type=OPERATOR;case'/':g_ope=DIV;returng_type=OPERATOR;case'(':returng_type=LB;case')':returng_type=RB;}returng_type=ERROR;}voidPutBack(){if(g_str!=g_last_str)g_str=g_last_str;}/*语法分析*/intg_error;intg_lb;constchar*g_pos;NODE*MakeNode(inttype,doublevalue,intope,NODE*l,NODE*r,NODE*p){NODE*node=(NODE*)malloc(sizeof(NODE));node->type=type;node->value=value;node->ope=ope;node->left=l;node->right=r;node->parent=p;returnnode;}voidDestroyTree(NODE*tree){if(!tree)return;if(tree->left)DestroyTree(tree->left);if(tree->right)DestroyTree(tree->right);free(tree);}intLevel(intope){switch(ope){caseATOM:return0;caseMUL:caseDIV:return1;caseADD:caseSUB:return2;caseEXPR:return32;}}voidShowError(){charbuff[256]={0};switch(g_error){case1:sprintf(buff,"需要一个运算符\t位置%s\n",g_pos);break;case2:sprintf(buff,"需要一个表达式\t位置%s\n",g_pos);break;case3:sprintf(buff,"括号不匹配\t位置%s\n",g_pos);break;case4:sprintf(buff,"空表达式\t位置%s\n",g_pos);break;case5:sprintf(buff,"表达式不应该在此结束\t位置%s\n",g_pos);break;}printf(buff);}NODE*BuildSyntaxTreeImpl(){NODE*root,*c,*new_node;intuse_level=0;intstate=0;root=c=MakeNode(OPERATOR,0,EXPR,0,0,0);while(1){GetNextToken();switch(g_type){caseNUMBER:if(state!=0){PutBack();g_error=1;gotoExitWithError;}new_node=MakeNode(NUMBER,g_value,ATOM,0,0,0);use_level=1;state=1;break;caseLB:if(state!=0)PutBack();g_error=1;gotoExitWithError;}++g_lb;new_node=BuildSyntaxTreeImpl();if(new_node==NULL){g_error=4;gotoExitWithError;}use_level=0;/*括号表达式的优先级很高,不使用优先级比较,直接建为右子树*/state=1;break;caseRB:if(!g_lb){g_error=3;gotoExitWithError;}--g_lb;caseEND:{c=root->right;free(root);if(c==NULL){g_error=4;gotoExitWithError;}if(state!=1){g_error=5;gotoExitWithError;}c->parent=NULL;returnc;}default:if(state!=1){PutBack();g_error=2;gotoExitWithError;}new_node=MakeNode(OPERATOR,0,g_ope,0,0,0);use_level=1;state=0;}if(use_level){while(Level(new_node->ope)>=Level(c->ope))c=c->parent;new_node->left=c->right;c->right=new_node;new_node->parent=c;c=new_node;}else{c->right=new_node;new_node->parent=c;}}ExitWithError:g_pos=g_str;DestroyTree(root);return0;}NODE*BuildSyntaxTree(constchar*expression){NODE*tree;g_lb=0;g_last_str=g_str=expression;tree=BuildSyntaxTreeImpl();if(g_lb){PutBack();g_error=3;g_pos=g_str;DestroyTree(tree);tree=0;}returntree;}/*结果计算*/doubleEvalueTree(NODE*tree){doublel,r;if(!tree)return0;if(tree->ope==ATOM)returntree->value;l=EvalueTree(tree->left);r=EvalueTree(tree->right);switch(tree->ope){caseADD:returnl+r;caseSUB:returnl-r;caseMUL:returnl*r;caseDIV:returnl/r;}return0;}doubleEvalue(constchar*expression){NODE*tree=BuildSyntaxTree(expression);doublevalue=0;if(!tree)ShowError();elsevalue=EvalueTree(tree);DestroyTree(tree);returnvalue;}intmain(){printf("%lf\n",Evalue("1+8*(9-8)*9+2-1"));return0;}
浙公网安备 33021202002483