#include
#include
struct node // 栈结构声明
{
int data; // 数据域
struct node *next; // 指针域
};
typedef struct node stacklist; // 链表类型
typedef stacklist *link; // 链表指针类型
link operand=NULL; // 操作数栈指针
link push(link stack,int value) // 进栈
{
link newnode; // 新结点指针
newnode=new stacklist; // 分配新结点
if (!newnode)
{
printf("分配失败！");
return NULL;
}
newnode->data=value; // 创建结点的内容
newnode->next=stack;
stack=newnode; // 新结点成为栈的开始return stack;
}
link pop(link stack,int *value) // 出栈
{
link top; // 指向栈顶
if (stack !=NULL)
{
top=stack; // 指向栈顶
stack=stack->next; // 移动栈顶指针
*value=top->data; // 取数据
delete top; // 吸收结点
return stack; // 返回栈顶指针}
else
*value=-1;
}
int empty(link stack) // 判栈空
{
if (stack!=NULL)
return 1;
else
return 0;
}
int isoperator(char op) // 判运算符
{
switch (op)
{
case'+':
case'-':
case'*':return 1; // 是运算符,返回1
case'/':return 0; // 不是运算符,返回0
}
}
int getvalue(int op,int operand1,int operand2) // 计算表达式值
{
switch((char)op)
{
case'*':return(operand1*operand2);
case'/':return(operand1/operand2);
case'+':return(operand1+operand2);
case'-':return(operand1-operand2);
}
}
void main() // 主函数
{
char exp[100];
int operand1=0; // 定义操作数1
int operand2=0; // 定义操作数2
int result=0; // 定义操作结果
int pos=0;
printf("\t\n 请输入后缀表达式：");
gets(exp); // 读取表达式
printf("\t\n\n 后缀表达式[%s]的计算结果是：",exp);
while (exp[pos] !='\0' && exp[pos] !='\n') // 分析表达式字符串
{
if (isoperator(exp[pos])) // 是运算符，取两个操作数
{
operand=pop(operand,&operand1);
operand=pop(operand,&operand2);
operand=push(operand,getvalue(exp[pos],operand1,operand2));// 计算结果入栈
}
else
operand=push(operand,exp[pos]-48); // 是操作数，压入操作数栈pos++; // 移到下一个字符串位置}
operand=pop(operand,&result); // 弹出结果
printf("%d\n",result); // 输出
}
表达式求值课程设计报告 表达式求值 《数据结构》 课程设计报告 题目: 栈的应用:表达式求值 (系): 信息科学与工程学院院 专业班级: 软件工程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(培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提 高程序设计水平。
数理学院 课程设计报告书 课程名称数据结构课程设计 设计题目算术表达式求值演示 专业班级 学号 姓名 指导教师
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;
湖南人文科技学院计算机科学技术系 课程设计说明书 课程名称:数据结构 课程代码: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.
一、设计思想 首先，将中缀表达式转换为后缀表达式。转换算法思路：设中缀表达式已存入数组E[n]；由于后缀表达式中操作数的次序与中缀表达式一致，故扫描到中缀表达式操作数时直接输出到B[n]即可；对于运算符，视其优先级别，优先级高的运算符先输出；设一存放运算符的栈s，先将s置空；依次扫描E[n]中各分量E[i]送x： 若x=“”（结束符），依次输出栈s中运算符，转换结束； 若x=操作数，直接输出x到B[n]中； 若x=‘）’，反复退栈输出栈s中子表达式运算符，直到栈顶符=‘（’，并退掉栈顶的‘（’； 若x=操作符，反复退栈输出栈s中运算符，直到栈顶符 三、源代码 下面给出的是用后缀表达式求值算法实现的程序的源代码： #include 实验表达式求值问题 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<<"栈创建失败，退出!"< 用栈进行表达式求值并输出逆波兰式（源代 码） #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.中缀转后缀算法 此算法分两步实现：先将算术表达式转换为后缀表达式，然后对后缀表达式进行计算。具体实现方法如下： （1）中缀转后缀 需要建一个操作符栈op和一个字符数组exp，op栈存放操作符，字符数组用来存放转换以后的后缀表达式。首先，得到用户输入的中缀表达式，将其存入str数组中。 对str数组逐个扫描，如果是数字或小数点，则直接存入exp数组中，当扫描完数值后，在后面加一个#作为分隔符。 如果是操作符，并且栈为空直接入栈，如果栈不为空，与栈顶操作符比较优先等级，若比栈顶优先级高，入栈；如果比栈顶优先级低或相等，出栈将其操作符存到exp数组中，直到栈顶元素优先等级低于扫描的操作符，则此操作符入栈；如果是左括号，直接入栈，如果是右括号，出栈存入exp数组，直到遇到左括号，左括号丢掉。然后继续扫描下一个字符，直到遇到str中的结束符号\0，扫描结束。结束后看op栈是否为空，若不为空，继续出栈存入exp数组中，直到栈为空。到此在exp数组最后加结束字符\0。 我们就得到了后缀表达式。 （2）后缀表达式计算 此时需要一个数值栈od来存放数值。对exp数组进行逐个扫描，当遇到数字或小数点时，截取数值子串将其转换成double类型的小数，存入od栈中。当遇到操作符，从栈中取出两个数，进行计算后再放入栈中。继续扫描，知道扫描结束，此时值栈中的数值就是计算的结果，取出返回计算结果。 2.两个栈实现算法 此算法需要两个栈，一个值栈od，一个操作符栈op。将用户输入的数学表达式存入str数组中，对其数组进行逐个扫描。 当遇到数字或小数点，截取数值子串，将其转换成double类型的数值存入od栈中； 当遇到左括号，直接入op栈；遇到右括号，op栈出栈，再从值栈od中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到操作符栈栈顶为左括号，将左括号丢掉。 如果遇到操作符，若op栈为空，直接入栈；若栈不为空，与栈顶元素比较优先等级，若比栈顶操作符优先等级高，直接入op栈，如果低于或等于栈顶优先等级，op栈出栈，再从值栈中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到栈顶优先等级低于扫描的操作符等级，将此操作符入op栈。继续扫描直到遇到str中的结束字符\0，扫描结束。此时看操作符栈是否为空，若不为空，出栈，再从值栈中取出两个数值进行计算，将其结果存入值栈，一直进行此操作，直到操作符栈为空。此时把值栈中的数值取出，即为所得的最终计算结果。 二、算法流程图 第一种算法：中缀转后缀算法 一、设计思想 计算算数表达式并求值，采取的共有两种方法： 1.先将算数表达式转化为后缀表达式，然后对后缀表达式进行计算。 2.对算数表达式进行直接的计算。 第一种算法 这种解决方案又分为两步： 1.将表达式先转化为后缀表达式的字符串数组 2.利用后缀表达式进行计算 在转化过程中，第一，建立一个存符号的栈，和一个字符串数组，用来存放转化以后的表达式 然后，对于得到的用户输入的字符串进行逐个的扫描，如果是数组或者小数点，则直接存放到数组中，并且在后面加入一个分隔符，如果是操作符，则和栈中的已存的进行比较，如果比栈中的操作符的优先级高，则直接入栈，如果优先级低或相等，则栈中元素出栈，存到字符串中，然后再次检查栈顶，直到栈中元素的优先级低于扫描操作符，则此操作符入栈，然后扫描下一个字符，直到遇到字符串的结束符号\0，扫描结束。数组中存的就是后缀表达式。得到后缀表达式后，进行计算，要用到数值栈。首先要将字符表示的数字转化为浮点小数，然后进行扫描，遇到数值，放入栈中，遇到操作符，就从栈中取出两个数，进行计算后再放入栈中，扫描下一个，最后的计算结果就存到了栈中，直接取出栈内元素，就是计算的最后结果。 第二种算发 首先要建立两个栈，一个用来存放操作符，一个用来存放数值。开始对用户输入的字符串进行扫描，如果是数字字符或者小数点，则将字符转化为浮点数存到数栈里，如果是操作符，则观察符号栈，如果栈顶元素的优先级低于观察的操作符，则操作符入栈，如果栈顶元素的优先级高于或者等于观察的操作符，则从数值栈中取出两个浮点数，从符号栈中取出栈顶的操作符，然后进行相应的数值计算，所得的结果再存到数值栈中，重复这样的操作，直到符号栈中栈顶元素的优先级低于观察的操作符，则此操作符入栈，然后对下一个字符进行扫描。如果是左括号，则不进行优先级的比较，直接入栈，入栈后优先级为-1。如果是右括号，则从数值栈中取两个操作数，符号栈中取出一个符号，然后进行计算后得数放入数栈中，不断进行此类操作，直到从栈中取出的是左括号为止，左括号去掉，扫描下一个。扫描结束后，计算也结束了，计算的结果就存放在数值栈中，最后把数值栈中的数取出，就是所得的计算结果。 容错的算法简要： 括号匹配：当扫描到左括号是，左括号直接入栈，扫描到右括号时，则左括号出栈，如果栈为空，则右括号多，如果最后栈中还有括号，则左括号多。给出错误提示。 除数不为0：当扫描到'/'时，就判断其后面的数字是否为0，如果为0报错。 取余运算：取余运算时，操作数判断是否为整数，不为整数报错。 二、算法流程图 第一种算法:先将表达式转化为后缀表达式，然后计算 其主函数流程图为： 逆波兰表达式求值 一、需求分析 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(); 源代码： //用来存储字符的结点类型 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); #include 汇编语言实训课程设计任务书 题目：表达式求值程序班级：计算机科学与技术一班 学生姓名：赵旭尧学号： 14730141 题目类型：软件工程（R）指导教师：刘树群 一．题目简介 该设计要求学生使用汇编语言，设计并开发出针对四则运算表达式进行求 值的命令行或窗口程序。 通过该题目的设计过程，可以培养学生结构化程序设计的思想，加深对汇 编语言基本语言要素和流程结构的理解，针对汇编语言中的重点和难点内容进 行训练，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格。 得到软件工程的综合训练，提高解决实际问题的能力。 二．设计任务 1、查阅文献资料，一般在5篇以上； 2、通过键盘输入表达式，进行针对整数的“加减乘除”四则运算表达式 进行求值，有良好的界面； 3、完成软件结构设计和算法设计； 4、完成系统的软件开发和测试工作； 5、撰写设计说明书； 6、做好答辩工作。 三．主要内容、功能及技术指标 1、实现功能及指标：①使用Win32的窗口程序模式，实现表达式求值程序 及测试界面程序的设计与开发；②支持整数的四则运算、位运算和小括号等； ③使用文本框对表达式进行交互式编辑和输出。 2、问题分析及解决方案框架确定：充分地分析和理解问题本身，弄清要求 做什么。在确定解决方案框架过程中，综合考虑系统功能，考虑怎样使系统结 构清晰、合理、简单和易于调试。最后确定每个过程和函数的简单功能，以及 过程（或函数）之间的调用关系，并画出函数之间的调用关系图。 3、详细设计和编码：定义相应的存储结构，确定各个函数的算法，并画出 流程图，在此基础上进行代码设计，每个明确的功能模块程序一般不超过200 行，否则要进一步划分。 表达式求值 一目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题 目，利用C/C++语言进行程序设计，并规地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描 述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果 二需求分析 设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果。对于这个程序我们从输入，输出，和功能三方面来分析。 1.程序输入：从键盘上输入表达式，一个算术表达式，由常量、运算符和括号组成（以字符串形式输入，不含变量）。为了简化，操作数只能为浮点数，操作符为“ +”、“-”、“*”、“/”、“（”、“）”，用“#“表示结束。 2.程序输出：表达式运算结果，运算符栈、运算数栈、输入字符和主要操作变化过程，如运算符栈、运算数栈的出入记录，字符出入栈的过程，打印出完整的过程。 3.功能要求及说明：从键盘上输入表达式。分析该表达式是否合法（包含分母不能为零的情况）： （1）是数字，则判断该数字的合法性。 （2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 （3）若是其它字符，则返回错误信息。 若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。 三概要设计 1.数据结构的选择： 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。 实验报告 课程名称： 程序设计与数据结构 指导老师： ljq 成绩： 实验名称：基于二叉树结构的表达式求值算法 实验类型： 上机 同组学生姓名： 一、实验目的和要求（必填） 三、代码缺陷及修正记录 五、讨论、心得 二、实验内容和代码（必填） 四、实验结果与分析（必填） 一、实验目的和要求 1. 掌握编程工具的使用 2. 掌握二叉树数据结构在计算机上的实现 3. 掌握通过计算机编程解决问题的基本方法 二、实验内容和代码 1．实验内容： ● 编程实现基于二叉树结构的表达式求值算法 ● 表达式包含加减乘除四则运算以及至少一层括弧运算 ● 首先将输入的原表达式转换成二叉树结构，然后采用二叉树的后序递归遍历 方法求得表达式的值 ● 将所有实验内容合并到一个工程，增加交互操作和循环处理（持续） 2．代码 1.头文件expnbitree .h 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include 高级语言程序设计 《算术表达式求值》 课程设计报告 算术表达式求值 系统可以实现实现对算术四则混合运算表达式求值，并打印求值过程中运算符栈、操作数栈的变化过程。 第二章系统分析 开始运行时界面如下： 你可以输入一个表达式，按E对其进行求值。 第四章系统实现 #include if(ch=='+'||ch=='-') return 2; if(ch=='*'||ch=='/') return 3; if(ch=='(') return -1; return 0; } double result(double num1,char op,double num2)//计算 { if(op=='+') return num1+num2; if(op=='-') return num1-num2; if(op=='*') return num1*num2; if(op=='/') return num1/num2; return 0; } int compute(char str[]) { double num=0; int i=0,j=1,k=1; numTop=opTop=0; while(str[i]!='\0'||opTop>0) { if(str[i]>='0'&&str[i]<='9') num=num*10+str[i]-'0'; else if( k==1&&str[i]=='-'&&(i==0||op(str[i-1])) ) k=-1; else { if(i>0&&!op(str[i-1])&&str[i]!='('&&str[i-1]!=')') 课程设计报告 题目：计算表达式的值 1.问题描述 对于给定的一个表达式，表达式中可以包括常数、算术运行符（“+”、“-”、“*”、“/”）和括号，编写程序计算表达式的值。 基本要求：从键盘输入一个正确的中缀表达式，将中缀表达式转换为对应的后缀表达式，并计算后缀表达式的值。对于表达式中的简单错误，能够给出提示，并给出错误信息；表达式中可以包括单个字母表示的变量。 测试数据：任意选取一个符合题目要求的表达式。 提高要求：（1）能够处理多种操作符。 （2）实现包含简单运算的计算器。 （3）实现一个包含简单运算和函数运算的计算器。 2.需求分析 （1）软件的基本功能 本软件实在win32工程下实现的带有界面和图标的功能较为齐全的计算器。 此计算器分三个方面进行计算，分别为数值表达式的计算，字母表达式的计算和函数计算。可由键盘或用鼠标点击按键输入带有数字或字母的中缀表达式，程序可以将输入的带有数字或字母的中缀表达式转换成对应的后缀表达式，并计算只含有数字的后缀表达式的值。本软件支持含小数、多位数等多种操作数的处理，可以计算含加、减、乘、除、百分号、求余、求幂，求阶乘，求三角函数的值等多种运算符和函数的表达式 （2）输入/输出形式 用户可通过打开图标弹出来的计算器界面任意点击操作。对于在输入时发生的简单错误，软件通过弹出对话框给出提示并且在提示错误的同时自动将用户的出错输入略去转化成正确的表达式进行计算，用户也可选择清楚操作然后重新输入a.对于数值和函数表达式软件会输出其表达式的后缀表达式和计算结果并保留六位小数； b.对于字母表达式因字母无法进行数值运算，软件仅输出其后缀表达式的值；清楚按钮可以清楚有已经输入或输出的数据从头计算； 软件窗口可实现最小化。并且输入编辑框可进行修改，复制，粘贴等操作，但后缀表达式和求值结果的编辑框中的内容不可修改，只能执行复制操作。 数据结构课程设计 后缀表达式求值 题目：后缀表达式求值 指导老师：高攀 姓名：顾力雄 学院：信息科学与技术学院 专业：计算机科学与技术专业 班级：计科2008级（1）班 学号：2008082258 时间：2009年3月28日 课程设计报告 一、题目：后缀表达式求值； 二、设计目的 1、掌握类模板的应用 2、掌握栈的操作 3、掌握 三、设计内容和要求 运用栈模板在求值过程顺序扫描后缀表达式，每次遇到操作数便将它压入堆栈；遇到运算符，则从栈中弹出两个操作数进行计算，然后再把结果压入堆栈，等到扫描结束时，输出结果，有加减乘除、平方根、sin、cos、tan、arcsin、arcos、arctan、取余、幂运算等等算术。 四、程序结构 后缀表达式 扫描并判断数据类型 运算符则从栈中 取数进行运算数字压入栈中 栈 结果压入栈中输出栈最终结果 五、运行图 参考文献： 刘振鹏编，数据结构（第二版），北京铁道出版社，2007.； 谭浩强编，C++程序设计，北京，清华大学出版社，2004.； 徐晓凯编，数据结构实用教程，第二版，北京，清华大学出版社。 附录：源文件 头文件myStack.h： #ifndef H_StackType #define H_StackType #include 实用标准文档 二课程设计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; } HUNAN UNIVERSITY 课程实习报告 题目：四则运算表达式求值 学生姓名：周华毅 学生学号：201308010411 专业班级：计科1304 指导老师：吴帆 完成日期：2015/5/1 一、需求分析 a)四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达 式，并计算结果。 b)本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结 果来求解后缀表达式的值。 c)在字符界面上输入一个中缀表达式，回车表示结束。如果该中缀表达式正确，那么 在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔 开；如果不正确，在字符界面上输出表达式错误提示。 d)测试数据 输入： 21+23*（12-6） 输出： 21 23 12 6 -*+ 二、概要设计 抽象数据类型 为实现上述程序的功能，应以字符串存储用户的输入，以及计算出的结果。 算法的基本思想 根据题目要求，利用二叉树后序遍历来实现表达式的转换。该算法的基本模块包括二叉树的建立以及如何把输入的中缀表达式利用二叉树后序遍历转化为后缀表达式。 1、首先要将输入的中缀表达式（数字字符）存入到二叉树中，由于存在两位或者两位以上的数，甚至还有小数，所以考虑用字符型指针存储数字字符和操作符。 2、为了便于将中缀表达式存入二叉树中，在录入中缀表达式后，要进行相应的处理，比如去掉空格符，添加结束标志，如‘=’、‘#’等。 3、中缀表达式存入到二叉树的过程中，要注意处理的顺序，如‘+’、‘-’号的优先级比‘*’、‘/’号的低，当遇到‘*’、‘/’号时，要判断树以上的节点中是否有‘+’、‘-’号，有的话要与其交换位置。遇到‘（’时要反复创建二叉树的结点，构建子二叉树，考虑到括号内要处理的步骤可能会较多，可以考虑用递归。遇到‘）’时则直接结束此子二叉树的建立。此外二叉树中叶子结点存储操作数，非叶子结点存储操作码。 4、对创建好的二叉树进行后序遍历，即可得到相应的后缀表达式，实现方法可以用递归的方式，由于后面还要计算表达式的值，故便利的过程中要将结点中得到的数据存入新的字符数组中。 程序的流程 程序由三个模块组成： （1）输入模块：完成一个中缀表达式的输入，存入字符串数组array[Max]中。 （2）计算模块：设计一个建立二叉树的函数，Node* crtTree(Node* root)，传入根结点指针，返回根结点指针，该函数的实现还要反复使用另一个函数char getOp(Node *temp)，其将数字字符存入一个结点，并返回数字字符的后一 个符号。void deal()函数功能是对字符数组进行处理。void output(Node *root); 函数功能是获得处理后的字符串，也就是中缀表达式转化为的后 缀表达式。 （3）输出模块：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和表达式的值；如果不正确，在字符界面上输出表达式错误提示。 三、详细设计数据结构课程设计_表达式求值问题
用栈进行表达式求值并输出逆波兰式(源代码)
(完整版)数学表达式计算(c语言实现)
C语言 后缀表达式计算
逆波兰表达式求值(实验报告及C 源码)
C语言_算术表达式求值_代码
后缀表达式求值的算法及代码
表达式求值程序设计说明书
数据结构课程设计：算术表达式
基于二叉树结构的表达式求值算法
数据结构课程设计算术表达式求值计算器.doc
数据结构计算器(包括中缀转换后缀)课程设计报告
后缀表达式求值_数据结构设计
《大数据结构》算术表达式求值
四则运算表达式求值(栈+二叉树,c++版)
相关主题
文本预览