《数据结构课程设计用两种方式实现表达式自动计算》由会员分享，可在线阅读，更多相关《数据结构课程设计用两种方式实现表达式自动计算（17页珍藏版）》请在金锄头文库上搜索。
1、用两种方式实现表达式自动计算一、设计思想（一）中缀转后缀的设计思想设计一个能实现表达式自动求值计算，算术表达式由操作数、算符和括号组成。由于运算符的优先级不同还要考虑括号。所以表达式不可能一直的从左到右进行，所以就借助栈来实现这个表达式的求值。首先要把算术表达式变换成与之等值的无括号表达式，也就是中缀转后缀，它也是这个算法的关键。设计两个栈，一个为字符型的，存放运算符，用以将算术表达式变成无括号的表达式；另一个浮点型的，存放操作数，用以对无符号的表达式进行求值。我们要假设运算符的优先级：( ) , * /, + - 。首先将一左括号(入栈，作为栈底元素；接着从左到右对算术表达式进行扫描。每次读
2、一位，若遇到左括号（，则进栈；若遇到的是操作数，则立即输出；若又遇到运算符，如果它的优先级比栈顶元素的优先级数高的话，则直接进栈，否则输出栈顶元素，直到新的栈顶元素的优先级数比它低的，然后将它压栈；若遇到是右括号），则将栈顶的运算符输出，直到栈顶的元素为（，然后，左右括号互相底消；到设计的结束标志的时候表示表达式已经扫描完毕，表达式已经全部输入，将栈中的运算符全部输出，删除栈底的左括号。以上完成了中缀表达式转后缀表达式，输出无括号的后缀表达式。读后缀表达式，若遇数值，操作数进栈；若遇运算符，让操作数栈的栈顶和次栈顶依次出栈并与此运算符进行运算，运算结果入操作数栈；重复这个步骤，直到遇到结束标志
3、，则此时栈中的结果便是所求的后缀表达式的值，接着输出结果。以上就是设计这个算法的主要的思想。 (二) 直接计算的设计思想直接计算其实跟上一个相似，它是在上面扫两遍的思想进行修改的得来。首先，要建立两个栈，一个为字符型的，存放运算符，另一个浮点型的，存放操作数，我们开始对表达式进行扫描。首先要确定运算符的优先级：（、）、*、/、+、-。如果扫描到的是数字符号，把它们转换成浮点型数据或其他可运算的数据类型，存入操作数栈中。如果扫描到的是运算符号，第一个运算符进栈，遇到（存入运算符栈中，我们按照第一种算法的方法将表达式依次扫描。只不过不同的是，当每取得的一个运算符的时候，都要与栈顶的运算符进行比较，
4、如果它的优先级小于栈顶运算符优先级时，取出栈顶运算符并从操作数栈中取栈顶两个数进行运算，得到的结果则要存回操作数栈，就这样边扫描边比较，再进行计算。遇到“）”对运算符的处理相同。扫描结束后，把运算符栈的元素和操作数栈里的数进行运算。每次的运算结果再放入操作数栈，一直到计算到运算符栈空。最后操作数栈的栈顶留下的操作数即表达式的计算结果。以上就是直接计算表达式的思路。二、算法流程图（一）中缀转后缀算法的流程图图1中缀转后缀算法的流程图流程图说明：该流程图分两部分成，第一部分是中缀转后缀部分，第二部分是用于后缀表达式求值的。（二）直接计算算法的流程图图2接计算算法的流程图流程图说明：该流程图进过图1
5、 改进得到，只是缺少中缀转后缀的部分。三、源代码下面给出的是用中缀转后缀算法实现的程序的源代码：#include #define N 50typedef struct StackArray float dataN; int top;StackArray; /*定义操作数栈*/typedef struct StackChar char dataN; int top;StackChar; /*定义操作符栈*/ StackArray *InitNum() /*初始化数值栈*/ StackArray *p = (StackArray *)malloc(sizeof(StackArray); /*取一段
6、内存赋予数值栈*/ p-top=-1; return p; /*返回*/StackChar *InitChar() /*初始化操作符栈*/ StackChar *p=(StackChar *)malloc(sizeof(StackChar); /*取一段内存赋予数值栈*/ p-top=-1; return p;int PushNum(StackArray *p,float value) /*定义入栈函数*/ if(p-toptop+=1; p-datap-top=value; /*栈顶*/ return 1; else return 0; int PushChar(StackChar *p,c
7、har value) /*操作符入栈*/ if(p-toptop+=1; p-datap-top=value; /*入栈为栈顶*/ return 1; else return 0; /*返回值*/ int PopNum(StackArray *p,float *value) /*操作数出栈*/ if(p-top=0) /*判断栈是否为空*/ *value=p-datap-top; p-top-=1; return 1;int PopChar(StackChar *p,char *q) /*操作符出栈函数*/if(p-top=0) /*定义操作符栈*/ *q=p-datap-top; p-top
8、-=1; return 1;float VisitNum(StackArray *p) /*定义数值栈遍历函数*/ if(p-top!=-1) return p-datap-top; else return 0;char visitChar(StackChar *p) /*定义操作符栈遍历函数*/ if(p-top!=-1) return p-datap-top; else return 0;int level(char c) /*优先级*/ switch(c) case #: return 0; /*#的优先级*/ case +:return 1; case -:return 1; /* -
9、的优先级*/ case *:return 2; case /:return 2; case (:return 3; /*（优先级*/ default : return -1; int strLen(char *L) /*字符串长度函数*/ int i; for(i=0;Li!=0;i+); /*循环条件*/ if(L0=-|L0=+) i=i-1; return i;float Compute(float a,char c,float b) /*计算*/ switch(c) case +:return a+b; /*加号的运算*/ case -:return a-b; case *:retur
10、n a*b; /*乘号的运算*/ case /:return a/b; /*除号的运算*/ default : return -1; void main() StackArray *data; StackChar *op; int i,j=0; float n; float result,opA,opB; char opChar; char arrayN; char *ptarray=NULL; /*定义指针*/ float houzhuiN; printf(Please enter a data:t); while(scanf(%s,array)!=EOF) /*循环条件*/ op=InitChar(); data=InitNum(); PushChar(op,#); arraystrLen(array)=#; /*结束标志*/ ptarray=array; for(i=0;i=48&arrayi=48&arrayi+1=57|arrayi+1=.) /*判定数值*/ if(arrayi+1=.) /*小数*/ flag=1; else if(flag=0)n=n*10+arrayi+1-48; /*整数化浮点数*/ else
