中缀表达式转化成后缀表达式的计算

目录一、设计思想……………………………………………………….01二、算法流程图…………………………………………………….02三、源代码………………………………………………………….03四、运行结果……………………………………………………….16五、遇到的问题及解决…………………………………………….17六、心得体会……………………………………………………….18用两种方式实现表达式自动计算-1-一、设计思想第一种算法先把算术表达式转化成后缀表达式，在对后缀表达式进行计算。首先建立一个符号栈，用于存放字符和字符的优先级别；然后在建立一个数栈，用于辅助后缀表达式的计算；最后在定义一个字符串数组，用于存放后缀表达式。建立一个计算的函数，该函数用于两个数的计算，在调用这个函数的时候，传入三个参数，两个浮点型参数和一个字符型参数，根据不同的符号进行不同的计算。定义一个判断优先级别的函数，用于判断两个操作符的优先级别，在根据优先级的不同决定不同的操作。后缀表达式的取得，对算术表达式字符串进行挨个的扫描，如果是数字或者是小数点，则将数字或者小数点存放到字符数组中，每取完一个数字，则在后面用“|”隔开，如果是操作符，则和栈中得操作符进行比较，若扫描到的符号优先级比栈里的符号优先级低，则栈中元素出栈并存放到字符数组中。每出一个字符到字符数组中就在后面加“|”分隔。继续检查栈顶比较优先级，直到栈中元素优先级比扫描到的符号优先级低或者符号栈为空，则将此操作符入栈。若是“（”则无条件入字符栈，若是“）”则从字符栈中出字符直到遇到“（”为止。当字符数组扫描到最后的时候，计算并没有结束。然后得进行字符栈的判断，看是否已经为空栈，若不是空栈，则出栈字符，将字符存放到数组中。最后字符串数组中存放的就是后缀表达式。得到后缀表达式后，要用数栈进行后缀表达式的计算，后缀表达式的计算中，对新的数组进行从道到尾的扫描，如果遇到数字，以“|”为标记取出完整的操作数，用辅助数组存放，然后转化成浮点数存放到数栈中，遇到“|”则直接将数组下标往后走。遇到字符，则从数栈取出两个数进行计算，将计算的结果从新存放到数栈中，循环直到接到结束。最后存放在数栈中的数就是计算的结果。最后在主函数中调用此函数，进行结果的输出。第二种算法对表达式直接进行计算，也称为边走边计算首先建立一个符号栈，用于存放字符和字符的优先级别；然后建立一个数栈，用于存放数。建立一个计算的函数，该函数用于两个数的计算，在调用这个函数的时候，传入三个参数，两个浮点型参数和一个字符型参数，根据不同的符号进行不同的计算。定义一个判断优先级别的函数，用于判断两个操作符的优先级别，在根据优先级的不同决定不同的操作。边走边计算实现，扫描算术表达式，如果遇到数字或者是小数点，则进行循环的扫描直到将整个数字从字符数组中取出，把取出的字符存放到一个数组中，在利用c语言的函数把这个字符串的数字转化成浮点型的数字，然后存放到数栈中，若果是字符，则将字符的优先级与字符栈中的字符优先级进行比较，若优先级别低于字符栈中的符号优先级别，则从字符栈中取出操作符，再从数栈中取出两个数字，进行计算，计算的结果存放到数栈中，继续检查符号栈中的元素直到遇到优先级别比扫描到的字符优先级别低或者符号栈为空，将扫描到的符号入栈。。若是“（”则无条件入字符栈，若是“）”则从字符栈中出栈字符从数栈中取数进行计算，直到遇到“（”为止。当字符数组扫描到最后的时候，计算并没有结束。然后得进行字符栈的判断，看是否已经为空栈，若不是空栈，则出栈字符，每出栈一个字符就出栈两个数字，进行计算，直到字符栈空为止。最终存放在数栈中的数就是计算的结果。最后在主函数中调用此函数，进行结果的输出。用两种方式实现表达式自动计算-2-二、算法流程图第一种算法：先将中缀表达式转化成后缀表达式，然后计算。图1中缀转后缀流程图图2后缀表达式的计算用两种方式实现表达式自动计算-3-图3直接计算中缀表达式三、源代码先将中缀表达式转化成后缀表达式，在进行后缀表达式的计算，最后将结果显示。下面给出的是用第一种算法实现的的程序的源代码：#includestdio.h#includestdlib.h#includestring.h//创建存放字符的结构体typedefstruct{charch;//定义ch存放操作符intlevel;//定义level存放操作符的优先级}OpNode;//创建字符栈typedefstruct{OpNodeopNode[100];用两种方式实现表达式自动计算-4-inttop;//存放栈顶的数intsize;//存放当前栈的大小}OpStack;//对字符栈的初始化voidOp_init(OpStack*ops){ops-top=0;ops-size=0;}//字符栈的入栈操作voidOp_push(OpStack*ops,OpNodeop){ops-size++;ops-opNode[(ops-top)++]=op;}//字符栈的出栈操作OpNodeOp_pop(OpStack*ops){if(ops-size==0)//判断栈是否为空，如果为空，则退出程序，否则出栈{exit(-1);}ops-size--;returnops-opNode[--(ops-top)];}//看字符栈顶操作OpNodeOp_getTop(OpStack*ops){intlen=ops-size;returnops-opNode[len-1];}//创建存放数的结构体typedefstruct{doubled;//定义d存放操作数}TdNode;//创建数栈typedefstruct{TdNodetdNode[100];intsize;inttop;}TdStack;//数栈的初始化用两种方式实现表达式自动计算-5-voidTd_init(TdStack*tds){tds-size=0;tds-top=0;}//数栈的入栈voidTd_push(TdStack*tds,TdNodetd){tds-size++;tds-tdNode[(tds-top)++]=td;}//数栈的出栈TdNodeTd_pop(TdStack*tds){if(tds-size==0)//判断栈是否为空，如果为空，则退出程序，否则出栈{exit(-1);}tds-size--;returntds-tdNode[--(tds-top)];}//看数栈栈顶TdNodeTd_getTop(TdStack*tds){intlen=tds-size;returntds-tdNode[len-1];}//创建一个返回值为double函数，用于两个数的计算，传入三个变量，//第一个变量为操作数1，第二个变量为操作数2，第三个变量为操作符doubleCal(doublenum_1,doublenum_2,charop){doublenum=0;//定义一个变量用于接收计算的结果switch(op){case'+':num=num_1+num_2;break;case'-':num=num_1-num_2;break;case'*':num=num_1*num_2;break;case'/':if(num_2==0)//如果除数为零，则推出程序并打印错误信息{printf(\ndivisorzerocan't);exit(-1);}elsenum=num_1/num_2;用两种方式实现表达式自动计算-6-}returnnum;}//创建一个返回值为int型的函数，用于比较两个操作符的优先级intCompare_opeate(intlevel_1,intlevel_2){if(level_1=level_2)//判断优先级别，返回相应的值return0;return-1;}//创建一个返回值为double型的函数，用于返回整个表达式的计算结果doubleCalResult(){//charch[]=23+12-34;//charch[]=19-(2*3)+12/2;charch[]=(23-3)/0+12*2;chartempCh[100];//存放后缀表达式intindex=0,i=0;OpStackops;//定义操作符栈TdStacktds;//定义操作数栈OpNodeop;//定义字符节点TdNodetd;//定义数节点Op_init(&ops);//初始化字符栈Td_init(&tds);//初始化操作数栈while(ch[index]!='\0'){charchr=ch[index];if(chr='0'&&chr='9'||chr=='.'){inttempIndex=index;while(chr='0'&&chr='9'||chr=='.')//判断是否为操作数{tempCh[i++]=ch[tempIndex];tempIndex++;chr=ch[tempIndex];}tempCh[i++]='|';//在一个操作数取完之后，后面加分隔符index=tempIndex;continue;}//判断是否为加法或者减法运算if(chr=='+'||chr=='-'){op.ch=chr;//存放操作符到操作符节点用两种方式实现表达式自动计算-7-op.level=2;//给操作符赋值优先级intlevel_2=2;//存放优先级别，用于比较优先级while(ops.size!=0)//若字符栈不为空，则进行字符的优先级比较{intlevel_1=Op_getTop(&ops).level;//两个字符比较优先级，若新的字符优先级比栈中的字符优先级高，则//从字符栈中字符出栈，将出栈的字符放到后续数组中if(Compare_opeate(level_1,level_2)==0){charop1=Op_pop(&ops).ch;tempCh[i++]=op1;tempCh[i++]='|';}else{Op_push(&ops,op);break;}}if(ops.size==0)//若字符栈是空栈，则直接进行入栈的操作{Op_push(&ops,op);}index++;continue;}//判断是否为乘法或者除法的运算符if(chr=='*'||chr=='/'){op.ch=chr;//存放操作符到操作符节点op.level=3;//给操作符赋值优先级intlevel_2=3;//存放优先级别，用于比较优先级while(ops.size!=0){intlevel_1=Op_getTop(&ops).level;//两个字符比较优先级，若新的字符优先级比栈中的字符优先级高，则//从字符栈中字符出栈，将出栈的字符放到后续数组中if(Compare_opeate(level_1,level_2)==0){charop1=Op_pop(&ops).ch;tempCh[i++]=op1;tempCh[i++]='|';}else用两种方式实现表达式自动计算-8-{Op_push(&ops,op);break;}}if(ops.size==0)//若字符栈是空栈，则直接进行入栈的操作{Op_push(&ops,op);}index++;continue;}//判断是否为左括号，直接进行入栈操作if(chr=='('){op.ch=chr;op.level=-1;Op_push(&ops,op);index++;continue;}//判断是否为右括号if(chr==')'){charch1=Op_getTop(&ops).ch;//进行出栈的操作，知道遇到左括号为止。将出栈的字符加入后续字符中while(ch1!='('){charop1=Op_pop(&ops).ch;tempCh[i++]=op1;tempCh[i++]='|';ch1=Op_getTop(&ops).ch;}Op_pop(&ops);index++;continue;}}/