中缀表达式转后缀表达式报告精选.doc

目录 1. 课题分析 1 1．1设计目的 1 1．2主要内容 1 1．2．1中缀表达式转换为后缀表达式 1 1．2．2后缀表达式求值 2 1．3设计要求 2 2.总体设计 2 2．1数据类型的定义 2 2．2主程序的流程 3 3．详细设计（源代码） 5 4．调试分析 14 4．1问题1 14 4．2问题2 15 4．3问题3 15 5．测试结果 15 6．心得体会 16 7．参考文献 16 课题分析 1．1设计目的 （1）掌握栈“后进先出”的特点。 （2）掌握栈的典型应用——中缀表达式转后缀表达式，并利用后缀表达式求值。 （3）掌握串或者数组的相关操作。 1．2主要内容 1．2．1中缀表达式转换为后缀表达式 （1）定义一个运算符栈，并输入一个中缀表达式（运算对象存在多位整数，运算符为+、-、*、/、%及括号），然后从中缀表达式中自左至右依次读入各个字符。 （2）如果是第一次读入运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算符，则先输出逗号作为分隔符，然后再将该运算对象输出到后缀表达式。 （3）如果读入的是运算符，并且运算符栈为空，则将该运算符直接进栈；如果栈不为空，则比较该运算符和栈顶运算符的优先级。 若该运算符高于栈顶运算符的优先级，则将该运算符直接进栈；若该运算符低于或等于栈顶运算符的优先级，则将栈中高于或等于该运算符优先级的元素依次出栈，然后再将该运算符进栈。每出栈一个运算符时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。 （4）如果读入的是开括号“（”，则直接进栈；如果读入的是闭括号“）”，则一直出栈并输出到后缀表达式，知道遇到一个开括号“（”为止。开括号“（”和闭括号“）”均不输出到后缀表达式。 （5）重复②、③、④步，知道中缀表达式结束，然后将栈中剩余的所有运算符依次出栈。每出栈一个运算符时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。 （6）给后缀表达式加上‘\0’作为字符串结束标志。 1．2．2后缀表达式求值 （1）定义一个double型的运算数栈，将中缀表达式转换得到的后缀表达式字符串自左向右依次读入。 （2）如果读入的是运算对象，则将该运算对象串（下一个逗号分隔符前的部分所构成的数字字符串）转换为对应的多位整数值，然后将该整数值（将自动类型转换为double型）直接进入运算数栈。 （3）如果读入的是运算符，则立即从运算数栈中弹出两个运算数，计算两个运算数运算后的值（运算时先出栈的元素放在运算符后面，后出栈的元素放在运算符前面），并将计算结果存回运算数栈。 （4）重复②、③步，直到后缀表达式结束，最后栈中保存的那个数即为该后缀表达式的计算结果。 （5）和手工计算的结果进行比较，检验程序运行结果的正确性。 假设输入中缀表达式为：（123+32）/5*2-15*18/（2+4）/15-7。 转换后的后缀表达式为：123，32，+，5，/，2，*，15，18，*，2，4，+，/，15，/，-，7，-。 后缀表达式求得的值为：52。 1．3设计要求 （1）运算对象存在多位整数。 （2）遇到除数为0的情况，应能给出相应提示，并提醒重新输入中缀表达式。 （3）%运算符左右遇到非整数时，应能自动对其进行取整；%运算符左右遇到负数时，应能给出相应提示，并提醒重新输入中缀表达式。 （4）如果有两个同学同时完成该课题，要求分别采用顺序和链式结构实现其栈。 2.总体设计 2．1数据类型的定义 calcolate（）：依次扫描string2中的字符，遇到数字则将其转化为整型数据存入栈中，遇运算符则将栈中栈顶的两个元素取出参与运算，并将计算结果放入栈中，如此直到运算符全部用完，最后一次运算结果即为后缀表达式的计算结果。 2．2主程序的流程 先把算术表达式转化成后缀表达式，在对后缀表达式进行计算。 首先建立一个符号栈，用于存放字符和字符的优先级别；然后在建立一个数栈，用于辅助后缀表达式的计算；最后在定义一个字符串数组，用于存放后缀表达式。建立一个计算的函数，该函数用于两个数的计算，在调用这个函数的时候，传入三个参数，两个浮点型参数和一个字符型参数，根据不同的符号进行不同的计算。定义一个判断优先级别的函数，用于判断两个操作符的优先级别，在根据优先级的不同决定不同的操作。 后缀表达式的取得，对算术表达式字符串进行挨个的扫描，如果是数字或者是小数点， 则将数字或者小数点存放到字符数组中，每取完一个数字，则在后面用“|”隔开，如果是操作符，则和栈中得操作符进行比较，若扫描到的符号优先级比栈里的符号优先级低，则栈中元素出栈并存放到字符数组中