线性表及其应用-中缀转后缀并计算其值

1、哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法 课程类型：必修实验项目名称：线性表及其应用 实验题目：算术表达式求值班级：学号：姓名： 设计成绩报告成绩指导老师一、 实验目的1. 掌握栈的数据结构与基本操作2. 了解什么是中缀表达式和后缀表达3. 了解并掌握中缀表达式转为后缀表达式的方法4. 掌握使用栈结构求解后缀表达式的求值方法5. 提高利用计算机分析和解决复杂实际问题的能力二、 实验要求及实验环境1. 试验要求：(1)从键盘输入任意一个语法正确的（中缀）表达式，显示并保存该表达式。(2)利用栈结构，把上述（中缀）表达式转换成后缀表达式，并显示栈的状态变化过程和所得到的后

2、缀表达式。(3)利用栈结构，对上述后缀表达式进行求值，并显示栈的状态变化过程和最终结果。2.试验环境： Windows 7操作系统 Devc C+ 编译器三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）程序中用到的数据类型的定义：char string1100; /存放表达式struct Stack /定义一个栈 char datamaxlength; int top; ;typedef struct Stack stack1;stack1 output1; /存放操作符stack output1; /存放后缀表达式的数字的栈 主程序流程图：开始输入

3、一个以字符串形式定义的运算式并保存至数组string1100中,声明一个运算符栈用来存放运算符指针遍历字符串数组弹出栈内所有元素存入结尾数组直接压入栈中弹出栈内与之匹配的（前的所有运算符并存结尾数组中直接压入栈中并在结尾数组中存入空格高直接存入结尾数组中与栈顶运算符比较低存入空格为）为数字为（为运算符判断字符串数组每一个单元的内容存入空格将栈内元素全部存至结尾数组中 申请一个新的整型栈用于后缀表达式计算遍历结尾数组中的每一个元素将字符型转换为整型存入一个数字数组中去将空格之前到前一个空格之间的所有存入数字数组中的数字进行位数计算得到一个新的数字压入栈中弹出整型栈中的两个元素进行相应的加减乘除运

4、算，并将运算结果重新压入栈中为“ ”为数字为运算符判断每一个元素的内容将后缀字符串和计算得到的结构输出结束各程序模块之间的调用关系：int main() char qianzhui100; cout 请输入一个语法正确的（中缀）表达式(在此过程不用输入等号)： ; gets(qianzhui); cout 该中缀表达式为：; cout qianzhui endl; change(qianzhui); cout 转换为后缀表达式为：; cout string2 endl; jisuan(string2); return 0;四、测试结果. 请输入一个语法正确的（中缀）表达式(在此过程不用输入等号

5、)：12.3*(12.34+23.54)-23.4/23.45该中缀表达式为：12.3*(12.34+23.54)-23.4/23.45进栈元素为：*进栈元素为：+出栈元素为：+出栈元素为：(出栈元素为：*进栈元素为：-进栈元素为：/出栈元素为：/出栈元素为：-转换为后缀表达式为：12.3 12.34 23.54 +*23.4 23.45 /-将12.3进栈将12.34进栈将23.54进栈将23.54进栈将23.54出栈将12.34出栈将35.88进栈将35.88进栈将35.88出栈将12.3出栈将441.324进栈将23.4进栈将23.45进栈将23.45进栈将23.45出栈将23.4出栈将

6、23.45进栈将23.45进栈将0.出栈将441.324出栈将440.326进栈将0.进栈将440.326出栈后缀表达式的值为：440.326五、系统不足与经验体会系统不足：无法处理负数，当输入不正确的表达式时程序会异常终止，没有找到解决的办法。体会：编程过程中遇到问题应该多问问同学，上网查资料，不应该自己死扣，还应该多于同学分享一下自己的编程思想，多吸取一下别的同学的编程思想。由于没有对问题进行深层次的分析思考，编的程序功能实现不完整，存在bug，但是主要功能都能实现。六、附录：源代码（带注释）#include #include#include#include#includechar str

7、ing1100; char string2100;const int maxlength = 100;using namespace std;struct Stack /定义一个栈 char datamaxlength; int top; ;typedef struct Stack stack1;void Push(int x,stack1 &S) /把x压栈S的栈顶 if(S.top=0) cout 栈已满！maxlength-1) return true; else return false;char Top(stack1 &S) /返回栈S的栈顶元素 int a; if(Empty(S)

8、 cout 栈是空的！ endl; else a=S.top; S.top=S.top+1; return S.dataa; void Pop(stack1 &s) /删除栈S的栈顶元素 if(Empty(s) cout 栈是空的！ endl; else s.top=s.top+1; bool prir(char a,stack1 &S) /判断操作符优先级 if(Empty(S) return true; else char b = S.dataS.top; switch(a) case -: case +: switch(b) case -: case +: case *: case /:

9、 return false;break; case (: return true; break ; break; case *: case /: switch(b) case -: case +: case (: return true; break ; case *: case /: return false;break; break; void change(char L) /中缀表达式转后缀表达式 int j=0; /存放后缀表达式 stack1 output1; /存放操作符 MakeNull(output1); int number = strlen(L); for(int i=0;

10、i=48 & Li=57| Li=.) /如果是数字，直接保存 string1j=Li; j+; else /不是数字 switch( Li) case + : case - : case * : case / : string1j= ; j+; if(prir(Li,output1) /比栈顶优先级高,直接进栈 Push(Li,output1); cout 进栈元素为： Li endl; else if(output1.dataoutput1.top!=() /比栈顶优先级低，先出栈,Li进栈 string1j=Top(output1); cout 出栈元素为： string1j endl;

11、 j+; Push(Li,output1); cout 进栈元素为： Li endl; break; case ( : /直接进栈 Push(Li,output1); break; case ) : /匹配栈内的(, 并删除( string1j= ; j+; do char a = Top(output1); cout 出栈元素为： a endl; if(a!=() string1j = a; j+; else break; while(1); break; string1j= ; j+; while(!Empty(output1) string1j = Top(output1); cout

12、出栈元素为： string1j =0&*li=9)|*li=.) *ni+=*li+; else *ni+=*li+; if(*li= ) *li+; void jisuan(char L) char n100; int j=0; double m ,k,b; stack output1; /存放后缀表达式的数字 int number = strlen(string1); for(int i=0;i=48 & Li=57|Li=.) /如果是数字，直接保存 nj=Li; j+ ; else if(Li= ) m = atof(n); output1.push(m); memset(n, ,j)

13、; j=0; cout 将 m 进栈 endl; else /不是数字 cout 将 m 进栈 endl; switch( Li) case + : m=output1.top(); output1.pop(); cout 将 m 出栈 endl; k=output1.top(); output1.pop(); cout 将 k 出栈 endl; m+=k; output1.push(m); cout 将 m 进栈 endl; break; case - : b=0; m=output1.top(); output1.pop(); cout 将 m 出栈 endl; k=output1.top

14、(); output1.pop(); cout 将 k 出栈 endl; b=k-m; output1.push(b); cout 将 b 进栈 endl; break; case * : m=output1.top(); output1.pop(); cout 将 m 出栈 endl; k=output1.top(); output1.pop(); cout 将 k 出栈 endl; m*=k; output1.push(m); cout 将 m 进栈 endl; break; case / : b=0; m=output1.top(); output1.pop(); cout 将 m 出栈 endl; k=output1.top(); output1.pop(); cout 将 k 出栈 endl; b=k/m ; output1.push(b); cout 将 m 进栈 endl; break; m=output1.top(); cout 将 m 出栈