计算机科学与技术学院
实验报告
课程名称:数据结构与算法
课程类型:必修课
实验项目名称:线性表及其应用
实验题目:中缀表达式转换为后缀表达式并求值
一、 实验目的
1、 熟练使用线性表。
2、 利用“栈”,将中缀表达式转换成后缀表达式并求值。
设计成绩
报告成绩
指导老师
3、 有意识地使程序具有一定的容错能力,能够在一定程度上
应对非法输入。
二、 实验要求及实验环境
实验要求:
1、使用“栈”来进行设计、编写程序;
2、输入恰当的中值表达式时,能够输出正确的后缀表达式并其
进行求值;
3、有较好的容错能力。
实验环境:Codeblocks10.05 / Windows 7
三、设计思想(本程序中的用到的所有数据类型的定义,主
程序的流程图及各程序模块之间的调用关系)
1.逻辑设计
具体实现过程是先创建一个符号栈,用于存放字符及字符的优先级别,再
建立一个操作数栈,用于辅助后缀表达式的计算的实现;定义一个字符串
数组,用于存放后缀表达式;建立一个计算的函数,该函数用于两个数的
计算;定义一个判断优先级别的函数,用于判断两个操作符的优先级,根
据优先级的不同,确定不同的操作行为。
对中缀表达式的字符逐个扫描,进行恰当的判断,确定正确后缀表达式。
如果是数字(或小数点)则继续判断,知道数字结束,并且同时存到字符
数组中去,并且在存放过程中附加了一个“ ”,使得输出时便于识任,
若是操作符,则和栈中得操作符进行比较,若扫描到的操作符优先级比栈
内的操作符优先级低,则栈中元素弹栈并存放到字符数组中。同时检查栈
顶,比较其优先级,直到栈中元素的优先级比扫描到的操作符优先级低或
者此时操作符为空,则将此操作符压栈。若是“(”则无条件入栈,若是
“)”则从字符栈中出字符直到遇到“(”为止。当字符数组扫描到最后的
时候,进行字符栈的判断,看是否为空栈,若不是空栈,则出栈所有字符,
并将字符存放到数组中。最后字符串数组中存放的即为后缀表达式。得到
后缀表达式后,利用数栈进行后缀表达式的计算,对新的数组进行扫描,
同时进行相关的判断,如果遇到数字,以“ ”为标记取出完整的操作数,
用辅助数组存放,然后转化为浮点数存放到数栈中,遇到“ ”则直接往
后走。遇到字符,则从数栈取出两个数进行计算,将计算的结果重新存放
到数栈中,直到循环结束。最后存放在数栈中的数即为计算的结果。最后
在主函数中调用此函数,进行结果的输出。
再谈一下容错的设计,在对输入的字符串进行逐个判断时,会统计“(”、
“)”个数是否一致,操作符是否连续出现(例:++,+*,\*等),除数是
否为零等错误输入并给出错误提示。
2.物理设计
主要数据类型
Stack ops, tds; Stack 是自己写的栈,使用它定义了操作符栈和操
作数栈
char tmpCh[100]; 这一字符数组用于存放后缀表达式
Node op, td; Node 是一个 Struct,包含字符型,整形,浮点型数
据各一个,用它定义了字符节点和操作数节点
流程图:
三、 测试结果
1、正常输入
2、除数为零
3、操作符的连续出现
4、括号不匹配
四、 系统不足与经验体会
程序的某些函数较为冗杂,表现为个别函数语句过多,