#include
#include
#include
#define FALSE 0
#define TRUE 1
#define MAXSIZE 100 /*存储空间初始分配量*/
#define N 10 /*存储空间增加量*/
#define NULL 0
typedef struct StStack{
float *base; /*在栈构造之前和销毁之后，base的值为0*/
float *top; /*栈顶指针*/
int size; /*当前已分配的存储空间，以元素为单位*/
}StStack;
typedef struct StStack_c{
char *base;
char *top;
int size;
}StStack_c;
void InitStack(StStack *S){
/*构造一个空栈S存储数据*/
S->base=(float *)malloc(MAXSIZE*sizeof(float));
if(!S->base) exit(TRUE); /*存储分配失败*/
S->top=S->base;
S->size=MAXSIZE;
}
void InitStack_c(StStack_c *S){
/*构造一个空栈S存储符号；*/
S->base=(char *)malloc(MAXSIZE*sizeof(char));
if(!S->base) exit(TRUE); /*存储分配失败*/
S->top=S->base;
S->size=MAXSIZE;
}
void Push(StStack *S,float e){
/*插入元素e为新的栈顶元素*/
if(S->top==S->base+S->size)
{ S->base=(float *)realloc(S->base,(S->size+N)*sizeof(float)); /*若栈满则增存储空间*/
if(!S->base) exit(TRUE); /*存储分配失败*/
S->top=S->base+S->size; /*增加存储空间*/
S->size+=N;
}
S->base[(S->top++)-S->base]=e;
}
void Push_c(StStack_c *S,char ch){
/*插入元素ch为新的栈顶元素*/
if(S->top==S->base+S->size)
{ S->base=(char *)realloc(S->base,(S->size+N)*sizeof(char)); /*若栈满则增存储空间*/
if(!S->base) exit(TRUE); /*存储分配失败*/
S->top=S->base+S->size;
S->size+=N;
}
S->base[(S->top++)-S->base]=ch;
}
void Pop(StStack *S,float *e){
/*若栈不空，则删除S的栈顶元素，用e返回其值*/
if(S->top!=S->base)
*e=S->base[(S->top--)-S->base-1];
}
void Pop_c(StStack_c *S,char *ch){
/*若栈不空，则删除S的栈顶元素，用ch返回其值*/
if(S->top!=S->base)
*ch=S->base[(S->top--)-S->base-1];
}
float GetTop(StStack *S){
/*若栈不空，则用e返回S的栈顶元素*/
int n; /*存放栈顶元素的位置*/
float e;
if(S->top!=S->base)
{n=S->top-S->base-1;
e=S->base[n];
return e; /*返回S的栈顶元素*/
}
}
char GetTop_c(StStack_c *S){
/*若栈不空，则用ch返回S的栈顶元素*/
int n;
char ch;
if(S->top!=S->base)
{n=S->top-S->base-1;
ch=S->base[n];
return ch;
}
}
int In_c(char ch){
/*判断是否为运算符，是则返回TRUE，否则返回FALSE*/
if(ch=='+'||ch=='-') return TRUE;
else if(ch=='*'||ch=='/') return TRUE;
else if(ch=='('||ch==')') return TRUE;
else if(ch=='#') return TRUE;
else return FALSE;
}
int check_ch(char *ch){
/*判断输入是否符合表达式的要求*/
while(*ch!='#')
{if(*ch=='.'||*ch>='0'&&*ch<='9'||In_c(*ch)) /*表达式的限制条件*/
{if(*ch>='0'&&*ch<='9') {ch++;continue;}
if(*ch=='.') /*小数点前后不是数字的处理*/
{if(In_c(*(++ch))) return FALSE;
else ch--;
if(In_c(*(--ch))) return FALSE;
else ch++;
}/*if-2*/
else
{if(In_c(*(++ch))&&In_c(*(--ch))) /*相邻的两运算符的处理*/
{if(*(++ch)=='(') continue; /*在'('前的运算符情况处理*/
else ch--;
if(*(++ch)=='-'&&*(--ch)=='(') {ch++; continue;} /*()内第一位数为负的运算符处理*/
else ch--;
if(*(++ch)!='#'&&*(--ch)==')') {ch++; continue;} /*在')'后的运算符情况处理*/
else if(*ch--!='#') return FALSE;
}/*if-3*/
else ch--;
}/*if-else2*/
ch++;
}/*if-1*/
else return FALSE;
}/*while*/
if(*ch=='#') return TRUE;
}
float operate(float x,char c,float y){
/*基本运算的实现*/
switch(c){
case '+': return x+y;
case '-': return x-y;
case '*': return x*y;
case '/': if(y!=0) return x/y; /*被除数不为0*/ else
{printf("\nThe divisor is 0,can't permit !\n");
exit(1);
}
}
}
char Precede(char x,char y){
/*运算符的优先权*/
switch(x){
case '+': if(y=='*'||y=='/'||y=='(') return '<';
else return '>';
case '-': if(y=='*'||y=='/'||y=='(') return '<';
else return '>';
case '*': if(y=='(') return '<';
else return '>';
case '/': if(y=='(') return '<';
else return '>';
case '(': if(y==')') return '=';
else return '<';
case ')': if(y!='(') return '>';
case '#': if(y=='#') return '=';
else if(y!=')') return '<';
}
}
int changeN(StStack *S,char *ch){
/*将字符转换为数值*/
int j,h,k=0;
float m,n=0;
char c;
while(*ch>='0'&&*ch<='9'||*ch=='.')
{n=n*10+(*ch-48); /*将字符转换为数值存入n中*/
k++; /*k记录数值的位数*/
ch++;
if(*ch=='.') /*若有小数，将n,k存入m,h，并初始化方便小数的转换*/ {m=n;n=0;
h=k;k=0;
c=*ch;ch++; /*将'.'存入c,对下一个字符进行操作*/
}
if(c=='.'&&In_c(*ch)==TRUE) /*对小数部分的处理*/
{for(j=0;j n=n/10; n+=m; k=++k+h; } }/*while*/ Push(S,n); /*将转换好的数值入栈*/ return k; /*返回数值的位数*/ } int DealNeg(StStack *S,char *ch){ /*对括号内负数的处理*/ int k=0,i=0; float e,n=0; if(*(--ch)=='('&&*(++ch)=='-') {k=changeN(S,++ch); Pop(S,&e); n=-1*e; Push(S,n); return k; } else return FALSE; } void Operating(char *c,StStack *OPND,StStack_c *OPTR) /*表达式运算过程*/ {char ch; int k=0,i=0; float a,b,e; if(c[0]=='-'&&(!In_c(c[1]))) /*判断首数是负数则进栈*/ {k=changeN(OPND,&c[1]); i+=k+1; /*首数是负数保存其位数*/ Pop(OPND,&e); e=-1*e; /*保存负数*/ Push(OPND,e); } do{ if(!In_c(c[i])) /*不是运算符则转换为数值并进栈*/ {k=changeN(OPND,&c[i]); i+=k-1; /*下一个字符在串中的下标*/ } else {if(k=DealNeg(OPND,&c[i])) i+=k; /*判断是负数则进栈*/ else {switch(Precede(GetTop_c(OPTR),c[i])){ case '<': Push_c(OPTR,c[i]); /*栈顶元素优先权低*/ break; case '=': Pop_c(OPTR,&ch); /*脱括号并接收下一字符*/ break; case '>': Pop_c(OPTR,&ch); /*退栈并将输出结果入栈*/ Pop(OPND,&b); Pop(OPND,&a); e=operate(a,ch,b); /*将运算结果存入e中*/ if(GetTop_c(OPTR)=='-') /*若结果前为'-'则取其相反数*/ {Pop_c(OPTR,&ch); Push_c(OPTR,'+'); e=-1*e; } Push(OPND,e); if(c[i]!='#'&&c[i]!=')') /*当前符号不是'#'则入栈*/ Push_c(OPTR,c[i]); else i--; }/*switch()*/ }/*if-else-1*/ }/*if-else-2*/ i++; }while(GetTop_c(OPTR)!='#'||c[i]!='#'); /*判断表达式是否结束*/ } void main() {char str[40 ],*c,ch; float i=0,n,f; FILE *fp; StStack s1,*OPND; /*定义关于数值的栈*/ StStack_c s2,*OPTR; /*定义关于字符的栈*/ OPND=&s1; OPTR=&s2; clrscr(); c=str; if((fp=fopen("date.txt","w"))==NULL) /*打开文档并将正确的表达式和结果写 入文档*/ {printf("can't open the file.\n");i=1;} /*出错提示*/ do{ InitStack_c(OPTR); Push_c(OPTR,'#'); InitStack(OPND); do{ printf("\nPlease input the expression: "); scanf("%s",c);getchar(); if(check_ch(c)) f=1; else {printf("\nWarning: the expression you input is non-standard!!\n"); f=0; } }while(f!=1); /*表达式若不符合要求则重新输入*/ Operating(c,OPND,OPTR); n=GetTop(OPND); printf("\nThe result of the expression is: %.2f.\n",n); if(i!=1) /*将表达式和结果写入文档*/ {fputs("\nThe expression is: \0",fp); fputs(c,fp); fputs("\nThe result is: \0",fp); fprintf(fp,"%.2f",n); } printf("\nDo you want to calculate the next expression(y/n): "); ch=getchar(); getchar(); }while(ch=='y'||ch=='Y'); fclose(fp); /*关闭文件*/ } 数理学院 课程设计报告书 课程名称数据结构课程设计 设计题目算术表达式求值演示 专业班级 学号 姓名 指导教师 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; 竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告 篇一：数据结构实验二——算术表达式求值实验报告 《数据结构与数据库》 实验报告 实验题目算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系pb0920603 姓学 邮名：李维谷号：pb09206285箱： liwg@https://www.doczj.com/doc/846593867.html,指导教师：贾伯琪 实验时间：20XX年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个(:数据结构表达式求值实验报告)算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 《数据结构与数据库》 实验报告 实验题目 算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系PB0920603 姓名：李维谷 学号：PB09206285 邮箱：liwg@https://www.doczj.com/doc/846593867.html, 指导教师：贾伯琪 实验时间：2010年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 输出结果：194.4 用栈进行表达式求值并输出逆波兰式（源代 码） #include "stdio.h" #include "malloc.h" #include "string.h" #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ char *top,*base; int csize; }*charstack,cstack; typedef struct{ float *top,*base; int fsize; }*floatstack,fstack; charstack initcharstack(){ charstack s; s=(charstack)malloc(sizeof(cstack)); s->base=s->top=(char*)malloc(STACK_INIT_SIZE * sizeof(char)); s->csize=STACK_INIT_SIZE; return s; } floatstack initfloatstack(){ floatstack s; s=(floatstack)malloc(sizeof(fstack)); s->base=s->top=(float*)malloc(STACK_INIT_SIZE * sizeof(float)); *(s->top)=-1; s->fsize=STACK_INIT_SIZE; return s; } char chargettop(charstack s){ return *(s->top-1); } float floatgettop(floatstack s){ return *(s->top-1); } void charpush(charstack s,char c){ if((s->top-s->base)>=s->csize){ s->base =(char *)realloc(s->base ,(s->csize +STACKINCREMENT)*sizeof(char)); s->top=s->base +s->csize ; s->csize +=STACKINCREMENT; } 逆波兰表达式求值 一、需求分析 1、从键盘中输入一个后缀表达式，该表示包括加减乘除等操作符，以及正整数作为操 作数等。 2、用堆栈来实现 3、测试数据 输入：2 3 * 1 – # 输出：2 3 * 1 -- =5 二、概要设计 抽象数据类型 需要一个浮点数栈来存储还没有计算的浮点数或者运算的结果。 ADT Stack 数据成员：int size; int top; //分别用于存储栈大小、栈顶位置 float *listArray;//存储浮点型数字的数组 成员函数： bool push(float it); bool pop(float& it); bool isEmpty(); //判断栈为空 bool isOne();//判断栈是否只有一个元素 算法的基本思想 1.逐一扫描字符串，用ascii码进行判断，如果该字符是数字，则利用x=x*10+str[i]-48 将数据由字符类型转换为浮点型数据； 2.如果字符是‘.’，则将‘.’转化为小数点，并将‘.’后的数据转化为小数部分； 3.遇到空格前是数据的，将x押入栈； 4.如果该字符是’+’，’-’，’*’或’/’，判断栈里的元素是否少于两个个，如果少于两个， 报错；如果大于等于两个，就弹出两个数据，并进行相应的计算； 程序的流程 输入字符串，程序对字符串依次扫描。扫描一位，处理一位。扫描完成后，判断栈里是不是只有一个数据，若是，得到正确结果；若不是，则表达式出错。 三、详细设计 物理数据类型 用浮点数类型的栈存储运算中要用的数据，需要入栈、出栈，故设计如下的浮点类型的栈： class Stack { private: int size; int top; float *listArray; public: Stack(int sz=20); ~Stack(); 软件技术基础实验报告 实验名称：表达式计算器 系别：通信工程 年级： 班级： 学生学号： 学生姓名： 《数据结构》课程设计报告 题目简易计算表达式的演示 【题目要求】 要求：实现基本表达式计算的功能 输入：数学表达式，表达式由整数和“+”、“-”、“×”、“/”、“（”、“）”组成输出：表达式的值 基本操作：键入表达式，开始计算，计算过程和结果记录在文档中 难点：括号的处理、乘除的优先级高于加减 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} 源代码： //用来存储字符的结点类型 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); 表达式求值课程设计报告 表达式求值 《数据结构》 课程设计报告 题目: 栈的应用:表达式求值 (系): 信息科学与工程学院院 专业班级: 软件工程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(培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提 高程序设计水平。 课程设计 教学院 课程名称 题目 专业 班级 姓名 同组人员 指导教师 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)，把一 个数字串转换为一个实型数，并压入运算数栈中。（整个程序的源代码 见附录，并有具体解释） 表达式求值 一目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题 目，利用C/C++语言进行程序设计，并规地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描 述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果 二需求分析 设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果。对于这个程序我们从输入，输出，和功能三方面来分析。 1.程序输入：从键盘上输入表达式，一个算术表达式，由常量、运算符和括号组成（以字符串形式输入，不含变量）。为了简化，操作数只能为浮点数，操作符为“ +”、“-”、“*”、“/”、“（”、“）”，用“#“表示结束。 2.程序输出：表达式运算结果，运算符栈、运算数栈、输入字符和主要操作变化过程，如运算符栈、运算数栈的出入记录，字符出入栈的过程，打印出完整的过程。 3.功能要求及说明：从键盘上输入表达式。分析该表达式是否合法（包含分母不能为零的情况）： （1）是数字，则判断该数字的合法性。 （2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 （3）若是其它字符，则返回错误信息。 若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。 三概要设计 1.数据结构的选择： 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。 汇编语言实训课程设计任务书 题目：表达式求值程序班级：计算机科学与技术一班 学生姓名：赵旭尧学号： 14730141 题目类型：软件工程（R）指导教师：刘树群 一．题目简介 该设计要求学生使用汇编语言，设计并开发出针对四则运算表达式进行求 值的命令行或窗口程序。 通过该题目的设计过程，可以培养学生结构化程序设计的思想，加深对汇 编语言基本语言要素和流程结构的理解，针对汇编语言中的重点和难点内容进 行训练，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格。 得到软件工程的综合训练，提高解决实际问题的能力。 二．设计任务 1、查阅文献资料，一般在5篇以上； 2、通过键盘输入表达式，进行针对整数的“加减乘除”四则运算表达式 进行求值，有良好的界面； 3、完成软件结构设计和算法设计； 4、完成系统的软件开发和测试工作； 5、撰写设计说明书； 6、做好答辩工作。 三．主要内容、功能及技术指标 1、实现功能及指标：①使用Win32的窗口程序模式，实现表达式求值程序 及测试界面程序的设计与开发；②支持整数的四则运算、位运算和小括号等； ③使用文本框对表达式进行交互式编辑和输出。 2、问题分析及解决方案框架确定：充分地分析和理解问题本身，弄清要求 做什么。在确定解决方案框架过程中，综合考虑系统功能，考虑怎样使系统结 构清晰、合理、简单和易于调试。最后确定每个过程和函数的简单功能，以及 过程（或函数）之间的调用关系，并画出函数之间的调用关系图。 3、详细设计和编码：定义相应的存储结构，确定各个函数的算法，并画出 流程图，在此基础上进行代码设计，每个明确的功能模块程序一般不超过200 行，否则要进一步划分。 实用标准文档 二课程设计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; } 数据结构课程设计 设计说明书表达式求值算法的实现（（（）（）（（ 学生姓名 学号 班级 成绩 指导教师 数学与计算机科学学院 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）编写课程设计报告； 指导教师（签字）：教研室主任（签字）： 批准日期：年月日 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 { 程序设计实训报告— 表达式求值问题 完成者：何炜 班级：计科1501 学号： 完成日期：2016年7月14日星期四 目录 一、题目的内容及要求................................. 错误!未定义书签。 二、需求分析 ................................................ 错误!未定义书签。 三、概要设计 ................................................ 错误!未定义书签。 四、详细设计 ................................................ 错误!未定义书签。 五、源代码 .................................................... 错误!未定义书签。 六、运行结果及分析..................................... 错误!未定义书签。 七、收获及体会............................................. 错误!未定义书签。 一、题目的内容及要求 求解形如（a+b)*((c+d)*e+f*h*g)的简单算术表达式的求值问题。这种表达式只包括加、减、乘、除4种运算符。 为了实现表达式求值，可以首先读入原表达式（包括括号）并创建对应二叉树，其次对二叉树进行前序遍历、中序遍历、后续遍历（非递归），并输出逆波兰表达式，最后求解原表达式的值，同时对非法表达式格式能予以判断。 用二叉树的结构来存储表达式，后续遍历二叉树即可得到逆波兰表达式 二、需求分析 本程序能解决形如（a+b)*((c+d)*e+f*h*g)并以’#’作为结束标志的简单算术表达式的求值问题。 不仅能够求解出多位浮点数，而且能够对简单的非法表达式进行判断以避免程序异常退出。 三、概要设计 1.用户输入中缀表达式 2.程序将中缀表达式用二叉树的链式存储结构存储下来 3.前序、中序遍历这颗二叉树，输出对应的前缀、中缀表达式 4.后续遍历（非递归）这颗二叉树，并把遍历结果存储在顺序栈内， 并输出后缀表达式 5.对后缀表达式进行求值 目录 题目一.二叉树操作（1）二.算术表达式求 (1) 一、课程设计的目的 (1) 二、课程设计的内容和要求 (1) 三、题目一设计过程 (2) 四、题目二设计过程 (6) 五、设计总结 (17) 六、参考文献 (18) 题目一.二叉树操作（1）二.算术表达式求 一、课程设计的目的 本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求学生掌握《数据结构》中的各方面知识，还要求学生具备一定的C语言基础和编程能力。 （1）题目一的目的： 1、掌握二叉树的概念和性质 2、掌握二叉树的存储结构 3、掌握二叉树的基本操作 （2）题目二的目的： 1、掌握栈的顺序存储结构和链式存储结构 2、掌握栈的先进后出的特点 3、掌握栈的基本运算 二、课程设计的内容和要求 （1）题目一的内容和要求： 1、编写已知二叉树的先序、中序序列，恢复此二叉树的程序 2、编写求二叉树深度的程序 （2）题目二的内容和要求： 1、算术表达式由操作数、运算符和界限符组成。操作数是正整数，运算符为 加减乘除，界限符有左右括号和表达式起始 2、将一个表达式的中缀形式转化为相应的后缀形式 3、依据后缀表达式计算表达式的值 三、题目一设计过程 1、题目分析 现已知一棵二叉树的先序遍历序列和中序遍历序列，依次从先序遍历序列中取结点，由先序序列确定根结点(就是第一个字母)，每次取出一个结点就与中序遍历的序列进行比较，当相等的时候，中序遍历序列就被分成以该结点为根的二叉树子树，该结点左部分为左子树，右部分为右子树，直到取完先序列里的所有结点，则二叉树构造完毕（树用链式存储结构存储），用递归实现！ 由建好的二叉树，先判断这棵树是否为空，若不为空则找数的左子树，统计它的高度，然后找树的右子树，统计它的高度，比较左子树和右子树的高度，然后返回其中大的那个值加一，则求出数的高度。这里用递归实现！ 2、算法描述 main ( )（主函数） 先构造一颗二叉树，初始化为空，用来存储所构造的二叉树，并输入一棵树的先序序列和中序序列，并统计这个序列的长度。然后调用实现功能的函数。 void CreateBiTree(BiTree *T,char *pre,char *in,int len)（由先序序列和中序序列构造二叉树） 根据前序遍历的特点, 知前序序列(pre)的首个元素(pre[0])为根(root), 然后在中序序列(in)中查找此根(pre[0]), 根据中序遍历特点, 知在查找到的根(root) 前边的序列为左子树, 后边的序列为右子树。设根前边有n个元素，则又有, 在前序序列中，紧跟着根(root)的n个元素序列(即pre[1...n]) 为左子树, 在后边的为右子树，而构造左子树问题其实跟构造整个二叉树问题一样，只是此时前序序列为pre[1...n]), 中序序列为in[0...n-1], 分别为原序列的子串, 构造右子树同样。这里用递归实现！ int Depth(BiTree T)（求树的深度） 当所给的参数T是NULL时，返回0。说明这个树只有一个叶子节点深度为0，当所给的参数不是NULL时，函数调用自己看看这个参数的左分支是不是NULL， 数据结构课程设计源代码：表达式求值 0900340131 张宁2011.6.26 #include top++; /*入栈*/ } else if(f[i]==' ') /*遇到空格，跳过去，不进行处理*/ { i++; } else if(f[i]=='+') /*如果字符是运算符'+',则从操作数栈中取出两个元素进行相加*/ { x2=obst[--top]; x1=obst[--top]; obst[top]=x1+x2; /*将运算结果入栈*/ top++; i++; /*继续下一个字符*/ } else if(f[i]=='-') /*如果字符是运算符'-',则从操作数栈中取出两个元素进行相减*/ { x2=obst[--top]; x1=obst[--top]; obst[top]=x1-x2; /*将运算结果入栈*/ top++; i++; /*继续下一个字符*/ } else if(f[i]=='*') /*如果字符是运算符'*',则从操作数栈中取出两个元素进行相乘*/ { x2=obst[--top]; x1=obst[--top]; obst[top]=x1*x2; /*将运算结果入栈*/ top++; i++; /*继续下一个字符*/ } else if(f[i]=='/') /*如果字符是运算符'/',则从操作数栈中取出两个元素进行相除*/ { x2=obst[--top]; x1=obst[--top]; obst[top]=x1/x2; /*将运算结果入栈*/ top++; i++; /*继续下一个字符*/ } } return obst[0]; /*最后栈中只剩下一个元素，即为后缀表达式的值*/算术表达式求值演示程序
数据结构表达式求值实验报告
数据结构实验二——算术表达式求值实验报告
用栈进行表达式求值并输出逆波兰式(源代码)
逆波兰表达式求值(实验报告及C 源码)
数据结构算术表达式求值实验报告
C语言_算术表达式求值_代码
表达式求值课程设计报告
算术表达式求值课程设计报告
数据结构课程设计：算术表达式
表达式求值程序设计说明书
《大数据结构》算术表达式求值
算术表达式求值课设报告
数据结构教学规划表达式求值【完全版】
算术表达式求值系统
最新《数据结构》算术表达式求值
程序设计实训报告—表达式求值问题
c语言实现一.二叉树操作 二.用栈实现算术表达式求值 课设报告
表达式求值源代码(数据结构课程设计)
相关主题
文本预览