HUNAN UNIVERSITY
背景
在工资管理软件中，不可避免的要用到公式的定义及求值等问题。对于数学表达式
的计算，虽然可以直接对表达式进行扫描并按照优先级逐步计算，但也可以将中缀
表达式转换为逆波兰表达式，这样更容易处理。
问题描述
四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。
一．需求分析
（1）本程序利用二叉树后序遍历来实现表达式的转换，同时可以使用栈来求解后缀表达式的值。
（2）输入输出的格式：
输入：在字符界面上输入一个中缀表达式，回车表示结束。
输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和计算结果，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。
（3）测试用例：
输入：21+23*（12-6）+9
输出：21 23 12 6 -*+ 9+
result is 168
二．概要设计
（1）抽象数据类型：
由于四则运算表达式中运算符可能有多个后继，而运算的对象无后继，可以采用二
叉树来实现把中缀表达式转换为后缀表达式。
数据对象：四则运算符及整数
数据关系：运算符有多个后继，二运算对象的值无后继
基本操作：后序遍历，二叉树的构建和摧毁，插入，删除
经过二叉树的后序遍历后的表达式惊醒运算是满足后进先出的原则，采用栈来实现
四则运算表达式的求值。
数据对象：运算符（字符）及整数
数据关系：后进先出
基本操作：入栈，出栈，栈的构建和删除
（2）算法基本思想：
用二叉树来存储四则表达式，再通过后序遍历把中缀表达式转换为后缀表达式，最
后通过栈来计算表达式的值，最后输出后序表达式和表达式的值。
（3）程序的流程：
该程序有三个模块组成：
1.输入模块：输入一个中缀表达式
2.处理模块：把中缀表达式转换为后缀表达式
3.计算模块：计算表达式的值
4.输出模块：输出后缀表达式及表达式的值
三．详细设计
（1）物理数据类型：采用指针来实现二叉树，其中分支节点存储运算符，用叶子节点存储操作数，可以减少二叉树的结构性开销。采用顺序栈来实现表达式的计算，建
立一个栈S 。从左到右读后缀表达式，如果读到操作数就将它压入栈S中，如果
读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作符
运算，再将运算的结果代替原栈顶的n项，压入栈S中。如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束。
伪代码：
二叉树的基本操作伪代码：
后序遍历：
template
void nextorder(BinNode
{
if(subroot==Null) return false;//Empty subtree,do nothing
nextorder(subroot->left());
visit(subroot); //Perform whatever action is desired
nextorder(subroot->right());
}
二叉树的建立：
// Binary tree node class
template
class BinNodePtr : public BinNode
{
private:
Elem it; // The node's value
BinNodePtr* lc; // Pointer to left child
BinNodePtr* rc; // Pointer to right child
public:
BinNodePtr()
{ lc = rc = NULL; }
BinNodePtr(Elem e, BinNodePtr* l =NULL,BinNodePtr* r =NULL)
{
it = e;
lc = l;
rc = r;
}
Elem& val()
{ return it; }
void setVal(const Elem& e)
{it = e; }
inline BinNode
{ return lc; }
void setLeft(BinNode
{ lc = (BinNodePtr*)b; }
inline BinNode
{ return rc; }
void setRight(BinNode
{ rc = (BinNodePtr*)b; }
bool isLeaf()
{ return (lc == NULL) && (rc == NULL); } };
插入及删除：
InsertChild(T, p, LR, c);
DestroyBiTree(&T);
DeleteChild(T, p, LR);
顺序栈的基本操作及伪代码：
void init_stack()
{ top = -1; } //空线性表初始化top void push_stack(int x)
{ s[top] = x; } //压栈：
void pop_stack()
{ top = top -1; } //出栈
int top_stack()
{ return s[top]; } //取得栈顶元素
bool empty_stack()
{
if(top==-1)
return true;
else
return false;
} //判断栈空
bool full_stack()
{
if(top==3)
return true;
else
return false;
} //判断栈满
int getHeadStack()
{
return s[top];
}
//返回栈顶元素的值
} 计算表达式的值：
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++;
}
}
（2） 算法的具体步骤：
首先建立一颗二叉树，用二叉树的分支节点存储四则运算的操作符，用二叉树的叶
子节点存储二叉树的操作数，然后再对二叉树进行一次后序遍历，把后序遍历得到的压入栈中，当读到n 元运算符时，则取出由栈顶向下的n 项按操作符运算，再将运算的结果代替原栈顶的n 项，压入栈中 。如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束。
（3） 算法的时空分析：采用二叉树中分支节点和叶子节点分别存储不同的数据类型，
是算法的结构性开销明显降低，对二叉树进行一次后序遍历的时间代价为()n Θ，对顺序栈实行压栈和出栈时()n n T 2=，故计算表达式值时时间开销为()n Θ （4） 输入输出格式：
Cout<<”请输入一串中缀表达式：” Cin>>21+23*（12-6）+9;
Cout<<”转换为后缀表达式时为：”< Cout<<21 23 12 6 -*+ 9+< Cout<<”表达式的值为：”< Cout<<168< （5）结果截图： （6）代码： #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/fe2415783.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/fe2415783.html, 指导教师：贾伯琪 实验时间：2010年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 输出结果：194.4 数理学院 课程设计报告书 课程名称数据结构课程设计 设计题目算术表达式求值演示 专业班级 学号 姓名 指导教师 2014 年12 月 4.2.2 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S 已存在。 操作结 果： 用P 返回S的栈顶元素。Push(&S 初始条 件：，ch) 栈S 已存在。 操作结 果：插入元素ch 为新的栈顶元素。 Pop(&S) 初始条件：栈S 已存在。 操作结 果：删除S 的栈顶元素。 In(ch) 操作结果：判断字符是否是运算符，运算符即返回1 Precede(c1, c2) 初始条件：c1,c2 为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b) 初始条件：a,b 为整数，op为运算符。操作结果： a 与 b 进行运算，op 为运算符，返回其值。num(n) 操作结果：返回操作数的长度。EvalExpr() 初始条件：输入表达式合法。操作结果：返回表达式的最终结果。}ADT Stack 主程序的流程： EvaluateExpression() 函数实现了对表达式求值的功能，main() 函数直接调用EvaluateExpression() 对输入的表达式求值输出。 4.2.3 函数的调用关系图 4.3 详细设计 4.3.1 ① . Precede(char c1,char c2)判断运算符优先权，返回优先权高的 算符间的优先关系 如下： 算法伪代码如下： char Precede(char c1,char c2) { static char array[49]={ >', '>', '<', '<', '<', '>', '>', >', '>', '<', '<', '<', '>', '>', >', '>', '>', '>', '<', '>', '>', >', '>', '>', '>', '<', '>', '>', <', '<', '<', '<', '<', '=', '!', >', '>', '>', '>', '!', '>', '>', <', '<', '<', '<', '<', '!', '='}; // 用一维数组存储 49 种情况 switch(c1) { /* i 为下面 array 的横标 */ case '+' : i=0;break; case '-' : i=1;break; case '*' : i=2;break; 实验表达式求值问题 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<<"栈创建失败，退出!"< 软件技术基础实验报告 实验名称：表达式计算器 系别：通信工程 年级： 班级： 学生学号： 学生姓名： 《数据结构》课程设计报告 题目简易计算表达式的演示 【题目要求】 要求：实现基本表达式计算的功能 输入：数学表达式，表达式由整数和“+”、“-”、“×”、“/”、“（”、“）”组成输出：表达式的值 基本操作：键入表达式，开始计算，计算过程和结果记录在文档中 难点：括号的处理、乘除的优先级高于加减 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} 表达式求值课程设计报告 表达式求值 《数据结构》 课程设计报告 题目: 栈的应用:表达式求值 (系): 信息科学与工程学院院 专业班级: 软件工程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(培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提 高程序设计水平。 《数据结构（C++版）》课设计报告2012—2013学年第一学期 课程名称数据结构 设计题目表达式求值 专业班级 姓名 学号 指导教师 课程设计题目：表达式求值 一、问题描述 对一个合法的中缀表达式求值。简单起见，假设表达式只包含+，-，*，/等4个双目运算符，且运算符本身不具有二义性，操作数均为一位整数。 二、基本要求 1.正确解释表达式； 2.符合四则运算规则； 3.输出最后的计算结果。 三、概要设计 对中缀表达式求值，通常使用“算符优先算法”。根据四则运算规则，在运算的每一步中，任意两个相继出现的运算符t和c之间的优先关系至多是下面三种关系之一： （1） t的优先级低于c； （2） t的优先级等于c； （3） t的优先级高于c。 为实现算符优先算法，可以使用两个工作栈：一个栈OPTR存放运算符；另一个栈OPND存放操作数，中缀表达式用一个字符串数组存储。 四、详细设计 利用类模板 #include 课程设计 教学院 课程名称 题目 专业 班级 姓名 同组人员 指导教师 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)，把一 个数字串转换为一个实型数，并压入运算数栈中。（整个程序的源代码 见附录，并有具体解释） 嘉应学院计算机学院 实验报告 课程名称：数据结构课程设计 开课学期：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) 源代码： //用来存储字符的结点类型 typedef struct CharNode { char c; struct CharNode *next; }CharNode; //用来存储数的结点类型 typedef struct IntNode { long double i; struct IntNode *next; }IntNode; //用来存储数的结点类型 typedef struct Node { long double n; struct Node_ys_char *next; }Node; //用来存储运算符的结点类型 typedef struct Node_ys_char { char c; struct Node_ys_char *next_c; struct Node *next; }Node_ys_char; char Precede(char x,char y)//运算符优先级判断{ int i,j; int from[5][5] ={ {0,0,-1,-1,0}, {0,0,-1,-1,0}, {1,1,0,0,1}, {1,1,0,0,1}, {0,0,-1,-1,0} };//定义一个二维数组存放算术符号的优先级 switch(x) { case '+':i=0;break; case '-':i=1;break; case '*':i=2;break; case '/':i=3;break; case '#':i=4;break; } switch(y) { case '+':j=0;break; case '-':j=1;break; case '*':j=2;break; case '/':j=3;break; case '#':j=4;break; } if(from[i][j]==1)//说明运算符i的优先级比j的优先级高return '>'; if(from[i][j]==-1) return '<'; else return '='; } //输入表达式，并对特殊情况做处理 CharNode *CreatRegister() { CharNode *top,*p,*q,*e; top=(CharNode *)malloc(sizeof(CharNode)); p=q=top; scanf("%c",&p->c); scanf("%c",&p->c); 数据结构课程设计 设计说明书表达式求值算法的实现（（（）（）（（ 学生姓名 学号 班级 成绩 指导教师 数学与计算机科学学院 2012年 9月 7日 数据结构课程设计评阅书 课程设计任务书 2011—2012学年第2学期 专业学号：姓名： 课程设计名称：数据结构课程设计 设计题目：表达式求值算法的实现 完成期限：自 2012 年 8 月 28 日至 2012 年 9 月 7 日共 2 周 栈的存储和相关运算是数据结构中数组部分的重点知识和技能。表达式求值算法可借助栈来完成，它的存储可以使用顺序结构也可以使用链式结构，这要根据具体的应用来决定。本课程设计按以下的要求运用C/ C++结构体、指针、数据结构等基知识编程实现。 任务要求：1）阐述设计思想,画出流程图;2）任意输入一个表达式（算术、逻辑、关系表达式）；3）建立栈；4）借助栈的相关运算完成表达式求值过程;5）将表达式及其运算结果按照其数学形式打印输出; 6）说明测试方法,写出完整的运行结果,较好的界面设计；7）按照格式要求完成课程设计说明书。设计要求: 1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。 2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图； 3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架； 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚； 5）程序调试与测试：能够熟练掌握调试工具的各种功能，设计测试数据确保程序正确。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果； 6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析； 7）编写课程设计报告； 指导教师（签字）：教研室主任（签字）： 批准日期：年月日 课程设计报告 课程名称数据结构 课题名称中缀算术表达式求值 专业通信工程 班级通信0902 学号 姓名 指导教师 2011 年07 月01 日 湖南工程学院 课程设计任务书 课程名称数据结构 课题中缀算术表达式求值 专业班级通信工程0902 学生姓名 学号 指导老师 审批 任务书下达日期2011 年06 月27日 任务完成日期2011 年07 月01日 设计要求： 1. 课程设计报告规范 （1）需求分析 a.程序的功能。 b.输入输出的要求。 （2）概要设计 a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系； 每个模块的功能。 b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是 什么样的结构，它们之间有什么关系等。 （3）详细设计 a.采用C语言定义相关的数据类型。 b．写出各模块的类C码算法。 c.画出各函数的调用关系图、主要函数的流程图。 （4）调试分析以及设计体会 a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输 出结果和含有错误的输入及输出结果。 b.程序调试中遇到的问题以及解决问题的方法。 c.课程设计过程经验教训、心得体会。 （5）使用说明 用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步 骤。 （6）书写格式 a.设计报告要求用A4纸打印成册： b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行 距为22。 （7）附录 源程序清单（带注释） 2. 考核方式 指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤（占10%） （2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%） （3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%） 注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。 （5）独立完成情况（占10%）。 3 . 课程验收 （1）运行所设计的系统。 （2）回答有关问题。 （3）提交课程设计报告。 （4）提交软盘（源程序、设计报告文档）。 （5）依内容的创新程度，完善程序情况及对程序讲解情况打分。 2 进度安排 第19 周：星期一8：00——12：00 上课 星期一14：30——18：30 上机 星期二14：30——18：30 上机 星期四8：00——12：00 上机 附： 课程设计报告装订顺序：封面、任务书、目录、正文、评分表、附件（A4大小的图纸及程序清单）。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。 正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现 XXXXXX大学《数据结构》课程设计报告 班级： 学号： 姓名： 指导老师： 目录 一算术表达式求值 一、需求分析 二、程序的主要功能 三、程序运行平台 四、数据结构 五、算法及时间复杂度 六、测试用例 七、程序源代码 二感想体会与总结 算术表达式求值 一、需求分析 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 二、程序的主要功能 （1）从键盘读入一个合法的算术表达式，输出正确的结果。 （2）显示输入序列和栈的变化过程。 三、程序运行平台 Visual C++ 6.0版本 四、数据结构 本程序的数据结构为栈。 （1）运算符栈部分： struct SqStack //定义栈 { char *base; //栈底指针 char *top; //栈顶指针 int stacksize; //栈的长度 }; int InitStack (SqStack &s) //建立一个空栈S { if (!(s.base = (char *)malloc(50 * sizeof(char)))) exit(0); s.top=s.base; s.stacksize=50; return OK; } char GetTop(SqStack s,char &e) //运算符取栈顶元素 { if (s.top==s.base) //栈为空的时候返回ERROR { printf("运算符栈为空!\n"); return ERROR; } else e=*(s.top-1); //栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OK return OK; } int Push(SqStack &s,char e) //运算符入栈 { if (s.top-s.base >= s.stacksize) { printf("运算符栈满!\n"); 数据结构课程设计报告 课设题目：算式表达式求值系统 班级: 软件1202 姓名： 学号： 指导教师: 李斌 成绩: 2013 年1月 目录 一、需求分析 (2) 二、概要设计 (2) (一）设计思想 (2) (二）实现方法 (2) (三）模块整体设计图 (3) (四）函数功能介绍 (3) 三、详细设计 (4) （一）数据结构设计 (4) （二）模块接口设计 (4) （三）盒图 (5) 四、调试分析 (7) 五、用户手册 (7) 六、测试结果 (8) 七、附录 (9) 附录一设计体会 (9) 附录二源程序 (9) 一、需求分析 算式表达式求值是程序设计语言编译中一个最基本的问题。本次任务要求完成一个四则算式表达式求值系统。具体需求为：当用户输入一个四则算式（包括加、减、乘、除和括号），如（12+3）*2+9*4，输出其计算结果。具体要求如下：（一）要实现栈的基本操作算法，包括初始化栈、进栈、出栈等。 （二) 在本程序中，表达式中的元素限定为char型，表达式长度不超过100，表达式以“#”号为结束标志。 （三）要求程序输出表达式的计算结果。 二、概要设计 （一）设计思想 本次四则算式表达式求值的程序采用的是中缀表达式的求值的方法。所谓中缀表达式，就是指每个二目运算符在两个运算量的中间，假设所讨论的算术运算符包括：+ 、- 、*、/、%、^（乘方）和括号（）。而本次程序的编写只涉及四则运算（+、-、*、/）和括号（）。 设运算规则为： ．运算符的优先级为：（）> *、/> +、- ； ．有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行； 表达式作为一个满足表达式语法规则的串存储，如表达式“3*2^（4+2*2-１*3）-5”,它的的求值过程为：自左向右扫描表达式，当扫描到3*2时不能马上计算，因为后面可能还有更高的运算，正确的处理过程是：需要两个栈：对象栈s1和算符栈s2。当自左至右扫描表达式的每一个字符时，若当前字符是运算对象，入对象栈，是运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符，直到遇到结束符“#”。 根据运算规则，左括号“（”在栈外时它的级别最高，而进栈后它的级别则最低了; 乘方运算的结合性是自右向左，所以，它的栈外级别高于栈内; 就是说有的运算符栈内栈外的级别是不同的。当遇到右括号“）”时，一直需要对运算符栈出栈，并且做相应的运算，直到遇到栈顶为左括号“(”时，将其出栈，因此右括号“）”级别最低但它是不入栈的。对象栈初始化为空。根据以上分析，每个运算符栈内、栈外的级别如下： 算符栈内级别栈外级别 ^ 3 4 *、/、% 2 2 +、- 1 1 ( 0 4 ） -1 -1 （二）实现方法 二课程设计2——算术表达式求值 一、需求分析 二、程序的主要功能 三、程序运行平台 四、数据结构 五、算法及时间复杂度 六、测试用例 七、程序源代码 三感想体会与总结 算术表达式求值 一、需求分析 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 二、程序的主要功能 （1）从键盘读入一个合法的算术表达式，输出正确的结果。 （2）显示输入序列和栈的变化过程。 三、程序运行平台 Visual C++ 6.0版本 四、数据结构 本程序的数据结构为栈。 （1）运算符栈部分： struct SqStack //定义栈 { char *base; //栈底指针 char *top; //栈顶指针 int stacksize; //栈的长度 }; int InitStack (SqStack &s) //建立一个空栈S { if (!(s.base = (char *)malloc(50 * sizeof(char)))) exit(0); s.top=s.base; s.stacksize=50; return OK; } char GetTop(SqStack s,char &e) //运算符取栈顶元素 { if (s.top==s.base) //栈为空的时候返回ERROR { printf("运算符栈为空!\n"); return ERROR; } else e=*(s.top-1); //栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OK return OK; } int Push(SqStack &s,char e) //运算符入栈 { if (s.top-s.base >= s.stacksize) { printf("运算符栈满!\n"); s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); //栈满的时候，追加5个存储空间 if(!s.base) exit (OVERFLOW); s.top=s.base+s.stacksize; s.stacksize+=5; } *(s.top)++=e; //把e入栈 return OK; } int Pop(SqStack &s,char &e) //运算符出栈 { if (s.top==s.base) //栈为空栈的时候，返回ERROR { printf("运算符栈为空!\n"); return ERROR; } else { 实用标准文档 二课程设计2——算术表达式求值 一、需求分析 二、程序的主要功能 三、程序运行平台 四、数据结构 五、算法及时间复杂度 六、测试用例 七、程序源代码 三感想体会与总结 算术表达式求值 一、需求分析 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 二、程序的主要功能 （1）从键盘读入一个合法的算术表达式，输出正确的结果。 （2）显示输入序列和栈的变化过程。 三、程序运行平台 Visual C++ 6.0版本 四、数据结构 本程序的数据结构为栈。 （1）运算符栈部分： struct SqStack //定义栈 { char *base; //栈底指针 char *top; //栈顶指针 int stacksize; //栈的长度 }; int InitStack (SqStack &s) //建立一个空栈S { if (!(s.base = (char *)malloc(50 * sizeof(char)))) exit(0); s.top=s.base; s.stacksize=50; return OK; } char GetTop(SqStack s,char &e) //运算符取栈顶元素 { if (s.top==s.base) //栈为空的时候返回ERROR { printf("运算符栈为空!\n"); return ERROR; } else e=*(s.top-1); //栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OK return OK; } 实验3：栈与队列实验 ——基于栈结构的中缀表达式求值 一、问题描述 从键盘输入任意中缀表达式字符串，读字符串，利用栈结构实现表达式求值。 二、输入与输出 输入：从键盘中缀表达式如： 32＋5×（6－4） 输出：计算结果42 三、需求分析 1.定义两个栈结构，数栈用于存放表达式中的数，符号栈用于存放表达式中的符号，实现栈的运算 2.在读数的时候考虑多位运算 3.实现表达式求值 四、开发工具与环境 硬件设备：微型计算机系统 软件环境：操作系统Windows 开发工具：Devc++ 五、概要设计 参考结构定义 typedef struct /* 运算符栈 */ { char *base,*top; int stacksize; }SqStack; typedef struct /* 运算数栈 */ { int *base,*top; int stacksize; }SqStack1; int priority[7][7]={{'>', '>', '<', '<', '<', '>', '>'}, // + {'>', '>', '<', '<', '<', '>', '>'}, // - {'>', '>', '>', '>', '<', '>', '>'}, // * {'>', '>', '>', '>', '<', '>', '>'}, // / {'<', '<', '<', '<', '<', '=', ' '}, // ( {'>', '>', '>', '>', ' ', '>', '>'}, // ) {'<', '<', '<', '<', '<', ' ', '='} // # }; /*用于比较符号优先级的全局二维数组*/ 2．各函数模块 void InitStack(SqStack *s); 操作结果：初始化运算符栈 char GetTop(SqStack *s); 操作结果：得到运算符栈的栈顶元素 void Push(SqStack *s,char e); 操作结果：对运算符栈进行压栈操作 int IsNumber(char c); 操作结果：判断一个字符是否是数字 int MidExpression_Eval(char Express[]); 操作结果：计算中缀表达式的值 int Operate (int a,char x,int b); 操作结果：计算表达式axb，并返回结果 六、详细设计 #include数据结构表达式求值实验报告
中缀表达式求值
数据结构实验二——算术表达式求值实验报告
算术表达式求值演示程序
数据结构课程设计_表达式求值问题
数据结构算术表达式求值实验报告
表达式求值课程设计报告
表达式求值
算术表达式求值课程设计报告
数据结构课程设计-表达式求值问题
C语言_算术表达式求值_代码
算术表达式求值课设报告
数据结构课程设计报告-中缀算术表达式求值
数据结构教学规划表达式求值【完全版】
算术表达式求值系统
最新《数据结构》算术表达式求值
《大数据结构》算术表达式求值
基于栈结构的中缀表达式求值
相关主题
文本预览