北京工业大学2016-2017学年第学期信息学部计算机学院课程名称：数据结构与算法报告性质：□作业报告√□实验报告学号：姓名：任课教师：苏航课程性质：学科基础必修课学分：3.5学时：56班级：成绩：小组成员：教师评语：2017年3月31日报告题目：输入中缀表达式，输出后缀表达式，并对表达式求值A．分析中缀表达式的运算顺序受运算符优先级和括号的影响。因此，将中缀表达式转换成等价的后缀表达式的关键在于如何恰当的去掉中缀表达式中的括号，然后在必要时按照先乘除后加减的优先规则调换运算符的先后次序。在去括号的过程中用栈来储存有关的元素。基本思路：从左至右顺序扫描中缀表达式，用栈来存放表达式中的操作数，开括号，以及在这个开括号后面的其他暂时不能确定计算次序的内容。（1）当输入的是操作数时，直接输出到后缀表达式（2）当遇到开括号时，将其入栈（3）当输入遇到闭括号时，先判断栈是否为空，若为空，则表示括号不匹配，应作为错误异常处理，清栈退出。若非空，则把栈中元素依次弹出，直到遇到第一个开括号为止，将弹出的元素输出到后缀表达式序列中。由于后缀表达式不需要括号，因此弹出的括号不放到输出序列中，若没有遇到开括号，说明括号不匹配，做异常处理，清栈退出。（4）当输入为运算符时（四则运算+-*/之一）时：a.循环，当（栈非空&&栈顶不是开括号&&栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作将栈顶元素弹出，放到后缀表达式中。b.将输入的运算符压入栈中。（5）最后，当中缀表达式的符号全部扫描完毕时，若栈内仍有元素，则将其全部依次弹出，放在后缀表达式序列的尾部。若在弹出的元素中遇到开括号，则说明括号不匹配，做异常处理，清栈退出。B．实现#include#include#include#includeusingnamespacestd;#defineN1000charinfix[N];//中缀表达式（未分离，都在一个字符串里）charexpression[N][10];//保存预处理过的表达式，也就是每个元素都分离过的表达式charsuffix[N][10];//保存后缀表达式的操作数intcount;//表达式中元素的个数（一个完整到数字（可能不止一位数）或者符号）intsuffixLength;//后缀表达式的长度intlevel(chara){switch(a){case'#':return0;case'+':case'-':return1;case'*':case'/':return2;case'^':return3;default:break;}return-1;}intisDigital(charx){if((x>='0'&&x<='9')||(x>='A'&&x<='Z')||(x>='a'&&x<='z')||(x=='.'))return1;return0;}intisNumber(char*str){inti;for(i=0;str[i];i++){if(isDigital(str[i])==0)return0;}return1;}/*************************************预处理中缀表达式，把连续的字符分离成不同的元素，用字符串数组（expression[][]）保存，方便后面的计算，因为这里考虑了运算数可能不全是个位数比如：（12+3）在处理成后缀表达式时，是123+，容易产生歧义（1+23?12+3）*************************************/voidpretreatment(char*str){inti,j,numberFlag;chartemp[3];charnumber[10];count=0;numberFlag=0;for(j=0,i=0;str[i];i++){if(isDigital(str[i])==0){if(numberFlag==1){number[j]=0;strcpy(expression[count++],number);j=0;numberFlag=0;}if(str[i]!=''){temp[0]=str[i];temp[1]=0;strcpy(expression[count++],temp);}}else{numberFlag=1;number[j++]=str[i];}}puts("分离后的表达式为");for(i=0;ist;inti=0;charMark[2]...
