表达式求值算法
一、设计思想
1.中缀表达式转换为前缀表达式。
首先创建算术符栈OPTR和表达式栈RESULT并置空，然后依次逆序检查中缀表达式每个字符，不同字符按不同情况处理：
(1).若是空格直接跳过。
(2).若是操作数直接压入RESULT栈。
(3).若是‘）’直接存入OPTR栈，等待和它匹配的‘（’出现。
(4).若是‘（’表明括号中的终追表达式已转换完毕，则循环弹出OPTR栈的操作符，
并压入RESULT栈，直到取出一个和它匹配的‘）’为止，‘）’出栈丢弃。
(5).若是运算符，如果OPTR栈是空的或者该运算符优先级高于或等于OPTR栈的栈顶运算符则入栈，如果该运算符优先级低，则循环弹出OPTR栈的运算符并存入RESULT，直到遇到栈顶的运算符优先级等于或小于该算法或栈空为止，然后将当前操作符存入OPTR栈。
若表达式扫描完后OPTR栈还有运算符，则依次弹出压入RESULT栈，直至栈空。最后RESULT栈中的元素依次出栈存入字符串中，并向字符串中写入‘\0’，则字符串中存放的就是前缀表达式。
2.前缀表达式求值。
首先建立一个栈并置空，然后从右到左扫描前缀表达式，从右边第一个字符开始判断，如果当前字符是数字则一直到数字串的末尾再将整个数字串作为一个整体压人栈，如果是运算符，则将栈顶和次栈顶的两个“数字串”出栈并作相应的运算，然后将计算结果入栈。扫描完前缀式后，栈中剩余的最后一个值就是前缀表达式的值。
3.中缀表达式转换成后缀表达式。
首先创建栈并置空，然后依次检查中缀表达式每个字符，不同字符按不同情况处理：
(1).若是操作数，就直接将存入字符串exp[]中。
(2).若是‘（’则将其压入栈中。
(3).若是‘）’则依次弹栈并存入字符串exp[]中，直到遇到取出和它匹配的‘（’为止，‘（’出栈丢弃。
(4).若是操作符，如果栈空或者该操作符的优先级大于栈顶操作符则将其放入到栈中。如果该操作符的优先级小于等于栈顶操作符则弹出栈中的操作符存入字符串exp[]中，直到该操作符的优先级大于栈顶操作符或栈空，然后将该操作符入栈。
当读到了中缀式的末尾时，如果栈非空则将栈中所有元素依次弹出存入字符串exp[]中，最后见‘\0’存入exp[]中，则exp[]中存储的就是后缀表达式。
4.后缀表达式求值。
首先建立一个栈并置空，然后依次左扫描后缀表达式，从第一个字符开始判断，如果当前字符是数字则一直到数字串的末尾再将整个数字串作为一个整体压人栈，如果是运算符，则将栈顶和次栈顶的两个“数字串”出栈并作相应的运算，然后将计算结果入栈。扫描完前缀式后，栈中剩余的最后一个值就是前缀表达式的值。
二、算法流程图
图1中缀式转前缀式流
程图
图2前缀式求值流程图
流程图
图4后缀式求值流程图
三、源代码
下面给出的是算法实现的程序的源代码：
#include
#include
#include
#include
#define MaxSize 50
typedef struct
{
float data[MaxSize];
int top;
}OpStack;
typedef struct
{
char data[MaxSize];
int top;
}SeqStack;
void InitStack(SeqStack *S);//初始化栈
int StackEmpty(SeqStack S);//判断栈是否为空
int PushStack(SeqStack *S,char e);//进栈
int PopStack(SeqStack *S,char *e);//删除栈顶元素
int GetTop(SeqStack S,char *e);//取栈顶元素
void PrefixExpress(char str[],char exp[]);//将中缀表达式转化为前缀表达式float ComputePExpress(char a[]);//计算前缀式的值
void SuffixExpress(char str[],char exp[]);//将中缀表达式转化为后缀表达式float ComputeSExpress(char s[]);//计算后缀表达式的值
int pre(char c);//判断逆输入时的优先级
int pre_1(char c);//判断优先级
void main()
{
char a[MaxSize],b[MaxSize],c[MaxSize];
float f,g;
printf("请输入一个合法的算术表达式:\n");
gets(a);
printf("中缀表达式为：%s\n",a);
PrefixExpress(a,c);
printf("前缀表达式为：%s\n",c);
g=ComputePExpress(c);
printf("计算结果：%f\n",g);
SuffixExpress(a,b);
printf("后缀表达式为：%s\n",b);
f=ComputeSExpress(b);
printf("计算结果：%f\n",f);
}
void InitStack(SeqStack *S)//初始化栈
{
S->top=0;
}
int StackEmpty(SeqStack S)//判断栈是否为空{
if(S.top ==0)
return 1;
else
return 0;
}
int PushStack(SeqStack *S,char e)//进栈
{
if(S->top>=MaxSize)
{
printf("栈已满，不能进栈!");
return 0;
}
else
{
S->data[S->top]=e;
S->top++;
return 1;
}
}
int PopStack(SeqStack *S,char *e)//删除栈顶元素{
if(S->top==0)
{
printf("栈已空\n");
return 0;
}
else
{
S->top--;
*e=S->data[S->top];
return 1;
}
}
int GetTop(SeqStack S,char *e)//取栈顶元素{
if(S.top<=0)
{
printf("栈已空");
return 0;
}
else
{
*e=S.data[S.top-1];
return 1;
}
}
int pre(char c)//判断优先级
{
int i;
switch(c)
{
case'(':i=3;break;
case'+':i=1;break;
case'-':i=1;break;
case'*':i=2;break;
case'/':i=2;break;
case')':i=0;break;
}
return i;
}
int pre_1(char c)//判断优先级
{
int i;
switch(c)
{
case'(':i=0;break;
case'+':i=1;break;
case'-':i=1;break;
case'*':i=2;break;
case'/':i=2;break;
case')':i=3;break;
}
return i;
}
void PrefixExpress(char str[],char exp[])//把中缀表达式转换为前缀表达式{
SeqStack OPTR;
SeqStack RESULT;
int i,j=0;
char ch;
char e;
i=strlen(str)-1;
ch=str[i];
InitStack(&OPTR);
InitStack(&RESULT);
while(i>=0)//依次逆扫描中缀式
{
switch(ch)
{
case' ':
break;
case'\t':
break;
case')':
PushStack(&OPTR,ch);
break;
case'(':
PopStack(&OPTR,&e);
while(e!=')')
{
PushStack(&RESULT,e);
PopStack(&OPTR,&e);
}
break;
case'+':
case'-':
case'*':
case'/':
if (StackEmpty(OPTR))
PushStack(&OPTR,ch);
else
{
GetTop(OPTR,&e);
if(pre(ch)>=pre(e))
PushStack(&OPTR,ch);
else
{
while(pre(ch) { PopStack(&OPTR,&e); PushStack(&RESULT,e); } PushStack(&OPTR,ch); } } break; default: while(ch>='0'&&ch<='9') { PushStack(&RESULT,ch); --i; ch=str[i]; } PushStack(&RESULT,' '); ++i; } --i; ch=str[i]; } while(!StackEmpty(OPTR ))//将栈中剩余运算符出栈 { PopStack(&OPTR,&e); PushStack(&RESULT,e); } while(!StackEmpty(RESULT))//依次出栈 { PopStack(&RESULT,&e); exp[j] = e; ++j; } exp[j]='\0'; } float ComputePExpress(char a[])//计算前缀式的值{ OpStack S; SeqStack A; int i; char e; float x1,x2,value; float result; i=strlen(a)-1; S.top=-1; InitStack(&A); while(i>=0) { if(a[i]!=' '&&a[i]>='0'&&a[i]<='9') { while(a[i]!=' ') { PushStack(&A,a[i]); i--; } value=0; while(!StackEmpty(A)) { PopStack(&A,&e); value=value*10+e-'0'; } S.top++; S.data[S.top] = value; } else { switch(a[i]) { case'+': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x1+x2; S.top++; S.data[S.top]=result; break; case'-': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x1-x2; S.top++; S.data[S.top]=result; break; case'*': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x1*x2; S.top++; S.data[S.top]=result; break; case'/': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x1/x2; S.top++; S.data[S.top]=result; break; } i--; } } if(S.top!=-1) //如果栈不空，将结果出栈并返回{ result=S.data[S.top]; S.top--; if(S.top==-1) return result; else { printf("表达式错误"); exit(-1); } } return 0; } void SuffixExpress(char str[],char exp[])//把中缀表达式转换为后缀表达式{ SeqStack S; char ch; char e; int i=0,j=0; InitStack(&S); ch=str[i]; while(ch!='\0') //依次扫描中缀表达式 { switch(ch) { case'(': PushStack(&S,ch); break; case')': PopStack(&S,&e); while(e!='(') { exp[j]=e; ++j; PopStack(&S,&e); } break; case'+': case'-': case'*': case'/': if(StackEmpty(S)) PushStack(&S,ch); else { GetTop(S,&e); if(pre_1(ch)>pre_1(e)) PushStack(&S,ch); else { while(pre_1(ch)<=pre_1(e)&&!StackEmpty(S)) { PopStack(&S,&e); exp[j]=e; ++j; } PushStack(&S,ch); } } break; case' ': break; default: while(ch>='0'&&ch<='9') { exp[j]=ch; j++; ++i; ch=str[i]; } i--; exp[j]=' '; j++; } i++; ch=str[i]; } while(!StackEmpty(S)) //将栈中剩余运算符出栈{ PopStack(&S,&e); exp[j]=e; j++; } exp[j]='\0'; } float ComputeSExpress(char a[])//计算后缀表达式的值{ OpStack S; int i=0; float x1,x2,value; float result; S.top=-1; while(a[i]!='\0') //依次扫描后缀表达式 { if(a[i]!=' '&&a[i]>='0'&&a[i]<='9')//如果是数字{ value=0; while(a[i]!=' ') //如果不是空格 { value=10*value+a[i]-'0'; i++; } S.top++; S.data[S.top]=value; //处理后进栈 } else//如果是运算符 { switch(a[i]) { case'+': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x1+x2; S.top++; S.data[S.top]=result; break; case'-': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x2-x1; S.top++; S.data[S.top]=result; break; case'*': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x1*x2; S.top++; S.data[S.top]=result; break; case'/': x1=S.data[S.top]; S.top--; x2=S.data[S.top]; S.top--; result=x2/x1; S.top++; S.data[S.top]=result; break; } i++; } } if(S.top!=-1) //如果栈不空，将结果出栈并返回{ result=S.data[S.top]; S.top--; if(S.top==-1) return result; else { printf("表达式错误"); exit(-1); } } return 0; } 四、运行结果 图5 程序运行结果图 五、遇到的问题及解决 这部分我主要遇到了如下三个问题，其内容与解决方法如下所列： ●问题1描述 打印前缀表达式和后缀表达容易使不同乘数混淆不易于阅读。 问题1解决方法： 在不同数字串之间加一个空格以此来区分不同的乘数，使人能够区分不同的乘数。 ●问题2描述 无法解决多位数的计算。 问题2解决方法： 使用数字串内循环，把一个完整数字串作为一个整体存入栈中。 ●问题3描述 程序运行时前缀式数据丢失。 问题3解决方法： 检查程序发现是在中缀式转化为前缀式时重复弹栈。 六、心得体会 写程序十分的注重细节，往往一个小细节就能使结果改变。因此在写程序时必须十分的细心。另一方面在写程序时，最好能够有良好的命名习惯，最好做到见名知意。这样有利于对程序的阅读。混乱的命名会使得程序的可读性降低，同时在写程序时不利于使用。 一个好的程序不能够太片面要考虑到各种问题，就拿我这程序来说，就只考虑到正整数的四则运算，没有考虑到负数和小数的运算、平方运算等。使得程序的功能有很大的局限性，实用性不大。 写程序的过程就是不断在发现问题和解决问题的过程，没有完美的程序只有不断完美的程序，这是在写表达式求值这个程序时的体会。 湖南人文科技学院计算机科学技术系 课程设计说明书 课程名称:数据结构 课程代码: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. 竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告 篇一：数据结构实验二——算术表达式求值实验报告 《数据结构与数据库》 实验报告 实验题目算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系pb0920603 姓学 邮名：李维谷号：pb09206285箱： liwg@https://www.wendangku.net/doc/6511075609.html,指导教师：贾伯琪 实验时间：20XX年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个(:数据结构表达式求值实验报告)算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 《数据结构与数据库》 实验报告 实验题目 算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系PB0920603 姓名：李维谷 学号：PB09206285 邮箱：liwg@https://www.wendangku.net/doc/6511075609.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<<"栈创建失败，退出!"< 数理学院 课程设计报告书 课程名称数据结构课程设计 设计题目算术表达式求值演示 专业班级 学号 姓名 指导教师 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; #include 软件技术基础实验报告 实验名称：表达式计算器 系别：通信工程 年级： 班级： 学生学号： 学生姓名： 《数据结构》课程设计报告 题目简易计算表达式的演示 【题目要求】 要求：实现基本表达式计算的功能 输入：数学表达式，表达式由整数和“+”、“-”、“×”、“/”、“（”、“）”组成输出：表达式的值 基本操作：键入表达式，开始计算，计算过程和结果记录在文档中 难点：括号的处理、乘除的优先级高于加减 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} 课程设计 教学院 课程名称 题目 专业 班级 姓名 同组人员 指导教师 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)，把一 个数字串转换为一个实型数，并压入运算数栈中。（整个程序的源代码 见附录，并有具体解释） 表达式求值课程设计报告 表达式求值 《数据结构》 课程设计报告 题目: 栈的应用:表达式求值 (系): 信息科学与工程学院院 专业班级: 软件工程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(培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提 高程序设计水平。 实验报告 课程名称： 程序设计与数据结构 指导老师： 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 源代码： //用来存储字符的结点类型 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); 高级语言程序设计 《算术表达式求值》 课程设计报告 算术表达式求值 系统可以实现实现对算术四则混合运算表达式求值，并打印求值过程中运算符栈、操作数栈的变化过程。 第二章系统分析 开始运行时界面如下： 你可以输入一个表达式，按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]!=')') 一、设计思想 一．中缀式计算结果的设计思想： 此种算法最主要是用了两个栈：用两个栈来实现算符优先，一个栈用来保存需要计算的数据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），这是在设计思想上错误提示的很重要一点，否则计算不全面！ 二、算法流程图 第一个图是直接计算的流程图，图中反应除了这种方法的大致设计思路，但是有些细节没有反映出来，比如说，怎样把字符型数据转换为浮点型数据，就没有反映出来。特别说明 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）输出模块：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和表达式的值；如果不正确，在字符界面上输出表达式错误提示。 三、详细设计 数据结构课程设计 设计说明书表达式求值算法的实现（（（）（）（（ 学生姓名 学号 班级 成绩 指导教师 数学与计算机科学学院 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）编写课程设计报告； 指导教师（签字）：教研室主任（签字）： 批准日期：年月日 数据结构课程设计报告 课设题目：算式表达式求值系统 班级: 软件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; } 程序设计实训报告— 表达式求值问题 完成者：何炜 班级：计科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.对后缀表达式进行求值表达式求值算法实现
数据结构表达式求值实验报告
数据结构实验二——算术表达式求值实验报告
数据结构课程设计_表达式求值问题
算术表达式求值演示程序
后缀表达式求值的算法及代码
数据结构算术表达式求值实验报告
算术表达式求值课程设计报告
表达式求值课程设计报告
基于二叉树结构的表达式求值算法
C语言_算术表达式求值_代码
数据结构课程设计算术表达式求值计算器.doc
用两种方法实现表达式求值
四则运算表达式求值(栈+二叉树,c++版)
算术表达式求值课设报告
算术表达式求值系统
《大数据结构》算术表达式求值
程序设计实训报告—表达式求值问题
- 数据结构课程设计_表达式求值【完整版】
- 数据结构课程设计_表达式求值问题
- (完整版)数据结构与算法表达式求值报告
- 数据结构实验二——算术表达式求值实验报告
- 表达式求值实验报告
- 四则运算表达式求值
- 数据结构课程设计-表达式求值问题
- 表达式求值问题++数据结构
- C语言表达式求值
- 表达式求值问题
- 表达式求值课程设计报告
- 四则运算表达式求值(栈+二叉树,c++版)
- 表达式求值
- 表达式求值课程设计报告
- 算术表达式求值问题课程设计报告
- 用两种方法实现表达式求值
- 数据结构课程设计_实验报告(一)表达式求值(计算器)
- 数据结构C语言表达式求值(带详细注释)
- C语言表达式求值(带详细注释)
- 数据结构实验二——算术表达式求值实验报告