数据结构实验报告 实验二 中缀表达式转化为后缀表达式算法.doc

昆明理工大学信息工程与自动化学院学生实验报告（ 201 201 学年 第 一 学期 ）课程名称：数据结构 开课实验室： 年 月 日年级、专业、班 学号 姓名 成绩实验项目名称中缀表达式转化为后缀表达式算法及后缀表达式计算算法的实现指导教师 教师评语 教师签名： 年 月 日一.实验内容：中缀表达式转化为后缀表达式算法及后缀表达式计算算法的实现。二.实验目的：结合堆栈入栈出栈的特点解决实际问题。三.主要程序代码分析：typedef struct /创建字符栈 OpNode opNode100;int top; /存放栈顶的数 int size; /存放当前栈的大小 OpStack;void Op_init(OpStack *ops) /对字符栈的初始化 ops-top = 0;ops-size = 0;void Op_push(OpStack *ops,OpNode op) /字符栈的入栈操作 ops-size+;ops-opNode(ops-top)+ = op;OpNode Op_pop(OpStack *ops) /字符栈的出栈操作if(ops-size = 0)/判断栈是否为空，如果为空，则退出程序，否则出栈exit(-1);ops-size-;return ops-opNode-(ops-top);OpNode Op_getTop(OpStack *ops) /看字符栈顶操作int len = ops-size;return ops-opNodelen - 1;while(tempChk != 0) /计算后缀表达式char chars = tempChk;if(chars = 0 & chars = 0 & chars = 9 | chars = .)asschi+ = tempChtempIndex;tempIndex+;chars = tempChtempIndex;td.d = atof(assch);push(&tds,td); /将取出的操作数入栈 k = tempIndex;continue;else if(chars = ) / 如是 则直接跳过 k+;else / 如果是字符，则出栈两个数 进行计算 char op1 = chars;double num_2 = Pop(&tds).d;double num_1 = Pop(&tds).d;double num = Cal(num_1,num_2,op1);td.d = num;push(&tds,td);k+;四.程序运行结果：五.实验总结：通过这次实验，将中缀表达式转化为后缀表达式以及计算后缀表达式的算法，我对栈的运用有了更进一步的认识。在转化的时候，将该字符与运算符栈顶的运算符的优先关系相比较。如果该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。否则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。计算过程则是：从左到右依次进栈遇字母入栈，遇见运算符将前面两个字母弹出，进行运算符运算后，将值再入栈，重复此过程，最终栈里只有