北工大数据结构第二次上机中缀转后缀实验报告

1、北工大数据结构第二次上机中缀转后缀实验报告北京工业大学2016-2017学年第学期信息学部计算机学院课程名称：数据结构与算法报告性质：作业报告，口实验报告学号：姓名：任课教师：苏航课程性质：学科基础必修课学分：3.5学时：56班级：成绩：小组成员：教师评语：2017年3月31日报告题目：输入中缀表达式，输出后缀表达式，并对表达式求值A.分析中缀表达式的运算顺序受运算符优先级和括号的影响。因此，将中缀表达式转换成等价的后缀表达式的关键在于如何恰当的去掉中缀表达式中的括号，然后在必要时按照先乘除后加减的优先规则调换运算符的先后次序。在去括号的过程中用栈来储存有关的元素。基本思路：从左至右顺序扫描中

2、缀表达式，用栈来存放表达式中的操作数，开括号，以及在这个开括号后面的其他暂时不能确定计算次序的内容。（1）当输入的是操作数时，直接输出到后缀表达式（2）当遇到开括号时，将其入栈（3）当输入遇到闭括号时，先判断栈是否为空，若为空，则表示括号不匹配，应作为错误异常处理，清栈退出。若非空，则把栈中元素依次弹出，直到遇到第一个开括号为止，将弹出的元素输出到后缀表达式序列中。由于后缀表达式不需要括号，因此弹出的括号不放到输出序列中，若没有遇到开括号，说明括号不匹配，做异常处理，清栈退出。（4）当输入为运算符时（四则运算+-*/之一）时：a.循环，当（栈非空&&栈顶不是开括号&&a

3、mp;栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作将栈顶元素弹出，放到后缀表达式中。b.将输入的运算符压入栈中。（5）最后，当中缀表达式的符号全部扫描完毕时，若栈内仍有元素，则将其全部依次弹出，放在后缀表达式序列的尾部。若在弹出的元素中遇到开括号，则说明括号不匹配，做异常处理，清栈退出。B.实现#include<stdio.h>#include<string.h>#include<stdlib.h>#include<stack>usingnamespacestd;defineN1000charinfixN;中缀表达式（未分离，都在一

4、个字符串里）charexpressionN10;保存预处理过的表达式，也就是每个元素都分离'a'&&x<='z')|,用字符串数组过的表达式charsuffixN10;保存后缀表达式的操作数intcount;/表达式中元素的个数（一个完整到数字（可能不止一位数）或者符号）intsuffixLength;/后缀表达式的长度intlevel(chara)switch(a)case'#':return0;case'+':case'-':return1;case'*':case'

5、;/':return2;case'A':return3;default:break;return-1;intisDigital(charx)if(x>='0'&&xv=9)|(x>='A'&&xv=Z)|(x>(x='.')return1;return0;intisNumber(char*str)inti;for(i=0;stri;i+)if(isDigital(stri)=0)return0;return1;产*预处理中缀表达式，把连续的字符分离成不同的元素（expres

6、sion口）保存，方便后面的计算，因为这里考虑了运算数可能不全是个位数比如：(12+3)在处理成后缀表达式时，是123+,容易产生歧义(1+23?12+3)*/voidpretreatment(char*str)inti,j,numberFlag;chartemp3;charnumber10;count=0;numberFlag=0;for(j=0,i=0;stri;i+)if(isDigital(stri)=0)if(numberFlag=1)numberj=0;strcpy(expressioncount+,number);j=0；numberFlag=0;if(stri!='&#

7、39;)temp0=stri;temp1=0;strcpy(expressioncount+,temp);elsenumberFlag=1;numberj+=stri;puts("分离后的表达式为");for(i=0;i<count;i+)printf("%s",expressioni);puts("");puts("");产*中缀表达式转后缀表达式遍历字符串，对于stristri是运算数(或者是字母代替的运算变量)输出；stri是符号，有两种情况(1),是右括号，栈顶元素输出，直到与stri匹配的左括号出栈

8、(左括号不用输出打印)(2),是运算符，判断stri与栈顶元素的优先级，stri优先级不高于栈顶符号，则栈顶元素输出，直到栈空或者栈顶符号优先级低于stri*/voidin巾x_to_suffix(charstrN10)memset(sufix,0,sizeof(suffix);suffixLength=0;stack<char*>st;inti=0;charMark2="#"st.push(Mark);doif(isNumber(stri)=1)运算数直接保存到后缀表达式中strcpy(suffixsufixLength+,stri);elseif(stri0

9、='(')/是左括号，直接入栈st.push(stri);elseif(stri0=')')是右括号，栈顶出栈，直到与其匹配的左括号出栈while(strcmp(st.top(),"(")!=0)chartemp10;strcpy(temp,st.top();strcpy(suffixsuffixLength+,temp);st.pop();st.pop();elseif(strcmp(st.top(),"(")=0)/是运算符，且栈顶是左括号，则该运算符直接入栈st.push(stri);else是运算符，且栈顶元素优先

10、级不小于运算符，则栈顶元素一直出栈，直到栈空或者遇到一个优先级低于该运算符的元素while(!st.empty()chartemp10;strcpy(temp,st.top();if(level(stri0)>level(temp0)break;strcpy(suffixsuffixLength+,temp);st.pop();st.push(stri);)i+；while(stri0!=0);while(strcmp(st.top(),"#")!=0)将栈取空结束chartemp10;strcpy(temp,st.top();strcpy(suffixsuffixL

11、ength+,temp);st.pop();)puts("后缀表达式为；for(i=0;i<suffixLength;i+)printfsuffixi);puts(");puts(”)；)*计算后缀表达式的值*/charktN10;intstackTop;voidgetResult(charstrN10)stackTop=0;/*这里要注意，内存的分配方案导致i的位置就在temp9旁边，然后strcpy()函数直接拷贝内存的话，在temp越界情况下会覆盖i的值*/inti;chartemp10;for(i=0;i<suffixLength;i+)if(isNum

12、ber(stri)=1)strcpy(ktstackTop+,stri);elsechara10,b10;doublena,nb,nc;strcpy(a,ktstackTop-1);na=atof(a);stackTop-;strcpy(b,ktstackTop-1);nb=atof(b);stackTop-;if(stri0='+')nc=nb+na;elseif(stri0='-')nc=nb-na;elseif(stri0='*')nc=nb*na;elseif(stri0='/')nc=nb/na;sprintf(temp

13、,"%lf",nc);strcpy(ktstackTop+,temp);puts("nTheresultis:%fn");printf("%sn",ktstackTop-1);intmain()printf("PleaseinputcalculateExpression:n");chartempN;while(gets(infix)strcpy(temp,infix);pretreatment(strcat(temp,"");infix_to_suffix(expression);getResult(su