数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序

实习报告实习报告 题目 题目 设计一个演示用运算优先法对算数表达式求值过程的程序 班级 班级 姓名 姓名 学号 学号 完成日期 完成日期 一 一 需求分析需求分析 1 建立运算数栈 SqStack1 和运算符栈 SqStack2 辅助分析算符有限关 系 2 用户输入以 结尾的算数表达式 本程序需要用户自行输入表 达式 运算符可以是加 减 乘 除 括号 以字符形式读入 在读入的同时 完成运算符和运算 数的识别处理 在识别出运算数的同时 要将其字符序列形式转换 成整数形式 3 在程序的适当位置输出运算符栈 运算数栈 输入字符和主要操 作的内容 即演示运算操作 4 测试数据见原题 5 程序执行的命令包括 1 建立算数表达式 2 得到运算表达式的值 3 演示运算过程 二 二 概要设计概要设计 1 设定栈的抽象数据类型定义 设定栈的抽象数据类型定义 ADT Stack 数据对象 D ai ai charSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 约定 an 端为栈顶 a1 端为栈底 基本操作 InitStack int top int stacksize SqStack1 操作数栈 typedef struct char base char top int stacksize SqStack2 操作符栈 2 栈类型栈类型 typedef struct char base char top int stacksize Stack 栈类型 栈的基本操作设置如下 主程序模块主程序模块 运算模块运算模块 栈模块栈模块 void InitStack Stack S top p S size Return TRUE else return FALSE Status Pop Stack else p S top S top S top next e p data S size return TRUE 3 3 运算代码 运算代码 int Operate int a char theta int b 计算表达式值 主要是将大的表达 式转化成小的表达式进行逐步求值 int c if theta c a b else if theta c a b else if theta c a b else c a b return c Operate int result SqStack1 OPND SqStack2 OPTR 求值 char a 0 char theta int b c number 0 IntInitStack OPND CharInitStack OPTR CharPush OPTR a getchar while a CharGetTop OPTR printf 输入字符 c a if In a 不是运算符则进栈 number 0 while In a number number 10 a 48 处理多位整数 z 10 x y a getchar IntPush OPND number printf 主要操作 Push OPND d number else switch Precede a CharGetTop OPTR case theta CharPop OPTR c IntPop OPND b IntPop OPND IntPush OPND Operate b theta c printf 主要操作 Operate d c d b theta c break printf OPND 栈 d OPTR 栈 c n IntGetTop OPND CharGetTop OPTR printf The result is d n IntGetTop OPND 打印输出表达式值 return OK 4 4 主函数和其他函数的代码主函数和其他函数的代码 void main 主函数 使用自定义函数完成功能 SqStack1 s1 OPND SqStack2 s2 OPTR OPND OPTR printf Please enter an expression with a end of n printf The Expression result OPND OPTR char Precede char a char b 运算优先级判断 int i j char Table 8 8 优先级表格 for i 0 i 8 i if Table 0 i a 纵坐标寻找 break for j 0 j 8 j 横坐标寻找 if Table j 0 b break return Table j i int In char c 判断 c 是否为操作符 if c c c c c c c c return 1 如果是操作符返回 1 else return 0 不是 返回 0 5 函数的调用关系图反映了演示程序的层次结构 函数的调用关系图反映了演示程序的层次结构 main result InitStackPushGetTopInPrecedePop 四 调试分析四 调试分析 算术表达式求值程序较为庞大 调试花费时间较多 主要是在 for 循 环和 while 循环时容易出错 对于涉及的循环的操作开始和结束条件设 置很关键 五 用户手册五 用户手册 1 本程序开发环境为 VC 6 0 运行环境为 dos 操作系统 执行文件为 1 exe 2 运行该程序后 产生如下图所示的界面 3 按照提示输入一组表达式 4 输入完成后 按回车键 5 屏幕上打印出对应于该表达式的后缀表达式 6 打印表达式计算结果 六 测试结果六 测试结果 1 2 3 4 七 附录七 附录 源程序文件名清单 1 cpp 主程序 1 exe 可执行文件 stdio h 程序中用到的头文件 stdlib h 程序中用到的头文件 string h 程序中用到的头文件 math h 程序中用到的头文件 程序代码 程序代码 include include include include define STACK INIT SIZE 100 define STACKINCREMENT 10 define ERROR 0 define OK 1 栈模块栈模块 typedef struct SqStack1 运算数栈运算数栈 int base int top int stacksize SqStack1 typedef struct SqStack2 运算符栈运算符栈 char base char top int stacksize SqStack2 void IntInitStack SqStack1 S S base int malloc STACK INIT SIZE sizeof int if S base exit ERROR S top S base S stacksize STACK INIT SIZE void CharInitStack SqStack2 S S base char malloc STACK INIT SIZE sizeof char if S base exit ERROR S top S base S stacksize STACK INIT SIZE int IntGetTop SqStack1 S 取栈顶元素取栈顶元素 int e if S top S base return 0 e S top 1 return e char CharGetTop SqStack2 S 取栈顶元素取栈顶元素 char e if S top S base return 0 e S top 1 return e int IntPush SqStack1 S int e S top e return OK int CharPush SqStack2 S char e S top e return OK int IntPop SqStack1 S int e if S top S base return 0 e S top return e int CharPop SqStack2 S char e if S top S base return 0 e S top return e 运运 算模块算模块 char Precede char a char b 运算优先级判断运算优先级判断 int i j char Table 8 8 优先级表格优先级表格 for i 0 i 8 i if Table 0 i a 纵坐标寻找纵坐标寻找 break for j 0 j 8 j 横坐标寻找横坐标寻找 if Table j 0 b break return Table j i int Operate int a char theta int b 计算表达式值 主要是将大的表计算表达式值 主要是将大的表 达式转化成小的表达式进行逐步求值达式转化成小的表达式进行逐步求值 int c if theta c a b else if theta c a b else if theta c a b else c a b return c Operate int In char c 判断判断 c 是否为操作符是否为操作符 if c c c c c c c c return 1 如果是操作符返回如果是操作符返回 1 else return 0 不是 返回不是 返回 0 int result SqStack1 OPND SqStack2 OPTR 求值求值 char a 0 char theta int b c number 0 IntInitStack OPND CharInitStack OPTR CharPush OPTR a getchar while a CharGetTop OPTR printf 输入字符 输入字符 c a if In a 不是运算符则进栈不是运算符则进栈 number 0 while In a number number 10 a 48 处理多位整数处理多位整数 z 10 x y a getchar IntPush OPND number printf 主要操作 主要操作 Push OPND d number else switch Precede a CharGetTop OPTR case theta CharPop OPTR c IntPop OPND b IntPop OPND IntPush OPND Operate b theta c printf 主要操作 主要操作 Operate d c d b theta c break printf OPND 栈 栈 d OPTR 栈 栈 c n IntGetTop OPND CharG