数据结构的第二次上机实验作业

《数据结构的第二次上机实验作业》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构实验报告实验名称：简单计算器学生姓名：刘健班级：2013211129班内序号：10学号：2013210796日期：1.实验目的和内容表达式求伉是程序设计语言编译屮最近本的问题，它要求把一个表达式翻译成能够直接求伉的序列。例如用户输入字符串“14+((13-2)*2-11*5>*2”，程序可以自动计算得到最终的结果。在这里，我们将问题简化，假定算数表达式的值均为非负整数常数，不包含变量、小数和字符常量。试设计一个算术四则运算表达式求值的简单计算器。基本要求.•1、操作数均为非负整数常数，操作符仅为+、•、*、八(和)：2、编写mai

2、n函数进行测试。2.程序分析2.1存储结构为了实现运算符有限算法，在程序中应该设计两个栈，分别是运算符栈OPTR,操作数栈OPND。2.2程序流程开始输入待计算表达式i分析待计算表达式字符串，并判断操作符优先级用OPTR栈存储操作符，用OPND栈存储操作数i根据己经处理好的机器序列处理表达式，并求值输出计算结果结束2.3关键算法分析算法1:charPrecede(chartl,chart2)[1]算法功能：判断运算符tl和t2的优先级关系[2]算法基本思想：如：case,:case,-：Jif(tl==,(，

3、

4、tl==,)f='〈';/

5、/tlt2break;优先级阁表：+—*/()+>><<<>>—>><<<>>*>>>><>>A/>>>><>>(<<<<<=)>>>>>><<<<<=[3]算法空间、时间杂度分析：0(1)算法2:boolIsOperator(charc)[1]算法功能：判断c是否为7种运算符之一[2]算法基本思想：boolIsOperator(charc)//判D断？c是?否?为a7种?运?算?符?之?一?switch(c)case'+T:case12:case':case’I、•.case'(’：case’)’：c

6、ase':returntrue;default:returnfalse;)>川switch进行选择判断。[3]算法空间、时间复杂度分析：0(1)算法3:intOperate(inta,charoper,intb)[1]算法功能：将a和b做运算，返回结果[2]算法基本思想：{switch(oper){case':returna+b;case1:returna-b;case':returna*b;default:break:}returna/b;}[3]算法空间、吋间复杂度分析：0(1)算法4:intEvaluateExpression()s

7、tackOPTR,OPND;//设0?H?操Ci作痢?数節栈?和i操Ci作痢?符?栈?inta,b,d,x,i,j;charc;OPTR.pushCr);c=getchar();x二OPTR.top();while(c!=，

8、

9、x!=’#’){if(IsOperator(c)){switch(Precede(x,c)){case/(:OPTR.push(c);c=getchar();break;case，=，:x=OPTR.top0:OPTR.pop();c=getchar();break;case’/:x=OPTR.top()

10、;OPTR.popO;b=OPND.top();OPND.pop0;a=0PND.top():OPND.pop():OPND.push(Operate(a,x,b));}}elseif(c>=0,&&c<=93d:0;while(c>=，0'&&c<=’9’){d=d*10+c」0’：c=getchar0;}OPND.push(cl);}elsecout«〃出？现?非?法&?字?符?〃<〈cndl;exit(0);x=OPTR.top():}x=0PND.top();if(OPND.empty()){cout«〃表括?达?式?不？正y确的

11、〃＜〈endl;exit(0);)returnx;}[1]算法空间、时间复杂度分析：0(n)算法思想：(1)首先置操作数栈为空栈，表达式起始符’力运算符栈的栈底元素；(2)依次读入表达式屮每个字符，若是操作数则进OPND栈，若是运算符则和OPTK栈的栈顶运算符比较优先级后作相应操作。若大于栈顶元素优先级别入栈，若小于栈顶元素优先级别则退出和OPND的操作数进行计算，并把计算结果入OPND栈，直至整个表达式求值完毕(即OPND栈的栈顶元素和当前读入的字符均为“#”)。1.程序运行结果分析实验数据测试：输入的表达式为“3*(1-5)”输出的结

12、果为-12运行正确。2.总结4.1实验的难点和关键点实验难点：(1)怎样解决运算符的优先级问题，在此程序中我构造了charPrecede(chartl,chart2)函数解决了优先级的问题(2