中缀表达式转后缀表达式报告

《中缀表达式转后缀表达式报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实用数据结构基础课程设计报告目录1.课题分析11．1设计目的11．2主要内容11．2．1中缀表达式转换为后缀表达式11．2．2后缀表达式求值21．3设计要求22.总体设计22．1数据类型的定义22．2主程序的流程33．详细设计（源代码）54．调试分析144．1问题1144．2问题2154．3问题3155．测试结果156．心得体会167．参考文献1610实用数据结构基础课程设计报告1.课题分析1．1设计目的（1）掌握栈“后进先出”的特点。（2）掌握栈的典型应用——中缀表达式转后缀表达式，并利用后缀表

2、达式求值。（3）掌握串或者数组的相关操作。1．2主要内容1．2．1中缀表达式转换为后缀表达式（1）定义一个运算符栈，并输入一个中缀表达式（运算对象存在多位整数，运算符为+、-、*、/、%及括号），然后从中缀表达式中自左至右依次读入各个字符。（2）如果是第一次读入运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算符，则先输出逗号作为分隔符，然后再将该运算对象输出到后缀表达式。

3、（3）如果读入的是运算符，并且运算符栈为空，则将该运算符直接进栈；如果栈不为空，则比较该运算符和栈顶运算符的优先级。若该运算符高于栈顶运算符的优先级，则将该运算符直接进栈；若该运算符低于或等于栈顶运算符的优先级，则将栈中高于或等于该运算符优先级的元素依次出栈，然后再将该运算符进栈。每出栈一个运算符时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。（4）如果读入的是开括号“（”，则直接进栈；如果读入的是闭括号“）”，则一直出栈并输出到后缀表达式，知道遇到一个开括号“（”为

4、止。开括号“（”和闭括号“）”均不输出到后缀表达式。（5）重复②、③、④步，知道中缀表达式结束，然后将栈中剩余的所有运算符依次出栈。每出栈一个运算符时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。（6）给后缀表达式加上‘’作为字符串结束标志。1．2．2后缀表达式求值（1）定义一个double型的运算数栈，将中缀表达式转换得到的后缀表达式字符串自左向右依次读入。（2）如果读入的是运算对象，则将该运算对象串（下一个逗号分隔符前的部分所构成的数字字符串）转换为对应的多位

5、整数值，然后将该整数值（将自动类型转换为double型）直接进入运算数栈。10实用数据结构基础课程设计报告（3）如果读入的是运算符，则立即从运算数栈中弹出两个运算数，计算两个运算数运算后的值（运算时先出栈的元素放在运算符后面，后出栈的元素放在运算符前面），并将计算结果存回运算数栈。（4）重复②、③步，直到后缀表达式结束，最后栈中保存的那个数即为该后缀表达式的计算结果。（5）和手工计算的结果进行比较，检验程序运行结果的正确性。假设输入中缀表达式为：（123+32）/5*2-15*18/（2+4）/1

6、5-7。转换后的后缀表达式为：123，32，+，5，/，2，*，15，18，*，2，4，+，/，15，/，-，7，-。后缀表达式求得的值为：52。1．3设计要求（1）运算对象存在多位整数。（2）遇到除数为0的情况，应能给出相应提示，并提醒重新输入中缀表达式。（3）%运算符左右遇到非整数时，应能自动对其进行取整；%运算符左右遇到负数时，应能给出相应提示，并提醒重新输入中缀表达式。（4）如果有两个同学同时完成该课题，要求分别采用顺序和链式结构实现其栈。2.总体设计2．1数据类型的定义calcolate

7、（）：依次扫描string2中的字符，遇到数字则将其转化为整型数据存入栈中，遇运算符则将栈中栈顶的两个元素取出参与运算，并将计算结果放入栈中，如此直到运算符全部用完，最后一次运算结果即为后缀表达式的计算结果。10实用数据结构基础课程设计报告end输出运算结果后缀表达式结果的计算calcolate（）String2中存放转化好的后缀表达式zi++先向string2中存入一个空格，再判断该字符类型。为减价乘除号，判断栈顶元素优先级，比其高，先将栈顶元素出栈到string2中，再将其入栈。为开阔号，直接

8、进栈。为闭括号，将栈顶元素依次弹出存入string2中，直至遇到开阔号。直接存入字符串string2中String1[i]是否为数字string1[i]?='';读入字符串string1[],i=0start2．2主程序的流程先把算术表达式转化成后缀表达式，在对后缀表达式进行计算。首先建立一个符号栈，用于存放字符和字符的优先级别；然后在建立一个数栈，用于辅助后缀表达式的计算；最后在定义一个字符串数组，用于存放后缀表达式。建立一个计算的函数，该函数用于两个数的计算，在调用这个函数