表达式求值数据结构实训报告

1、数据结构实训总结报告题 目：学生姓名： 学生学号: 专业班级: 指导老师:表达式求值目录1. 课题分析1. 1需求分析1. 2设计要求2总体设计2. 1主程序的流程3详细设计（步骤及代码实现）3. 1判断运算符优先级3. 2中缀表达式转后缀表达式3. 3后缀表达式求值4. 测试结果5. 心得体会6. 参考文献1课题分析11需求分析(1) 栈“后进先出”的特点。并利用后缀表达式求值。(2) 屮缀表达式转后缀表达式,1. 2设计要求(1) 运算对象存在多位整数。(2) 实现表达式错误的报错。(3) 判断运算符优先级。(4) 中缀表达式转后缀表达式。2总体设计2. 1主程序的流程string2屮存放

2、转 化好的后缀表达后缀表达式结果的计 算i+输出运算结果3详细设计(步骤及代码实现)3. 1判断运算符优先级(乘除优先于加减)int sqstack:cmp(char ch)switch(ch)casecase l，: return 1;casecase 71: return 2; default: return 0;3. 2中缀表达式转后缀表达式(1) 首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；(2) 定义一个运算符栈，并输入一个中缀表达式(运算对象存在多位整数，运 算符为+、-、*、/、及括号)，然后从中缀表达式中自左至右依次读入各个字符。(3) 在字符串si读取到的运

3、算对象直接输送到后缀表达式字符串s2,两相邻 操作数之间利用空格隔开。(4) 如果读入的是运算符，并且运算符栈为空，则将该运算符直接进栈；如果 栈不为空，则比较该运算符和栈顶运算符的优先级。若该运算符高于栈顶运算符的优先级，则将该运算符直接进栈；若该运算 符低于或等于栈顶运算符的优先级，则将栈中高于或等于该运算符优先级的元素 依次岀栈，然后再将该运算符进栈。出栈的运算符输入到s2中，利用空格隔开。(5) 如果读入的是开括号“(”，则直接进栈；如果读入的是闭括号“)”，则一 直出栈并输出到后缀表达式，知道遇到一个开括号“(”为止。开括号“(”和闭 括号“)”均不输岀到后缀表达式。(6) 重复34

4、5步，肓到中缀表达式结束，然后将栈中剩余的所有运算符依次出 栈。void sqstack:change(string &sl, string &s2)stack <char> s;s.push('#');int i = 0;while(i < sl.length()if(sli = t)s.push(sli+j)； else= t)while( s.top() !='(')s2 += s.top(); s2 += * s.pop();s.pop(); i+；elseif( sli=屮 | sli = *- |sli =*! |

5、sli = 71)while( cmp(s.top() >= cmp(sli)s2 += s-top(); s2 + 二' s.pop(); s.push(sli);i+；elsewhileco' <= sli&&sli <= 9| |sli= s2 + 二 sli+;s2 + 二 * ;while(s.top() != #)s2 += s.top();s2 + 二 1 *;s.pop();3. 3后缀表达式求值(1)定义一个double型的运算数栈，将中缀表达式转换得到的后缀表达式字符 串自左向右依次读入。(2) 如果读入的是运算对象，则将该

6、运算对象串(下一个逗号分隔符前的部分 所构成的数字字符串)转换为对应的多位整数值，然后将该整数值(将自动类型 转换为double型)直接进入运算数栈。(3) 如果读入的是运算符，则立即从运算数栈中弹岀两个运算数，计算两个运 算数运算后的值(运算时先出栈的元素放在运算符后面，后出栈的元素放在运算 符前面)，并将计算结果存回运算数栈。(4) 重复2、3步，直到后缀表达式结束，最后栈中保存的那个数即为该后缀表 达式的计算结果。double sqstack:value(string &s2)stack <double> s;double x,y;int i = 0;while(i

7、< s2.length()-l)if(s2i =1 *)i+；switch(s2i)caseif (s.size()>=2) x = s.top(); s.pop(); x += s.top(); s.pop(); i+； break; else return 0;caseif(s.size()>=2)x = s.top(); s.pop(); x =s.top()-x; s.pop(); i+; break; else return 0;caseif (s.size()>=2)x = s.top(); s.pop(); x *= s.top(); s.pop(); i

8、+; break; else return 0;caseif (s.size()>=2)x = s.top(); s.pop(); x = s.top()/x; s.pop(); i+; break;else return 0;default:x = 0;whileco' <= s2i&&s2i <= 9)x = x*10+s2i -'o'i+；if(s2i = 7)double k = 10.0;y = 0;i+；whileco' <= s2i&&s2i <= 9)y+= (s2i.'0&#

9、39;)/k);i+； k *= 10;x+= y; break;s.push(x);if( s.size()=l)return s.top();elsereturn 0;int main()string sl,s2;sqstack t;cout«"请输入中缀表达式：”；cin> >sl;s2="t.cha nge(sl,s2);if (t.value(s2)collt«"后缀表达式为 cout«s2«endl;coutvv”表达式的值为：n; cout«fixed«setprecisi on

10、 (2)«t.value(s2)«e ndl;elsecout«"a wrong input!"«endl;return 0;4测试结果12-3*5 3 5 * -00 cont inueo t yky 中达的an 入表式s r3表为为ke式达« 表为为ke 費值y 中达的an 入al式s nes 注普表pr:<2*5>/9 5 9 /78 continue5 心得体会通过这该程序的编写，我发现了学习上的挺多问题，尤其在遇到指针的问题 的时候，很茫然，以后在学习中要多注意指针的使用，以达到熟练掌握的程度, 平时的学习中一定要多写程序，多写一些才回把知识用得自然。这次实验中我熟 练掌握了栈的应用，并练习了串与数组的相关操作。其实大一就开始学习c语言，可是，当时学的时候就觉得语言好像是学会了, 可是一遇到编程的问题还是头大，总感觉没有什么思路，而这次作业，给自己一 个不得不动手操作的机会，在十一的这儿天中，复习了以前学过的c的基本知识, 然后一点一点的摸索，遇到了错误和同学一起讨论，有问题自己想办法解决，最 后程序调试出来的时候，会觉得真的很高兴。我知道，我们现在的水平还很差, 要想学习好这门课，在以后就要多动手操作，书上的例题或算法，最好都自己编 写程序实