数据结构二叉树遍历和表达式求值.doc-资料库

zjlightman-6834589-4744300845192467126.doc.pdf-第1页.png

第1页 / 共19页

zjlightman-6834589-4744300845192467126.doc.pdf-第2页.png

第2页 / 共19页

zjlightman-6834589-4744300845192467126.doc.pdf-第3页.png

第3页 / 共19页

zjlightman-6834589-4744300845192467126.doc.pdf-第4页.png

第4页 / 共19页

zjlightman-6834589-4744300845192467126.doc.pdf-第5页.png

第5页 / 共19页

zjlightman-6834589-4744300845192467126.doc.pdf-第6页.png

第6页 / 共19页

zjlightman-6834589-4744300845192467126.doc.pdf-第7页.png

第7页 / 共19页

zjlightman-6834589-4744300845192467126.doc.pdf-第8页.png

第8页 / 共19页

用两种方式实现表达式自动计算数据结构（双语） ——项目文档报告用两种方式实现表达式自动计算专班业：计算机科学与技术级：指导教师：姓学名：号： - 1 -

用两种方式实现表达式自动计算目录一、设计思想……………………………………………………….03 二、算法流程图…………………………………………………….04 三、源代码………………………………………………………….06 四、运行结果……………………………………………………….18 五、遇到的问题及解决…………………………………………….18 六、心得体会……………………………………………………….19 - 2 -

用两种方式实现表达式自动计算一、设计思想本报告用两种算法分别对表达式进行计算：一：将用户所输入的中缀表达式先变换成后缀表达式，然后在对后缀表达式进行计算。二：将用户所输入的中缀表达式直接进行计算。第一种算法：这种算法又可分为两步：第一步：将用户输入的中缀表达式先转换成后缀表达式：在这一步中，首先要建立一个符号栈，和一个字符串数组，接着读用户输入的字符，如果用户输入的是数字、+、—、*、/、%、（、）以外的字符，则程序报错。如果读到的是数字或小数点，则直接放入字符串数组。如果读到的是符号，则与符号栈栈顶的元素的优先级进行比较，如果当前读入的符号的优先级高，则直接入栈，如果当前符号的优先级低于栈顶元素的优先级，那么将栈顶元素弹出，并将其放入字符串数组中，如果读到的是左括号，则直接入栈，并将当前符号与栈中栈顶的下一个元素进行对比。如果读到的是右括号，则观察栈顶元素，如果栈顶不为左括号或空，则将符号存入字符串数组中，如果遇到左括号，则弹出左括号，如果栈为空，则结束。如此循环，直到遇到’\0’结束，最终字符串数组中的表达式为后缀表达式。第二步：对后缀表达式进行计算：在这一步中，首先要建立一个数值栈，对字符串数组中的字符进行读取，当读取到数值时，将数值放入数值栈中，如果读到符号，则将弹出栈中的两个数字进行计算，在将计算结果放入数值栈中，最后栈中留下的结构就是表达式最后的结果。第二种算法：在此算法中要定义两个栈，一个叫数值栈，一个叫符号栈，将用户输入的字符逐个进行扫描，如果用户输入的是数字、+、—、*、/、%、（、）以外的字符，则程序报错。如果是数字或小数点，则放入数值栈中，如果是符号，则先将此符号的优先级与符号栈的栈顶元素的优先级做比较，如果当前读到的符号的优先级比符号栈栈顶元素的优先级高，则此符号入栈。如果此符号优先级低，则将栈顶元素出栈，然后从数值栈中弹出两个元素，将这两个元素进行计算，计算结果继续压入到数值栈中，而将当前读到的符号继续与符号栈中的下一个栈顶元素比较，如此循环，直到符号栈中栈顶元素的优先级小于或等于当前符号的优先级，则将当前符号压入符号栈中，如果读到的是左括号，则直接放入符号栈中，如果读到的是右括号，则从符号栈中弹出一个符号，从数值栈中弹出两个数字，然后将计算结果放入数值栈中，如此循环操作，如果遇到左括号，则停止，并释放左括号。接着读取下一个字符，读取结束时，计算结果就放在数值栈中，从而将数值栈中的元素弹出即为所求结果。 - 3 -

