HUNAN UNIVERSITY 课程实验报告
题目：四则运算表达式求值
学生姓名
学生学号201208010
专业班级计科班
指导老师李晓鸿
完成日期
一、需求分析
（1）输入的形式和输入值的范围：
输入输出格式：
输入：在字符界面上输入一个中缀表达式，回车表示结束。
不对非法输入做处理，即假设输入都是合法的。
（2）输出的形式：
输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和计算结果，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。
（3）测试数据：
输入：21+23*（12-6）
输出：21 23 12 6 -*+
result is 159
二、概要设计
抽象数据类型
由于四则运算表达式中运算符可能有多个后继，而运算的对象无后继，可以采用二叉树来实现把中缀表达式转换为后缀表达式。
数据对象：四则运算符及整数
数据关系：n元运算符有n个后继，运算对象的值无后继
基本操作：
void nextorder(BinNode
二叉树的构建：
void setVal(const Elem& e)
void setLeft(BinNode
inline BinNode
void setRight(BinNode
bool isLeaf()
插入删除操作：
InsertChild(T, p, LR, c);
DestroyBiTree(&T);
DeleteChild(T, p, LR);
经过二叉树的后序遍历后的表达式惊醒运算是满足后进先出的原则，采用栈来实现四则运算表达式的求值。
数据对象：运算符（字符）及整数
数据关系：后进先出
基本操作：
void init_stack()
void push_stack(int x)
void pop_stack()
int top_stack()
bool empty_stack()//判断栈空
bool full_stack()//判断栈满
int getHeadStack()//返回栈顶元素的值
算法的基本思想
先用一个堆栈存储operator（操作符，其中‘#’为运算符栈的栈底元素），遇到数字就不做处理直接放到目的串中，遇到operaor则将其与堆栈顶元素比较优先级，决定是否送到输出串中，直至整个表达式遍历完毕（即运算符栈的栈顶元素和当前读入的字符均为'#'）这样处理之后能得到一个后续的排列，再建立二叉树。
1.当遇到ab+这样的则建立左右结点为a和b且根为+的树并返回根结点
2.当遇到操作符前面只有一个操作数的如c*这样的就建立右子结点为c的根
3.当遇到接点为*的，左结点为上次操作返回的子树的根结点（这种情况下就是合并树的情况）
程序流程
该程序有三个模块组成：
（1）输入模块：输入一个中缀表达式。
（2）求解模块：用上述算法进行转换。
（3）输出模块：输出所求表达式的结果到屏幕上。
三、详细设计
实现概要设计中的数据类型
根据字符串exp的内容构建表达式树T：
void CrtExptree(BiTree &T, char exp[])
{//根据字符串exp的内容构建表达式树T
stack
stack
char op;
int i=0;
OPTR.push ('#');
op = OPTR.top();
while( !((exp[i]=='#') && (OPTR.top()=='#')) ) //与
{
if (IsDigital(exp[i]))
{//建立叶子节点并入栈PTR
i+=CrtNode(PTR, &exp[i]);
}
else if (exp[i] == ' ')
i++;
else
{
switch (exp[i])
{
case '(':
{
OPTR.push (exp[i]);
i++;
break;
}
case ')':
{
op = OPTR.top (); OPTR.pop ();
while(op!='(')
{
CrtSubTree(PTR, op);
op = OPTR.top (); OPTR.pop ();
}//end while
i++;
break;
}
default: //exp[i]是+ - * /
while(! OPTR.empty ())
{
op = OPTR.top ();
if (Precede(op, exp[i])=='>')
{
CrtSubTree(PTR, op);
OPTR.pop ();
}
if(exp[i]!='#')
{
OPTR.push (exp[i]);
i++;
}
break;
}
}//end switch
}//end else
}//end while
T = PTR.top();
PTR.pop ();
}
判断操作符优先级
char symbol[5][5]={{'>', '>', '<', '<', '>'}, //符号优先级
{'>', '>', '<', '<', '>'},
{'>', '>', '>', '>', '>'},
{'>', '>', '>', '>', '>'},
{'<', '<', '<', '<', '='}};
int sym2num(char s) //返回符号对应优先级矩阵位置{
switch(s)
{
case '+': return 0; break;
case '-': return 1; break;
case '*': return 2; break;
case '/': return 3; break;
case '#': return 4; break;
}
}
char Precede(char a, char b) //返回符号优先级
{
return(symbol[sym2num(a)][sym2num(b)]);
}
生成后缀表达式
后序遍历表达式树T，获取树中每个结点的数据值生成后缀表达式存放在exp中
T是表达式树的根节点，count保存exp中字符的个数
后序遍历中，处理根结点时，依据T->len的值，把T->data中的字符依次添加到当前exp字符串的尾端。
添加完T->data后，再添加一个空格字符，同时更新count计数器的值。
void PostOrderTraverse(BiTree &T, char * exp ,int &count)
{
if(T)
{
PostOrderTraverse(T->lchild,exp,count);
PostOrderTraverse(T->rchild,exp,count);
strncpy(exp+count,T->data,T->len);
exp[count+=(T->len)]=' ';
count++;
}
}
计算表达式的值：
Status evaluate (char ch[], float & result)
{
SqStack S;
Status St;
int i;
i=0;
St = InitStack(S);
while(ch[i]!='#'&&i<100)
{
if(IsDigital(ch[i]))
{
i+=EvalValue(&ch[i], S);
}
else if(ch[i]==' ')
i++;
else{
EvalExpr(ch[i], S);
i++;
}
}
算法的具体步骤：
采用指针来实现二叉树，其中分支节点存储运算符，用叶子节点存储操作数，可以减少二叉树的结构性开销。采用顺序栈来实现表达式的计算，建立一个栈S 。从左到右读后缀表达式，如果读到操作数就将它压入栈S中，如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作符运算，再将运算的结果代替原栈顶的n项，压入栈S中。如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束。
算法的时空分析：
采用二叉树中分支节点和叶子节点分别存储不同的数据类型，是算法的结构性开销明显
Θ，对顺序栈实行压栈和出栈时降低，对二叉树进行一次后序遍历的时间代价为()n
()n
=，故计算表达式值时时间开销为()n
Θ
T2
n
输入输出格式：
Cout<<”请输入表达式。回车表示结束”
Cin>>21+23*（12-6）+9;
Cout<<”后缀表达式时为：”< Cout<<21 23 12 6 -*+ 9+< Cout<<”result is：”< Cout<<168< 四、测试结果 五、用户使用说明（可选） 1、本程序的运行环境为DOS操作系统，执行文件为四则运算.exe 2、运行程序时： (1) 显示提示“请输入表达式。回车表示结束”，此时输入的表达式表示要运算的表达式 (2) 数据输入完毕后，输出“后缀表达式为”输出后缀表达式 (3) 输出运算结果。 六、实验心得 这次实验让我更加二叉树和堆栈的定义，对课堂内容更加了解。 七、附录 #include #include #include #include #include #include #define STACK_INIT_SIZE 100 #define DATA_SIZE 10 #define STACKINCREMENT 10 #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OVERFLOW -2 using namespace std; typedef float SElemtype; typedef int Status; typedef char * TElemType; typedef struct BiTNode { TElemType data; int len; //data字符串中字符的个数struct BiTNode * lchild, * rchild; }BiTNode, *BiTree; typedef struct { SElemtype *base; SElemtype *top; int stacksize; }SqStack; Status IsDigital(char ch) { if(ch>='0'&&ch<='9') { return 1; //是数字字母 } return 0; //不是数字字母 } int CrtNode(stack { BiTNode * T; int i=0; T = (BiTNode *)malloc(sizeof(BiTNode)); T->data = (char *)malloc(DATA_SIZE*sizeof(char)); while(IsDigital(c[i])) { T->data [i] = c[i]; i++; } T->len = i; T->lchild = T->rchild = NULL; PTR.push (T); return i; } void CrtSubTree(stack { BiTNode * T; T = (BiTNode *)malloc(sizeof(BiTNode)); T->data = (char *)malloc(DATA_SIZE*sizeof(char)); T->data [0] = c; T->len = 1; T->rchild = PTR.top(); //先右子树，否则运算次序反了 PTR.pop (); T->lchild = PTR.top(); PTR.pop (); PTR.push (T); } char symbol[5][5]={{'>', '>', '<', '<', '>'}, //符号优先级 {'>', '>', '<', '<', '>'}, {'>', '>', '>', '>', '>'}, {'>', '>', '>', '>', '>'}, {'<', '<', '<', '<', '='}}; int sym2num(char s) //返回符号对应优先级矩阵位置{ switch(s) { case '+': return 0; break; case '-': return 1; break; case '*': return 2; break; case '/': return 3; break; case '#': return 4; break; } } char Precede(char a, char b) //返回符号优先级 { return(symbol[sym2num(a)][sym2num(b)]); } void CrtExptree(BiTree &T, char exp[]) {//根据字符串exp的内容构建表达式树T stack stack char op; int i=0; OPTR.push ('#'); op = OPTR.top(); while( !((exp[i]=='#') && (OPTR.top()=='#')) ) //与 { if (IsDigital(exp[i])) {//建立叶子节点并入栈PTR i+=CrtNode(PTR, &exp[i]); } else if (exp[i] == ' ') i++; else { switch (exp[i]) { case '(': { OPTR.push (exp[i]); i++; break; } case ')': { op = OPTR.top (); OPTR.pop (); while(op!='(') { CrtSubTree(PTR, op); op = OPTR.top (); OPTR.pop (); }//end while i++; break; } default: //exp[i]是+ - * / while(! OPTR.empty ()) { op = OPTR.top (); if (Precede(op, exp[i])=='>') { CrtSubTree(PTR, op); OPTR.pop (); } if(exp[i]!='#') { OPTR.push (exp[i]); i++; } break; } }//end switch }//end else }//end while T = PTR.top(); PTR.pop (); } void PostOrderTraverse(BiTree &T, char * exp ,int &count) { //后序遍历表达式树T，获取树中每个结点的数据值生成逆波兰表达式exp //T是表达式树的根节点；字符串exp保存逆波兰表达式；count保存exp中字符的个数 //后序遍历中，处理根结点时，依据T->len的值，把T->data中的字符依次添加到当前exp字符串的尾端 //添加完T->data后，再添加一个空格字符，同时更新count计数器的值。 //填空 //int i; if(T) { PostOrderTraverse(T->lchild,exp,count); PostOrderTraverse(T->rchild,exp,count); strncpy(exp+count,T->data,T->len); exp[count+=(T->len)]=' '; count++; } } //--------------------------------- //逆波兰表达式计算 //填空 Status InitStack(SqStack &S) { S.base = (SElemtype *)malloc(STACK_INIT_SIZE*sizeof(SElemtype)); if (! S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; //printf("程序运行到构建栈\n"); return OK; } int StackLength(SqStack S) { return S.top-S.base; //printf("程序运行到获得堆栈元素的个数\n"); //获得堆栈元素的个数 } Status Push(SqStack &S, SElemtype e) { if(S.top-S.base>=S.stacksize) { S.base=(SElemtype *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemtype)); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; //printf("程序运行到入栈\n"); return OK; //入栈 } Status Pop(SqStack &S, SElemtype &e) { if(S.top==S.base) return ERROR; e=*--S.top; // printf("程序运行到出栈\n"); return OK; //出栈 } int EvalValue(char *ch, SqStack &S) { int i=0; SElemtype result=0; char a; a=ch[i]; while(IsDigital(a)) { result=10*result+(int)(a-48); a=ch[++i]; } Push(S, result); //printf("程序运行标志1\n"); return i; } void EvalExpr(char ch, SqStack &S) { float p ,q,r; if((ch=='+')||(ch=='-')||(ch=='*')||(ch=='/')) { Pop(S,p); Pop(S,q); switch(ch) { case '+':r=p+q; break; case '-':r=q-p; break; case '*':r=q*p; break; case '/': if(p==0) printf("输入错误!!!!"); else r=q/p; break; default:; } Push(S,r); //printf("程序运行标志2\n"); } //如果ch中保存的是操作符，则从堆栈中弹出两个元素，并把操作符应用在这两个元素之上，//然后把操作结果压入到栈中。如果试图从栈中弹出两个元素是，该栈中并没有，那么该 //后缀表达式是不正确的。 } Status evaluate (char ch[], float & result) { SqStack S; Status St; int i; i=0; St = InitStack(S); while(ch[i]!='#'&&i<100) { if(IsDigital(ch[i])) { i+=EvalValue(&ch[i], S); } else if(ch[i]==' ') i++; else{ EvalExpr(ch[i], S); i++; } } //如果到达表达式末尾时，栈中剩余元素不止一个，那么该 //后缀表达式是不正确的。 if(StackLength(S) ==1) Pop(S, result); else{ //printf("表达式错误"); return ERROR; } //printf("程序运行标志3\n"); return OK; } //------------------------- main() { BiTree T; Status St; char ch[100],c; //输入的四则运算表达式 char exp[100]; //逆波兰表达式 int count=0; int i=0; float result; printf("请输入表达式: \n"); while(i<100) { scanf("%c",&c); ch[i++]=c; if(c=='\n'){ ch[--i]='#'; break; }//end if } CrtExptree(T, ch);//根据字符串ch的内容构建表达式树T //后序遍历表达式树T得到表达式的逆波兰表达式exp；count中保存exp中字符的个数PostOrderTraverse(T, exp, count); printf("逆波兰表达式为:\n"); for(i=0; i printf("%c",exp[i]); printf("\n"); exp[count] = '#'; //添加结束符 St = evaluate (exp, result); //计算逆波兰表达式exp 的值 //输出计算的结果 if (St) printf("运算结果:%5.2f \n", result); else printf("\n表达式错误\n"); return 0; } 竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告 篇一：数据结构实验二——算术表达式求值实验报告 《数据结构与数据库》 实验报告 实验题目算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系pb0920603 姓学 邮名：李维谷号：pb09206285箱： liwg@https://www.doczj.com/doc/912413724.html,指导教师：贾伯琪 实验时间：20XX年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个(:数据结构表达式求值实验报告)算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 江西理工大学软件学院计算机类课程实验报告 课程名称：数据结构 班级：11软件会计4班 姓名：黄健 学号：11222122 江西理工大学软件学院 一、目录（中缀表达式求值） 1、目录--------------------------------------------------------------2 2、实验目的--------------------------------------------------------3 3、实验要求--------------------------------------------------------3 4、实验仪器设备与材料-----------------------------------------3 5、实验原理--------------------------------------------------------4 6、实验步骤--------------------------------------------------------5 7、实验原始记录--------------------------------------------------6 8、实验数据分析计算结果--------------------------------------10 9、实验心得体会--------------------------------------------------11 10、思考题----------------------------------------------------------12 《数据结构与数据库》 实验报告 实验题目 算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系PB0920603 姓名：李维谷 学号：PB09206285 邮箱：liwg@https://www.doczj.com/doc/912413724.html, 指导教师：贾伯琪 实验时间：2010年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 输出结果：194.4 实验表达式求值问题 1.问题描述 表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3.中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀表达式（如：11 22 7 4 - * 3 / +）和前缀表达式（+ 11 / * 22 - 7 4 3）。后缀表达式 和前缀表达式中没有括号，给计算带来方便。如后缀表达式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。 2.数据结构设计 （1）顺序栈类定义：首先应在类中定义成员函数，以此来完成顺序栈的相关操作，如下： class SqStack { private: T *base; //栈底指针 int top; //栈顶 int stacksize; //栈容量public: SqStack(int m); //构建函数 ~SqStack(){delete [] base;top=0;stacksize=0;} //析构函数 void Push(T x); //入栈 T Pop(); //出栈 T GetTop(); //获取栈顶元素 int StackEmpty(); //测栈空 void ClearStack(); //清空栈 void StackTop(); //返回栈顶指针 void StackTranverse(); //显示栈中元素 }; （2）顺序栈类实现：对顺序栈进行初始化，初始化的首要操作就是创建一个空顺序栈。 Step1：申请一组连续的存空间为顺序栈使用： base=new T[m]; i f(base==NULL) { cout<<"栈创建失败，退出!"< 数据结构课程设计 设计说明书 算术表达式求值问题 学生姓名白子健 学号1318014057 班级计本1302 成绩 指导教师李军 计算机科学与技术系 2015年9月10日 数据结构课程设计评阅书 课程设计任务书 2015—2016学年第一学期 专业：计算机科学与技术学号：1318014057 姓名：白子健 课程设计名称：课程设计Ⅰ---数据结构课程设计 设计题目：表达式求值算法的实现 完成期限：自2015 年9 月 1 日至2015 年9 月12 日共 2 周 设计内容及要求: 算术表达式求值是程序设计语言编译中的一个基本问题，通过栈实现表达式运算优先级的匹配和运算。用C/C++语言编程实现任意算术表达式的求值，设计内容要求如下：（1）表达式共有三种基本表示方法：前缀法、中缀法、后缀法。从表达式的这三种基本方法中任选一种方法进行编程求值。 （2）分析所选的表示方法，根据选定的表示方法确定对应的存储结构和相关算法。 （3）算法要能正确处理算术运算的优先级规则，即: 先括号内，后括号外的规则；运算先乘除，后加减；同级运算从左到右。 如下表达式： 50+（6*3+2） 要求： (1)用C/C++语言编写一个程序将这组学生成绩输入到计算机中，数据运算的存储 逻辑结构为栈。 (2)程序要能正确处理表达式的优先级、输出正确运算结果。 最终设计成果形式为： 1、设计好的软件一套； 2、撰写一份课程设计说明书一份，打印并装订成册。 指导教师（签字）：教研室主任（签字）： 批准日期：年月日 目录 1 课题描述 (1) 2 设计思路 (2) 3 算法设计 (3) 4 程序代码 (5) 5 测试及分析 (12) 6 总结 (13) 参考文献 (13) 软件技术基础实验报告 实验名称：表达式计算器 系别：通信工程 年级： 班级： 学生学号： 学生姓名： 《数据结构》课程设计报告 题目简易计算表达式的演示 【题目要求】 要求：实现基本表达式计算的功能 输入：数学表达式，表达式由整数和“+”、“-”、“×”、“/”、“（”、“）”组成输出：表达式的值 基本操作：键入表达式，开始计算，计算过程和结果记录在文档中 难点：括号的处理、乘除的优先级高于加减 1．前言 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/、=，用#表示结束。 算法输出：表达式运算结果。 算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。 2．概要设计 2.1 数据结构设计 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top 指示栈顶元素在顺序栈中的位置，base 为栈底指针，在顺序栈中，它始终指向栈底，即top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针top 增1，删除栈顶元素时，指针top 减1。 2.2 算法设计 为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR ，用以寄存运算符，另一个称做OPND ，用以寄存操作数或运算结果。 1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素； 2.依次读入表达式，若是操作符即进OPND 栈，若是运算符则和OPTR 栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR 栈的栈顶元素和当前读入的字符均为”#”）。 2.3 ADT 描述 ADT Stack{ 数据对象：D={ i a |i a ∈ElemSet,i=1,2,…，n, n ≧0} 数据对象：R1={< 1 ,-i i a a >| 1-i a ,D a i ∈,i=2,…，n} 湖南人文科技学院计算机科学技术系 课程设计说明书 课程名称:数据结构 课程代码:408024 题目: 表达式求值 年级/专业/班:08级计算机科学与技术二班 学生姓名: 黄胜李业芝黄自强 黄沅涛姚洋 学号:08408210 08408211 08408212 08408213 08408215 指导教师: 袁辉勇 开题时间: 2009 年12 月21 日 完成时间: 2010 年 1 月 1 日 目录 摘要 (1) 一、引言 (3) 二、设计目的与任务 (3) 1、课程设计目的 (3) 2、课程设计的任务 (4) 三、设计方案 (4) 1、需求分析 (4) 2、概要设计 (4) 3、详细设计 (6) 4、程序清单 (13) 四、调试分析与体会 (17) 五、运行结果 (18) 六、结论 (20) 七、致谢 (21) 八、参考文献 (21) 摘要 在高级语言环境中算术表达上的结果是通过语言环境预设的算法的思想计算出来的，然而高级语言初学者并不了解表达式的计算过程和方法。本文采用算符优先分析和堆栈的方法给出了算术表达式的计算过程。 所以本次课程设计的程序是在Windows系统上为用户解决包括加、减、乘、除以及括号在内的四则混合运算。用户可通过键盘输入四则运算，经过程序运行之后，可以判断出用户所输入的表达式是否正确。如果正确，就给出表达式的值；如果不正确，就提示输入有误。 关键词：四则混合运算；高级语言；栈 Abstract The arithmetic expression result is the algorithm thought which supposes in advance through the language environment calculatesin the higher order language environment,however the higher order language beginner does not understand the expression the computationprocess and the method. This article used the operator first to analyze and the storehouse method has given the arithmetic expression computa-tion process. Therefore, the procedure in this curriculum design is the solution for users on Windows systems, including add, subtract, multiply, divide and brackets, including four hybrid operation. Users can enter via the keyboard 4 operation, after a program is running, you can determine the user entered expression is correct. If correct, it gives the value of the expression; if not correct, it prompted an error. 实验3四则运算表达式求值 背景 在工资管理软件中，不可避免的要用到公式的定义及求值等问题。对于数学表达式的计算，虽然可以直接对表达式进行扫描并按照优先级逐步计算，但也可以将中缀表达式转换为逆波兰表达式，这样更容易处理。 问题描述 四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。 基本要求 使用二叉树来实现。 实现提示 利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。 输入输出格式： 输入：在字符界面上输入一个中缀表达式，回车表示结束。 输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。 选作内容 （1）在输入输出方式上要求使用： 输入：将中缀表达式存于文本文件中，程序从该文本文件中读出表达式。 输出：如果该中缀表达式正确，则将后缀表达式输出到该文件中原表达式的后面，它们之间用“---”后相连；如果不正确，请在输出表达式错误提示到该文件原表达式的后面，它们之间用“---”相连。 (2) 利用堆栈来实现中缀表达式转换为后缀表达式。 测试用例 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 程序代码： #include HUNAN UNIVERSITY 课程实习报告 题目：四则运算表达式求值 学生姓名： 学生学号： 专业班级： 指导老师： 完成日期： 一、需求分析 四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达式，并计算结果。 本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。 在字符界面上输入一个中缀表达式，回车表示结束。如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。 测试数据 输入： 21+23*（12-6） 输出： 21 23 12 6 -*+ 二、详细设计 输入和输出的格式 输入 本程序可以将输入的四则运算表达式（中缀表达式）转换为后缀表达式 输出 后缀表达式为：//输出结果的位置 表达式的值为：//输出结果的位置 三、调试分析 本次实验的难点主要是在建立二叉树的问题上。关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法，成功实现了目标，但是却遇到了一个问题，那就是不能处理小数，甚至两位或两位以上的整数。因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改进采用字符串数组来存储操作数，成功解决了问题。 另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。 四、测试结果 五、用户使用说明（可选） 1、运行程序时 提示输入四则运算表达式 本程序可以将中缀表达式转化为后缀表达式，并计算结果 请输入四则运算表达式： 输出 后缀表达式为： 表达式的值为： 程序源代码（c++） #include 《数据结构（C++版）》课设计报告2012—2013学年第一学期 课程名称数据结构 设计题目表达式求值 专业班级 姓名 学号 指导教师 课程设计题目：表达式求值 一、问题描述 对一个合法的中缀表达式求值。简单起见，假设表达式只包含+，-，*，/等4个双目运算符，且运算符本身不具有二义性，操作数均为一位整数。 二、基本要求 1.正确解释表达式； 2.符合四则运算规则； 3.输出最后的计算结果。 三、概要设计 对中缀表达式求值，通常使用“算符优先算法”。根据四则运算规则，在运算的每一步中，任意两个相继出现的运算符t和c之间的优先关系至多是下面三种关系之一： （1） t的优先级低于c； （2） t的优先级等于c； （3） t的优先级高于c。 为实现算符优先算法，可以使用两个工作栈：一个栈OPTR存放运算符；另一个栈OPND存放操作数，中缀表达式用一个字符串数组存储。 四、详细设计 利用类模板 #include 表达式求值课程设计报告 表达式求值 《数据结构》 课程设计报告 题目: 栈的应用:表达式求值 (系): 信息科学与工程学院院 专业班级: 软件工程1102班学生姓名: 学号: 指导教师: 20 13 年 6 月 8 日至20 13 年 6 月 21 日 表达式求值 目录 目录 (2) 1 概述 (1) 1.1 课程设计目的 (1) 1.2 课程设计内容 (1) 2 系统需求分析 ...................................................... 1 2.1 系统目标 (1) 2.2 主体功能 (1) 2.3 开发环境 (1) 3 系统概要设计 .................................................... 2 3.1 系统的功能模块划分 (2) 3.2 系统流程图 (2) 4系统详细设计 ..................................................... 3 5 测试 ............................................................ 6 5.1 测试方案 (6) 5.2 测试结果 (6) 6 小结 ............................................................ 8 参考文献 .......................................................... 9 附录1 源程序清单 (10) 2 数据结构课程设计报告(2012) 表达式求值 1 概述 1.1 课程设计目的 1(要求学生达到熟练掌握C语言的基本知识和技能。 2(了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。 3(提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 4(培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提 高程序设计水平。 实验课程名称 专业班级 学生姓名 学号 指导教师 20 至 20 学年第学期第至周 算术表达式求值演示 一、概述 数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 在这次的课程设计中我选择的题目是算术表达式求值演示。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。 二、系统分析 1．以字符列的形式从终端输入语确的、不含变量的整数表达式。利用已知的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。 2．一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最后编出程序，进行测试，调试直至得到想要的答案。对于算术表达式这个程序，主要利用栈，把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法，可以使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。 3．演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言的转化。 4．程序执行时的命令： 本程序为了使用具体，采用菜单式的方式来完成程序的演示，几乎不用输入什么特殊 的命令，只需按提示输入表达式即可。（要注意输入时格式，否者可能会引起一些错误）5. 测试数据。 三、概要设计 一个算术表达式中除了括号、界限符外，还包括运算数据和运算符。由于运算符有优先级别之差，所以一个表达式的运算不可能总是从左至右的循序执行。每次操作的数据或运算符都是最近输入的，这与栈的特性相吻合，故本课程设计借助栈来实现按运算符的优先级完成表达式的求值计算。 算法设计 程序包含三个模块 (1) 主程序模块，其中主函数为 void main{ 输入表达式； 根据要求进行转换并求值； 输出结果； } (2) 表达式求值模块——实现具体求值。 (3) 表达式转换模块——实现转换。 各个函数之间的调用关系 嘉应学院计算机学院 实验报告 课程名称：数据结构课程设计 开课学期：2017-2018学年第2学期 班级： 指导老师： 实验题目：学生通讯录管理系统 学号： 姓名： 上机时间： (一) 需求分析 1、输入的形式和输入值的范围： 根据题目要求与提示，先选择你要使用的表达式形式（中缀用1，后缀用0），在输入一个中缀表达式，输入数的范围为int型，此时，程序将计算出表达式的结果。 2、输出的形式： 当按照程序要求选择了1或0之后，再输入表达式；如果选择的是1，则程序将自动运算出表达式结果；如果之前选择的是0，则程序将现将中缀表达式转化为后缀表达式并计算出结果。 3、程序所能达到的功能： 本程序能计算出含+、-、*、/、（、）等运算符的简单运算。 4、测试数据： 输入一个表达式，如果你之前选择的是“中缀表达式”，那么输入5*(4-2)#,那么输出结果是10；如果之前选择的是“后缀表达式”，那么输入5*（4-2）#，那么他将先转换成后缀表达式5 4 2 - * #，再输出结果10。 如果输入表达式没有结束标示符#，如5*（4-2），那将不会输出任何结果，或出现错误结果。 (二) 概要设计 为了实现上述操作，应以栈为存储结构。 1．基本操作： （1）. int GetTop(SqStack *s) 初始条件：栈存在； 操作结果：若栈为空，则返回s的栈顶元素；否则返回ERROR。 （2）. void Push(SqStack *s,int e) 初始条件：栈存在； 操作结果：插入e为新的栈顶元素。 （3）. int Pop(SqStack *s) 初始条件：栈存在； 操作结果：若栈不空，则删除之，并返回其值；否则返回REEOR。 （4）.void InitStack(SqStack *s) 初始条件：栈存在； 操作结果：置栈为空。 （5）. int Empty(SqStack *s) 初始条件：栈存在； 操作结果：判定s是否为空栈。 （6）. int Operate(int a,char theta, int b) 初始条件：操作数a和b存在，且theta是+、-、*、/四则运算； 操作结果：返回a与b间theta运算的结果。 （7）. int In(char s,char* TestOp) 初始条件：s为待判断字符，TestOp为已知的算符集合； 操作结果：s为算符集合中的元素则返回1，否则返回0. （8）. int ReturnOpOrd(char op,char* TestOp) 初始条件：op为待确定运算符，TestOp为已知的算符集合； 操作结果：确定运算符类型。 （9）. char precede(char a, char b) 课程设计 教学院 课程名称 题目 专业 班级 姓名 同组人员 指导教师 2013 年 6 月22 日 (完成时间) 目录 一．概述 (2) 二．总体方案设计 (4) 三．详细设计 (6) 四．程序的调试与运行结果说明 (14) 五．课程设计总结 (14) 六．附录 (16) 参考文献 (3233) （“目录”要求必须自动生成） 一概述（宋体，三号，加粗，居中） 1.课程设计的目的（小标题，宋体，四号，加粗，左对齐顶格） （1）．理解和掌握该课程中的有关基本概念，程序设计思想和方法。 （2）．培养综合运用所学知识独立完成课题的能力。 （3）．培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。 （4）．掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。 2.课程设计的要求 算术表达式求值程序实现以下功能： (1)构造一个空栈S,初始条件：栈S已存在 (2)用P返回S的栈顶元素 (3)插入元素ch为新的栈顶元素 (4)删除S的栈顶元素 (5)判断字符是否是运算符，运算符即返回1 (6)判断运算符优先权，返回优先权高的 (7)输入表达式 (8)返回表达式的最终结果。 二总体方案设计 a)需求分析 该程序能实现算术四则运算表达式的求值，显示运算过程。 输入的形式：表达式，例如5*（3+7）#。 包含的运算符只能有'+'、 '-'、'*'、 '/'、 ' (' ') '； 程序所能达到的功能：对表达式求值并输出。 b)总体设计 本程序使用的是编程工具是Visual c++ 6.0，实现了运算器的功能和仿真界面（大体界面如下图所示）。在基本要求的基础上，运算数可以是实数类型，同时增加了乘方运算的功能；可以实现对负数的运算，例如用户输入表达式6* （-0.25）,则程序会在负号的前面自动加上一个0。 1)算符包括加（+）、减（-）、乘（*）、除（/）、乘方（^）；另一个称作 OPND，用以寄存操作数和运算结果，操作数可以是float型的浮点数。 算法的基本思想是： 2)首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素； 依次读入表达式中的每个字符，若是操作数（浮点数）则进OPND栈， 若是运算符（+、—、*、/、^）则和OPTR栈的栈顶运算符比较优先权 后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当 前读入的字符均为“#”）。 3)编写一个原型为void strtofloat(char str[ ],int n,int i)，把一 个数字串转换为一个实型数，并压入运算数栈中。（整个程序的源代码 见附录，并有具体解释） 淮海工学院计算机工程学院 课程设计报告 设计名称：数据结构课程设计 选题名称：表达式求值 姓名：学号： 专业班级： 系（院）：计算机工程学院 设计时间： 设计地点：软件工程实验室、教室 指导教师评语： 成绩： 签名： 年月日 1．课程设计目的 1、训练学生灵活使用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。 2．课程设计任务和要求： 任务 根据教材《数据结构-C语言描述》（耿国华主编）和参考书《数据结构题集（C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择使用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。 设计题目从任务书所列选题表中选取，每班每题不得超过2人。 学生自选课题 学生原则上可以结合个人爱好自选课题，要求课题有一定的深度和难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。 要求： 1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备和否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。 3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释; 4、每位同学需提交可独立运行的程序； 5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）； 6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3．课程设计说明书 一、设计思想 一．中缀式计算结果的设计思想： 此种算法最主要是用了两个栈：用两个栈来实现算符优先，一个栈用来保存需要计算的数据numStack（操作数栈）,一个用来保存计算优先符priStack（操作符栈）。从字符串中获取元素，如果是操作数，则直接进操作数栈，但如果获取的是操作符，则要分情况讨论，如下：（这里讨论优先级时暂不包括“（”和“）”的优先级） 1.如果获取的操作符a的优先级高于操作符栈栈顶元素b的优先级，则a直接入操作符栈; 2.如果获取的操作符a的优先级低于操作符栈栈顶元素b的优先级，则b出栈，a进栈，并且取出操作数栈的栈顶元素m，再取出操作数栈新的栈顶元素n，如果b为+，则用n+m，若为减号，则n-m，依此类推，并将所得结果入操作数栈； 3.如果获取的是“（”，则直接进操作符栈； 4.如果获取的是“）”，则操作符栈的栈顶元素出栈,做类似于情况2的计算，之后把计算结果入操作数栈，再取操作符栈顶元素，如果不是“（”，则出栈，重复操作，直到操作符栈顶元素为“（”，然后“（”出栈； 5.当表达式中的所有元素都入栈后，看操作符栈中是否还有元素，如果有，则做类似于情况2 的计算，并将结果存入操作数栈，则操作数栈中最终的栈顶元素就是所要求的结果。 二．中缀转后缀及对后缀表达式计算的设计思想： 中缀转后缀时主要用了一个操作符栈和一个用来存放后缀表达式的栈，从表达式中依次获取元素，如果获取的是操作数，则直接存入s3栈中，如果获取的是操作符也需分情况讨论，如下：（这里讨论优先级时暂不包括“（”和“）”的优先级） 1. 如果获取的操作符a的优先级高于操作符栈栈顶元素b的优先级，则a直接入操作符栈; 2. 如果获取的操作符a的优先级低于操作符栈栈顶元素b的优先级，则b出栈，a进栈，并且将b存入到操作符栈中； 3.如果获取的是“（”，则直接进操作符栈； 4.如果获取的是“）”，则操作符栈的栈顶元素出栈,并依次存入到操作符栈中，直到操作符栈栈顶元素为“（”，然后将“（”出栈； 5.当表达式中的所有元素都入栈或存入到操作符栈之后，看操作符栈中是否还有元素，如果有，则依次出栈，并且依次存入到操作符栈中，最后打印操作符栈中的字符串，则此字符串即为要求的后缀表达式。 对后缀表达式的计算方法：主要用到了一个操作数栈，从操作符栈中依次取出元素，如果是操作数，则进栈，如果是操作符，则从操作数栈中依次取出两个栈顶元素a1和a2,如果操作符是“/”,则计算a2/a1,将计算结果再次进栈，依此类推，最终栈顶元素即为计算的最终结果。 在这两种算法中，应该特别注意一点：人的习惯，用户在输入表达式时，容易这样输入，如：3*4（3+2），这样是不可取的，应必须要用户输入3*4*（3+2），这是在设计思想上错误提示的很重要一点，否则计算不全面！ 二、算法流程图 第一个图是直接计算的流程图，图中反应除了这种方法的大致设计思路，但是有些细节没有反映出来，比如说，怎样把字符型数据转换为浮点型数据，就没有反映出来。特别说明 一、需求分析 1.程序说明： 本程序利用二叉树的后序遍历实现表达式的转换，同时可以使用本程序的结果求解后缀表达式的值 2.输入输出的形式： 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 计算结果为：159 3.输入输出范围： 程序仅计算int类型的数，输入输出的结果均在int类型的限定范围内 4.测试数据 第一组： 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 计算结果为：159 第二组： 输入：9+(3-1)*3+10/2 输出：9 3 1-3*+ 10 2/+ 计算结果为：20 第三组： 输入：( ( 35 + 15 ) * ( 80 – 70 ) ) / 20 输出：35 15 + 80 70 - * 20 / 计算结果为：25 第四组： 输入：14×8/7-20×3 输出：14 8 × 7 / 20 3 × - 计算结果为：-44 第五组： 输入：10×8+9×6-(6+4) 输出：10 8 ×+ 9 6 ×- 6 4 + 计算结果为：124 二、概要设计 抽象数据类型 由于中序遍历表达树，将得到中缀表达式；后序遍历表达式树，将得到 后缀表达式，而使用栈对后序表达式求取较为方便 因此，获取的四则运算表达式使用线性表临时存储，再转存至二叉树中， 利用二叉树，得到后缀表达式，通过栈，对后缀表达式求值 清华大学数据结构课程实验报告（20 -20 学年第学期） 报告题目：算术表达式求值 任课老师： 专业： 学号： 姓名： 二0一年月日 摘要：现代科学技术高速发展，各种高科技产品频频问世，而各种技术的基础都离不开基本的表达式求值，它虽然简单，但却是任何复杂系统的基本执行操作。栈是一种重要的线性结构，从数据结构的角度看，它是一种特殊的线性表，具有先入先出的特点。而算符优先法的设计恰巧符合先入先出的思想。故我们基于栈这种数据结构，利用算符优先法，来实现简单算术表达式的求值。 关键字：算符优先法；算术表达式；数据结构；栈 一、课题概述 1、问题描述 一个算术表达式是由运算数、运算符、界限符组成。假设操作数是正整数，运算符只含有加“+”、减“-”、乘“*”、除“/”四种二元运算符，界限符有左括号“（”、右括号“）”和表达式起始、结束符“#”。利用算符优先法对算术表达式求值。 2、设计目的 （1）通过该算法的设计思想，熟悉栈的特点和应用方法； （2）通过对算符优先法对算术表达式求值的算法执行过程的演示，理解在执行相应栈的操作时的变化过程。 （3）通过程序设计，进一步熟悉栈的基本运算函数； （4）通过自己动手实现算法，加强从伪码算法到C语言程序的实现能力。3、基本要求： （1）使用栈的顺序存储表示方式； （2）使用算符优先法； （3）用C语言实现； （4）从键盘输入一个符合要求的算术表达式，输出正确的结果。 4、编程实现平台 Microsoft Visual C++ 6.0 二、设计思路及采取方案 1、设计思路： 为了实现算符优先法，可以使用两个工作栈。一个称做OPTR，用以寄存运数据结构表达式求值实验报告
中缀表达式求值
数据结构实验二——算术表达式求值实验报告
数据结构课程设计_表达式求值问题
表达式求值课程设计
数据结构算术表达式求值实验报告
表达式求值算法实现
四则运算实验报告
四则运算表达式求值实验报告
表达式求值
表达式求值课程设计报告
《数据结构课程设计》表达式求值实验报告
数据结构课程设计-表达式求值问题
算术表达式求值课程设计报告
表达式求值实验报告
用两种方法实现表达式求值
四则运算表达式求值
算术表达式求值-数据结构实验报告
相关主题
文本预览