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

用两种方式实现表达式自动计算目 录一、设计思想.01二、算法流程图.02三、源代码.03四、运行结果.16五、遇到的问题及解决.17六、心得体会.18一、设计思想第一种算法先把算术表达式转化成后缀表达式，在对后缀表达式进行计算。首先建立一个符号栈，用于存放字符和字符的优先级别；然后在建立一个数栈，用于辅助后缀表达式的计算；最后在定义一个字符串数组，用于存放后缀表达式。建立一个计算的函数，该函数用于两个数的计算，在调用这个函数的时候，传入三个参数，两个浮点型参数和一个字符型参数，根据不同的符号进行不同的计算。定义一个判断优先级别的函数，用于判断两个操作符的优先级别，在根据优先级的不同决定不同的操作。后缀表达式的取得，对算术表达式字符串进行挨个的扫描，如果是数字或者是小数点，则将数字或者小数点存放到字符数组中，每取完一个数字，则在后面用“|”隔开，如果是操作符，则和栈中得操作符进行比较，若扫描到的符号优先级比栈里的符号优先级低，则栈中元素出栈并存放到字符数组中。每出一个字符到字符数组中就在后面加“|”分隔。继续检查栈顶比较优先级，直到栈中元素优先级比扫描到的符号优先级低或者符号栈为空，则将此操作符入栈。若是“（”则无条件入字符栈，若是“）”则从字符栈中出字符直到遇到“（”为止。当字符数组扫描到最后的时候，计算并没有结束。然后得进行字符栈的判断，看是否已经为空栈，若不是空栈，则出栈字符，将字符存放到数组中。最后字符串数组中存放的就是后缀表达式。得到后缀表达式后，要用数栈进行后缀表达式的计算，后缀表达式的计算中，对新的数组进行从道到尾的扫描，如果遇到数字，以“|”为标记取出完整的操作数，用辅助数组存放，然后转化成浮点数存放到数栈中，遇到“|”则直接将数组下标往后走。遇到字符，则从数栈取出两个数进行计算，将计算的结果从新存放到数栈中，循环直到接到结束。最后存放在数栈中的数就是计算的结果。最后在主函数中调用此函数，进行结果的输出。第二种算法对表达式直接进行计算，也称为边走边计算首先建立一个符号栈，用于存放字符和字符的优先级别；然后建立一个数栈，用于存放数。建立一个计算的函数，该函数用于两个数的计算，在调用这个函数的时候，传入三个参数，两个浮点型参数和一个字符型参数，根据不同的符号进行不同的计算。定义一个判断优先级别的函数，用于判断两个操作符的优先级别，在根据优先级的不同决定不同的操作。边走边计算实现，扫描算术表达式，如果遇到数字或者是小数点，则进行循环的扫描直到将整个数字从字符数组中取出，把取出的字符存放到一个数组中，在利用c语言的函数把这个字符串的数字转化成浮点型的数字，然后存放到数栈中，若果是字符，则将字符的优先级与字符栈中的字符优先级进行比较，若优先级别低于字符栈中的符号优先级别，则从字符栈中取出操作符，再从数栈中取出两个数字，进行计算，计算的结果存放到数栈中，继续检查符号栈中的元素直到遇到优先级别比扫描到的字符优先级别低或者符号栈为空，将扫描到的符号入栈。若是“（”则无条件入字符栈，若是“）”则从字符栈中出栈字符从数栈中取数进行计算，直到遇到“（”为止。当字符数组扫描到最后的时候，计算并没有结束。然后得进行字符栈的判断，看是否已经为空栈，若不是空栈，则出栈字符，每出栈一个字符就出栈两个数字，进行计算，直到字符栈空为止。最终存放在数栈中的数就是计算的结果。最后在主函数中调用此函数，进行结果的输出。二、算法流程图第一种算法：先将中缀表达式转化成后缀表达式，然后计算。图1中缀转后缀流程图图 2 后缀表达式的计算图 3 直接计算中缀表达式三、源代码先将中缀表达式转化成后缀表达式，在进行后缀表达式的计算，最后将结果显示。下面给出的是用第一种算法实现的的程序的源代码：#include #include #include /创建存放字符的结构体 typedef structchar ch;/定义ch 存放操作符 int level;/定义level 存放操作符的优先级 OpNode;/创建字符栈 typedef structOpNode opNode100;int top;/存放栈顶的数 int size;/存放当前栈的大小 OpStack;/对字符栈的初始化 void Op_init(OpStack *ops)ops-top = 0;ops-size = 0;/字符栈的入栈操作 void Op_push(OpStack *ops,OpNode op)ops-size+;ops-opNode(ops-top)+ = op;/字符栈的出栈操作 OpNode Op_pop(OpStack *ops)if(ops-size = 0)/判断栈是否为空，如果为空，则退出程序，否则出栈exit(-1);ops-size-;return ops-opNode-(ops-top);/看字符栈顶操作 OpNode Op_getTop(OpStack *ops)int len = ops-size;return ops-opNodelen - 1;/创建存放数的结构体 typedef structdouble d;/定义 d 存放操作数 TdNode;/创建数栈 typedef structTdNode tdNode100;int size;int top;TdStack;/数栈的初始化 void Td_init(TdStack *tds)tds-size = 0; tds-top = 0;/数栈的入栈 void Td_push(TdStack *tds,TdNode td)tds-size+;tds-tdNode(tds-top)+ = td;/数栈的出栈 TdNode Td_pop(TdStack *tds)if(tds-size = 0)/判断栈是否为空，如果为空，则退出程序，否则出栈exit(-1);tds-size-;return tds-tdNode-(tds-top);/看数栈栈顶 TdNode Td_getTop(TdStack *tds)int len = tds-size;return tds-tdNodelen - 1;/创建一个返回值为double函数，用于两个数的计算，传入三个变量，/第一个变量为 操作数1，第二个变量为操作数2，第三个变量为操作符 double Cal(double num_1,double num_2,char op)double num = 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(ndivisor zero cant);exit(-1); elsenum = num_1 / num_2;return num;/创建一个返回值为int型的函数，用于比较两个操作符的优先级 int Compare_opeate(int level_1,int level_2)if(level_1 = level_2)/判断优先级别，返回相应的值 return 0;return -1;/创建一个返回值为double型的函数，用于返回整个表达式的计算结果 double CalResult()/char ch = 23+12-34;/char ch = 19-(2*3)+12/2;char ch = (23-3)/0+12*2;char tempCh100; /存放后缀表达式 int index = 0,i = 0;OpStack ops;/定义 操作符栈 TdStack tds;/定义 操作数栈 OpNode op;/定义 字符节点 TdNode td;/定义 数节点 Op_init(&ops);/初始化字符栈 Td_init(&tds);/初始化操作数栈 while(chindex != 0)char chr = chindex;if(chr = 0 & chr = 0 & chr = 0 & cc = 0 & cc = 9 | cc = .)asschi+ = tempChtempIndex;tempIndex+;cc = tempChtempIndex;td.d = atof(assch);Td_push(&tds,td); /将取出的操作数入栈 k = tempIndex;continue;else if(cc = |) / 如是 | 则直接跳过 k+;else / 如果是字符，则出栈两个数 进行计算 char op1 = cc;double num_2 = Td_pop(&tds).d;double num_1 = Td_pop(&tds).d;double num = Cal(num_1,num_2,op1);td.d = num;Td_push(&tds,td);k+;return Td_pop(&tds).d;main()double result = CalResult(); /调用函数，得到计算的结果 printf(nResult is ：);printf(%.2f,result);第二种算法对中缀表达式直接进行计算，并将结果输出，实现的源代码：#include #include #include /创建存放字符的结构体 typedef structchar ch; /定义ch 存放操作符 int level;/定义level 存放操作符的优先级 OpNode;/创建字符栈 typedef structOpNode opNode100;int top;/存放栈顶的数 int size;/存放当前栈的大小 OpStack;/对字符栈的初始化 void Op_init(OpStack *ops)ops-top = 0;ops-size = 0;/字符栈的入栈操作 void Op_push(OpStack *ops,OpNode op)ops-size+;ops-opNode(ops-top)+ = op;/字符栈的出栈操作 OpNode Op_pop(OpStack *ops)if(ops-size = 0)/判断栈是否为空，如果为空，则退出程序，否则出栈 exit(-1);ops-size-;return ops-opNode-(ops-top);/看字符栈顶操作 OpNode Op_getTop(OpStack *ops)int len = ops-size;return ops-opNodelen - 1;/创建存放数的结构体 typedef structdouble d;/定义 d 存放操作数 TdNode;/创建数栈 typedef structTdNode tdNode100;int size;int top;TdStack;/数栈的初始化 void Td_init(TdStack *tds)tds-size = 0; tds-top = 0;/数栈的入栈 void Td_push(TdStack *tds,TdNode td)tds-size+;tds-tdNode(tds-top)+ = td;/数栈的出栈 TdNode Td_pop(TdStack *tds)if(tds-size = 0)/判断栈是否为空，如果为空，则退出程序，否则出栈 exit(-1);tds-size-;return tds-tdNode-(tds-top);/看数栈栈顶 TdNode Td_getTop(TdStack *tds)int len = tds-size;return tds-tdNodelen - 1;/创建一个返回值为double函数，用于两个数的计算，传入三个变量，/第一个变量为 操作数1，第二个变量为操作数2，第三个变量为操作符 double Cal(double num_1,double num_2,char op)double num = 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(divisor zero cant);exit(-1); elsenum = num_1 / num_2;return num;/创建一个返回值为int型的函数，用于比较两个操作符的优先级 int Compare_opeate(int level_1,int level_2)if(level_1 = level_2)/判断优先级别，返回相应的值 return 0;return -1;/创建一个返回值为double型的函数，用于返回整个表达式的计算结果 double CalResult()/char ch = 23+12-34;char ch = 19-(2*3)+12/0;/char ch = (23-3)/2+12*2;int index = 0; /定义字符串的索引 OpStack ops;/定义 操作符栈 TdStack tds;/定义 操作数栈 OpNode op;/定义 字符节点 TdNode td;/定义 数节点 Op_init(&ops);/初始化字符栈 Td_init(&tds);/初始化操作数栈 while(chindex != 0)char chr = chindex; /取出字符串的而一个字符 if(chr = 0 & chr = 0 & chr = 9 | chr = .) tempChi+ = chtempIndex;tempIndex+;chr = chtempIndex;td.d = atof(tempCh); Td_push(&tds,td);/把取出的操作数存放到操作数栈 index = tempIndex;continue;/判断是否为加法或者减法运算 if(chr = + | chr = -)op.ch = chr;/存放操作符到操作符节点 op.level = 2; /给操作符赋值优先级 int level_2 = 2; /存放优先级别，用于比较优先级 while(ops.size != 0) /若字符栈不为空，则进行字符的优先级比较 int level_1 = Op_getTop(&ops).level;/两个字符比较优先级，若新的字符优先级比栈中的字符优先级高，则/从字符栈中字符出栈，同时从数栈中出栈两个数，进行计算，计算结/果存入数栈,否则将新的字符入栈 if(Compare_opeate(level_1,level_2) = 0)char op1 = Op_pop(&ops).ch;double num_2 = Td_pop(&tds).d;double num_1 = Td_pop(&tds).d;double num = Cal(num_1,num_2,op1);td.d = num;Td_push(&tds,td);elseOp_push(&ops,op);break;if(ops.size = 0) /若字符栈是空栈，则直接进行入栈的操作 Op_push(&ops,op);index+;continue;/判断是否为乘法或者除法的运算符 if(chr = * | chr = /)op.ch = chr; /存放操作符到操作符节点 op.level = 3; /给操作符赋值优先级 int level_2 = 3;/存放优先级别，用于比较优先级while(ops.size != 0)int level_1 = Op_getTop(&ops).level;/两个字符比较优先级，若新的字符优先级比栈中的字符优先级高，则/从字符栈中字符出栈，同时从数栈中出栈两个数，进行计算，计算结/果存入数栈,否则将新的字符入栈 if(Compare_opeate(level_1,level_2) = 0)char op1 = Op_pop(&ops).ch;double num_2 = Td_pop(&tds).d;double num_1 = Td_pop(&tds).d;double num = Cal(num_1,num_2,op1);td.d = num;Td_push(&tds,td);elseOp_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 = )char ch1 = Op_getTop(&ops).ch;/进行出栈的操作，知道遇到左括号为止。 while(ch1 != ()char op1 = Op_pop(&ops).ch;double num_2 = Td_pop(&tds).d;double num_1 = Td_pop(&tds).d;double num = Cal(num_1,num_2,op1);td.d = num;Td_push(&tds,td);ch1 = Op_getTop(&ops).ch;Op_pop(&ops);index+;continue;/如果字符栈不为空，则一直出栈直到字符栈为空。 while(ops.size != 0)char op1 = Op_pop(&ops).ch;double num_2 = Td_pop(&tds).d;double num_1 = Td_pop(&tds).d;double num = Cal(num_1,num_2,op1);td.d = num;Td_push(&tds,td);/将结果出栈返回 return Td_pop(&tds).d;main()double result = CalResult(); /调用函数，得到计算的结果 printf(Result is :);printf(%.2f,result);四、运行结果中缀表达式直接进行计算的运行结果如下：图 4 中缀表达式直接计算后缀转中缀再进行计算的运行结果如下：图 5 后缀表达式计算结果五、遇到的问题及解决l 问题1：从字符数组中截取出数字的操作，并转化成浮点型的数不正确。计算的结果有时候是一个意想不到的很大的数。问题1的解决方法：从字符数数组中将数字截取出来就是为了能进行计算，而数字是单个字符的形式存在，必须把一个完整的数从算术表达式中截取出来，如果遇到数字的字符就是一个数字的入口，然后循环取出直到遇到不是数字或者小数点为止。而这些取出的数字是一堆离散的数字字符。这时候就需要建立一个辅助的数组来存放这些数字字符以组成一个数字的字符。用一个辅助的索引将数字的组成字符一个一个从数组中取出来，存放到新的数组中，以得到一个字符串的数字。从数组中截取出一个数后，将取出的数用atof 函数进行转化成浮点型的数。在把浮点型的数存放到数栈中，在后面的计算中取出。在调试中第一个取出的浮点型数是正确的，当遇到后面截取的数的长度比第一个数短的时候，发现取出的数和第一个数的位数相同了。经过分析，每次截取完数字后并没有对辅助数组进行重新的初始化，数组中宗存放着前一个字符，一旦遇到数字比前面的数字短的的情况，后面的数字只覆盖了前面的数字的前几位，后面的几位都是原先的数字。造成取出的结果是错误的。解决问题的方法可以在每次存放数字之前，把辅助数组进行初始化，结果能正确计算表达式。l 问题2：如何生成后缀表达式，将数与字符存放在一个字符串中。问题2的解决方法：想把数字从字符数组中取出来，然后再存入后缀表达式中，从字符数组中取出是很容易的，但是在把这些数字和操作符进行存入一个后缀表达式数的时候出现了问题，因为c 语言中没有这样的字符数组，所以取出的数字根本没法和操作符一块存到一个数组中去。改变一种想问题的方法，就是不把字符数组的数字都截取出来，而是把数字进行一个分割，让数字还依旧存放在数组中，只是在每个数字的后面都加上一个分割符号“|”