存在错误并结束程序二、算法流程图第一个算法的流程图：主函数的流程图：返回计算结果用两种方式实现表达式自动计算用户输入的中缀表达式判断表达式中是否含有除数字、 +、—、*、/、%、（、）以外的字符调用函数将中缀表达式转换成后缀表达式调用函数通过后缀表达式计算出结果图 1 主函数流程图中缀转化为后缀的流程图：如果是数字或小数点读取用户输入的字符并判断如果是除括号以外的操作符优先级高于栈顶与栈顶元素比较入栈优先级低于栈顶栈顶元素出栈存入数组将其放入字符数组中，并在后面加上分隔符如果是括号判断括号类型如果是左括如果是右括号号直接入栈放入数组中从栈中取出操作符 - 4 -

用两种方式实现表达式自动计算取出的不是左括号图 2 中缀转化为后缀流程图后缀表达式计算的流程图后缀表达式如果是数字判断符号类型如果是操作符转化为浮点数入栈从数值栈中取出两个数计算并将结果放入栈中第二种算法的流程图主函数的流程图：返回计算结果返回最终数值栈中的结果图 3 后缀表达式计算流程图用户输入的中缀表达式判断表达式中是否含有除数字、 +、—、*、/、%、（、）以外的字符调用直接计算的函数图 4 主函数流程图 - 5 - 存在错误并结束程序

用两种方式实现表达式自动计算直接计算函数的流程图：得到中缀表达式数字从字符串中读取一个字符并判断类型转化为浮点数入数值栈左括号直接入栈括号判断括号类型右括号从栈中取出操作符操作符高于栈顶直接入栈与符号栈的栈顶元素做比较低于栈顶从相应栈中分别取出一个操作符和两个操作数进行计算，并将结果放入栈中，并再次看栈顶元素从数值栈中取出两个数，并是释放左括号判断是否为左括号不是栈空符号栈是否为空非空取出数栈的两个数和符号栈的一个操作符进行计算，并将结果放入数值栈将数值栈顶图 4 直接计算流程图三、源代码下面给出的是用中缀转后缀计算算法实现的程序的源代码： #include #include #include #include /*导入需要用到的各种包*/ typedef struct { char op; int level; }OpNode; /*定义结构体用来存储操作符*/ /*存储字符*/ /*存储优先级*/ - 6 -

typedef struct { OpNode op[100]; int top; int size; } stack; void init(stack *st) { st->size=0; st->top=0; } OpNode pop(stack *a) { if (a->size==0) { exit(-1); } a->size--; return a->op[--(a->top)]; } void push(stack *a,OpNode op) { a->size++; a->op[(a->top)++]=op; } OpNode top(stack *a) { if (a->size==0) { printf("stack is empty\n"); exit(-1); } return a->op[(a->top)-1]; } typedef struct { double num[100]; int top; int size; } numstack; void init2(numstack *st) { 用两种方式实现表达式自动计算 /*表示栈内元素的个数*/ /*定义符号栈*/ /*初始化栈*/ /*出栈 */ /*如果栈为空结束操作*/ /*取出栈顶元素*/ /*入栈函数*/ /*观察栈顶函数*/ /*如果栈为空结束操作*/ /*只得到栈顶的值而不出栈*/ /*定义数值栈*/ /*栈顶指针*/ /*初始化数值栈*/ - 7 -

用两种方式实现表达式自动计算 st->size=0; st->top=0; } double pop2(numstack *a) { if (a->size==0) { exit(-1); } a->size--; return a->num[--(a->top)]; } void push2(numstack *a,double num) { a->size++; a->num[(a->top)++]=num; } void main() { /*数值栈出栈*/ /*出栈前的判空*/ /*得到栈顶的值*/ /*入栈*/ /*主函数*/ void change (char str[],char exp[]); double CalResult(char exp[]); /*声明要用到的各个函数*/ /*声明后缀表达式的计算函数*/ char str[100],exp[100]; printf("算术表达式为:\n"); /*str 存储原算术表达式， exp 存储对应的后缀表达式,chestr 存储容错字符'^'*/ printf("算术表达式为:\n"); gets(str); change(str,exp); printf("后缀表达式为:%s\n",exp); printf("运算结果为： %f\n",CalResult(exp)); int a; scanf(&a); /*调用函数将中缀转化为后缀*/ /*调用函数计算后缀表达式*/ } void change (char str[],char ch[]) { int i=0; int k=0; char c; stack st; OpNode op; OpNode ops; init(&st); c=str[i++]; /*将前缀表达式转化为后缀表达式*/ /*str 的索引*/ /*字符串中取出的放在 C 中*/ /*定义符号栈*/ /*初始化符号栈*/ - 8 -

资料库

数据结构二叉树遍历和表达式求值.doc

相关推荐

课程资源

热门标签

最新资料