中缀表达式求值实验报告

HUNANUNIVERSITY课程实习报告题目：四则运算表达式求值学生姓名：学生学号：专业班级：指导老师：完成日期：一、需求分析四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达式，并计算结果。

本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。

在字符界面上输入一个中缀表达式，回车表示结束。

如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。

测试数据输入：21+23G（12-6）输出：2123126-G+二、详细设计输入和输出的格式输入本程序可以将输入的四则运算表达式（中缀表达式）转换为后缀表达式输出后缀表达式为：//输出结果的位置表达式的值为：//输出结果的位置三、调试分析本次实验的难点主要是在建立二叉树的问题上。

关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法，成功实现了目标，但是却遇到了一个问题，那就是不能处理小数，甚至两位或两位以上的整数。

因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改进采用字符串数组来存储操作数，成功解决了问题。

另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。

四、测试结果五、用户使用说明（可选）1、运行程序时提示输入四则运算表达式本程序可以将中缀表达式转化为后缀表达式，并计算结果请输入四则运算表达式：输出后缀表达式为：表达式的值为：程序源代码（c++）#include<iostream>#include<string>#include<stack>#include<iomanip>constintMaG=100;usingnamespacestd;classNode{public:charch[MaG];//考虑到数值有时会是两位数，所以使用字符串数组NodeGlChild;NodeGrChild;Node(){strcpy(ch,"");lChild=rChild=NULL;}~Node(){if(lChild!=NULL)deletelChild;if(rChild!=NULL)deleterChild;}};staticintcount=0;staticchararray[MaG];//保存原始的中缀表达式staticcharstr[2GMaG];//保存后序遍历出来的字符串，为表达式求值提供方便staticintk=0;chargetOp(NodeGtemp);//temp指针保存每个结点，返回的是运算符NodeGcrtTree(NodeGroot);//传入根结点指针，返回根结点指针voidoutput(NodeGroot);//获得处理后的字符串boolisError(char);//判断字符是否有问题voiddeal();//对字符数组进行处理doublevalue(string);//计算后缀表达式，得到其结果。

算术表达式求值实验报告前言算术表达式求值是计算机科学中比较基础的内容，同时也是很实用的技能，因为有时候我们需要用程序来计算一些复杂的数学运算。

在本次实验中，我们将对算术表达式的求值进行深入研究，并实际编写程序来实现这一功能。

实验原理算术表达式通常由数字、运算符和括号组成，我们需要将其转换为计算机能够直接执行的形式。

常见的算术表达式求值方法有两种：1.中缀表达式求值中缀表达式就是我们平时所熟悉的数学表达式，如2+3*4-5/2。

中缀表达式求值需要遵循一定的运算符优先级和括号的影响，可以通过栈来实现。

首先，我们需要将中缀表达式转换为后缀表达式，即将运算符放在数字后面。

具体的转换方法可以使用栈来实现。

遍历中缀表达式，遇到数字就直接输出，遇到运算符就将其与栈顶运算符进行比较，如果优先级高于栈顶运算符，则将其入栈，否则将栈顶运算符弹出并输出，直到遇到优先级小于等于栈顶运算符或者栈顶为空时，将运算符入栈。

最后将栈中的运算符依次弹出并输出即可。

转换为后缀表达式之后，我们可以通过再次遍历后缀表达式来求值。

遇到数字将其入栈，遇到运算符则弹出栈顶两个数字进行运算，并将结果入栈。

遍历完毕后，栈中剩下的数字就是最终结果。

2.前缀表达式求值前缀表达式就是将运算符放在数字前面的表达式，如：- + * 3 4 5 6。

前缀表达式求值与后缀表达式求值类似，不同之处在于需要从右至左遍历表达式，并将运算符与栈顶数字进行操作。

实验步骤在本次实验中，我们将通过 Python 语言来实现算术表达式求值功能。

具体步骤如下：1. 输入待求值的算术表达式。

2. 对算术表达式进行转换，得到后缀表达式或前缀表达式。

3. 遍历后缀表达式或前缀表达式，求出最终结果。

4. 输出结果。

实验结果我们在 Python 中编写了求解算术表达式的程序，以下是一些样例输入和输出：1. 输入：2+3*4 输出：142. 输入：(2+3)*4 输出：203. 输入：-+*3456 输出：-9通过多组测试，我们可以发现程序能够正确地求解各种算术表达式，包括包含括号和负数的表达式。

(一) 需求分析1、输入的形式和输入值的范围：根据题目要求与提示，先选择你要使用的表达式形式（中缀用1，后缀用0），在输入一个中缀表达式，输入数的范围为int型，此时，程序将计算出表达式的结果。

2、输出的形式：当按照程序要求选择了1或0之后，再输入表达式；如果选择的是1，则程序将自动运算出表达式结果；如果之前选择的是0，则程序将现将中缀表达式转化为后缀表达式并计算出结果。

3、程序所能达到的功能：本程序能计算出含+、-、*、/、（、）等运算符的简单运算。

4、测试数据：输入一个表达式，如果你之前选择的是“中缀表达式”，那么输入5*(4-2)#,那么输出结果是10；如果之前选择的是“后缀表达式”，那么输入5*（4-2）#，那么他将先转换成后缀表达式5 4 2 - * #，再输出结果10。

如果输入表达式没有结束标示符#，如5*（4-2），那将不会输出任何结果，或出现错误结果。

(二) 概要设计为了实现上述操作，应以栈为存储结构。

1．基本操作：（1）. int GetTop(SqStack *s)初始条件：栈存在；操作结果：若栈为空，则返回s的栈顶元素；否则返回ERROR。

（2）.void Push(SqStack *s,int e)初始条件：栈存在；操作结果：插入e为新的栈顶元素。

（3）.int Pop(SqStack *s)初始条件：栈存在；操作结果：若栈不空，则删除之，并返回其值；否则返回REEOR。

（4）.void InitStack(SqStack *s)初始条件：栈存在；操作结果：置栈为空。

（5）.int Empty(SqStack *s)初始条件：栈存在；操作结果：判定s是否为空栈。

（6）.int Operate(int a,char theta, int b)初始条件：操作数a和b存在，且theta是+、-、*、/四则运算；操作结果：返回a与b间theta运算的结果。

（7）.int In(char s,char* TestOp)初始条件：s为待判断字符，TestOp为已知的算符集合；操作结果：s为算符集合中的元素则返回1，否则返回0.（8）.int ReturnOpOrd(char op,char* TestOp)初始条件：op为待确定运算符，TestOp为已知的算符集合；操作结果：确定运算符类型。

数据结构表达式求值（中缀）实验报告题目名称表达式求值学号姓名指导教师日期一1. 问题描述：在计算机中，算术表达式由常量、变量、运算符和括号组成。

由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行，在程序设计时，借助栈实现。

2. 表达式求值这个程序，主要利用栈和数组，把运算的先后步骤进行分析并实现简单的运算，以字符列的形式从终端输入语法的正确的、不含变量的整数表达式。

利用已知的算符优先关系，实现对算术四则运算的求值，在求值中运用栈、运算栈、输入字符和主要操作的变化过程。

该程序相当于一个简单的计算机计算程序，只进行简单的加减乘除和带括号的四则运算。

1、基本思想（中缀表达式求值）要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式，要了解算术四则运算的规则即：（1）先乘除后加减；（2）从左到右计算；（3）先括号内，后括号外。

下表定义的运算符之间的关系:b + - * / （） # a+ > > < < < > > _ > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = ) > > > > > > # < < < < < =为了实现运算符有限算法，在程序中使用了两个工作栈。

分别是：运算符栈OPTR,操作数栈OPND.基本思想：（1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2）依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈得栈顶运算符比较优先级后作相应操作。

实验三基于栈结构的中缀表达式求值班级：计科131、问题描述从键盘输入一中缀表达式字符串，读字符串，利用栈结构实现表达式求值。

2、输入与输出输入：从键盘中缀表达式如： 32＋5×（6－4）输出：计算结果423、需求分析1.定义两个栈结构，数栈用于存放表达式中的数，符号栈用于存放表达式中的符号，实现栈的运算2.在读数的时候考虑多位运算3.实现表达式求值4、开发工具与环境硬件设备：微型计算机系统软件环境：操作系统Windows，开发工具等等5、概要设计1.结构定义typedef struct /* 运算符栈 */{ char *base,*top;int stacksize;}SqStack;typedef struct /* 运算数栈 */{ int *base,*top;int stacksize;}SqStack1;int priority[7][7]={{'>', '>', '<', '<', '<', '>', '>'}, // +{'>', '>', '<', '<', '<', '>', '>'}, // -{'>', '>', '>', '>', '<', '>', '>'}, // *{'>', '>', '>', '>', '<', '>', '>'}, // /{'<', '<', '<', '<', '<', '=', }, // ({'>', '>', '>', '>', ' ', '>', '>'}, // ){'<', '<', '<', '<', '<', ' ', '='} // #};/*用于比较符号优先级的全局二维数组*/2．各函数模块void InitStack(SqStack *s);操作结果：初始化运算符栈。

数据结构表达式求值实验报告数据结构表达式求值实验报告1. 引言表达式求值是计算机科学中的一个重要问题，也是数据结构的一个经典应用。

通过将中缀表达式转换为后缀表达式，并利用栈这一数据结构，可以实现对表达式的有效求值。

本实验旨在探究数据结构在表达式求值中的应用。

2. 实验内容本实验中，我们将实现一个表达式求值的程序。

具体步骤如下：1. 将中缀表达式转换为后缀表达式。

2. 使用栈来求解后缀表达式。

3. 算法原理3.1 中缀表达式转后缀表达式中缀表达式是我们常见的数学表达式，如 2 + 3 4。

而后缀表达式是将操作符放在操作数后面的表达式，上述中缀表达式的后缀表达式为 2 3 4 +。

中缀表达式到后缀表达式的转换可以通过以下步骤完成：1. 初始化一个栈和一个输出队列。

2. 从左到右遍历中缀表达式的每个字符。

3. 如果当前字符是数字，将其加入输出队列。

4. 如果当前字符是左括号，将其压入栈。

5. 如果当前字符是右括号，将栈中的操作符依次弹出并加入输出队列，直到遇到左括号为止。

6. 如果当前字符是操作符，将其与栈顶操作符进行比较：1. 如果栈为空，或者栈顶操作符为左括号，直接将当前操作符压入栈。

2. 否则，比较当前操作符与栈顶操作符的优先级，如果当前操作符的优先级较低，将栈顶操作符弹出并加入输出队列，然后将当前操作符压入栈。

3. 如果当前操作符的优先级大于等于栈顶操作符的优先级，则直接将当前操作符压入栈。

7. 遍历完中缀表达式后，将栈中的操作符依次弹出并加入输出队列。

3.2 后缀表达式求值通过将中缀表达式转换为后缀表达式，我们可以利用栈来对后缀表达式进行求值。

具体求值操作如下：1. 初始化一个栈。

2. 从左到右遍历后缀表达式的每个字符。

3. 如果当前字符是数字，将其加入栈。

4. 如果当前字符是操作符，从栈中弹出两个数字，进行相应的运算，然后将结果加入栈。

5. 遍历完后缀表达式后，栈中的元素即为最终的结果。

4. 实验结果我们用中缀表达式\。

程序设计实训报告—表达式求值问题完成者：何炜班级：计科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.对后缀表达式进行求值四、详细设计以下对概要设计进行详细的原理分析。

一、实验目的1. 理解中缀表达式及其求值原理。

2. 掌握中缀表达式的转换方法，即将中缀表达式转换为后缀表达式。

3. 实现中缀表达式的求值算法，并编写相应的程序。

二、实验原理中缀表达式是一种常见的数学表达式表示方式，其特点是运算符位于操作数之间。

例如，表达式 "3 + 4 2" 就是一个中缀表达式。

中缀表达式转换为后缀表达式（也称为逆波兰表达式）是求值的关键步骤，因为后缀表达式可以直接按照运算符的优先级进行计算。

中缀表达式转换为后缀表达式的基本原理如下：1. 创建一个栈，用于存储运算符。

2. 从左到右扫描中缀表达式中的每个字符。

3. 如果是操作数，直接输出到结果字符串。

4. 如果是运算符，比较当前运算符的优先级与栈顶运算符的优先级。

a. 如果栈为空或者栈顶元素是左括号 "(", 将当前运算符压入栈中。

b. 如果当前运算符的优先级高于栈顶运算符的优先级，或者栈顶元素是右括号")", 将当前运算符压入栈中。

c. 如果当前运算符的优先级低于或等于栈顶运算符的优先级，将栈顶运算符弹出并输出到结果字符串，然后重复步骤 4。

5. 当扫描完中缀表达式后，将栈中的所有运算符依次弹出并输出到结果字符串。

6. 将中缀表达式转换为后缀表达式后，按照后缀表达式的规则进行求值。

三、实验步骤1. 定义一个函数，用于判断字符是否为操作数。

2. 定义一个函数，用于判断字符是否为运算符。

3. 定义一个函数，用于判断运算符的优先级。

4. 定义一个函数，用于将中缀表达式转换为后缀表达式。

5. 定义一个函数，用于求值后缀表达式。

6. 编写主函数，实现中缀表达式的求值。

四、实验代码```pythondef is_operand(c):return c.isdigit()def is_operator(c):return c in ['+', '-', '', '/', '(', ')']def precedence(op):if op in ['+', '-']:return 1if op in ['', '/']:return 2return 0def infix_to_postfix(expression):stack = []postfix = []for c in expression:if is_operand(c):postfix.append(c)elif c == '(':stack.append(c)elif c == ')':while stack and stack[-1] != '(':postfix.append(stack.pop())stack.pop()else:while stack and precedence(stack[-1]) >= precedence(c): postfix.append(stack.pop())stack.append(c)while stack:postfix.append(stack.pop())return postfixdef evaluate_postfix(postfix):stack = []for c in postfix:if is_operand(c):stack.append(int(c))else:b = stack.pop()a = stack.pop()if c == '+':stack.append(a + b)elif c == '-':stack.append(a - b)elif c == '':stack.append(a b)elif c == '/':stack.append(a / b)return stack[0]def evaluate_infix(expression):postfix = infix_to_postfix(expression)return evaluate_postfix(postfix)# 主函数if __name__ == '__main__':expression = input("请输入中缀表达式：")result = evaluate_infix(expression)print("结果为：", result)```五、实验结果与分析1. 输入中缀表达式 "3 + 4 2"，程序输出结果为 11，与预期一致。

课程设计报告课程名称数据结构课题名称中缀算术表达式求值专业通信工程班级通信0902学号姓名指导教师2011 年07 月01 日湖南工程学院课程设计任务书课程名称数据结构课题中缀算术表达式求值专业班级通信工程0902学生姓名学号指导老师审批任务书下达日期2011 年06 月27日任务完成日期2011 年07 月01日设计要求：1. 课程设计报告规范（1）需求分析a.程序的功能。

b.输入输出的要求。

（2）概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。

b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。

（3）详细设计a.采用C语言定义相关的数据类型。

b．写出各模块的类C码算法。

c.画出各函数的调用关系图、主要函数的流程图。

（4）调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。

b.程序调试中遇到的问题以及解决问题的方法。

c.课程设计过程经验教训、心得体会。

（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。

（6）书写格式a.设计报告要求用A4纸打印成册：b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。

（7）附录源程序清单（带注释）2. 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。

具体考核标准包含以下几个部分：（1）平时出勤（占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。

数据结构第3章中缀表达式数据结构实验报告（第三章）实验类型：综合性实验班级：学号：姓名：实验⽇期：2014年5⽉24⽇⼀、表达式求值1.问题描述表达式是数据运算的基本形式。

⼈们的书写习惯是中缀式，如：11+22*(7-4)/3。

中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进⾏计算。

表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀式（如：+ 11 / * 22 – 7 4 3）。

后缀表达式和前缀表达式中没有括号，给计算带来⽅便。

如后缀式计算时按运算符出现的先后进⾏计算。

本设计的主要任务是进⾏表达式形式的转换及不同形式的表达式计算。

2.基本要求●从⽂件或键盘读⼊中缀表达式。

●设计操作数为多位整数，操作符为加、减、乘、除、求模的中缀表达式求值算法。

●设计将中缀表达式转换为后缀表达式的算法。

●设计将中缀表达式转换为前缀表达式的算法。

●设计后缀表达式求值算法。

●设计前缀表达式求值算法。

●输出各种形式的表达式。

3.数据结构设计任何⼀个表达式都是由操作符，运算符和界限符组成的。

我们分别⽤顺序栈来寄存表达式的操作数和运算符。

栈是限定于紧仅在表尾进⾏插⼊或删除操作的线性表。

顺序栈的存储结构是利⽤⼀组连续的存储单元依次存放⾃栈底到栈顶的数据元素，同时附设指针top指⽰栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插⼊新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。

typedef struct{int *base;int *top;int numstacksize; //数字栈}numstack;typedef struct{char *base;char *top;int charstacksize;//字符栈}charstack;4.算法设计（1）中缀表达式求值1.从左到右读⼊中缀表达式，每次⼀个字符。

数据结构实训总结报告题目：表达式求值学生姓名：学生学号：专业班级：指导老师：目录1.课题分析 .....................................................................1．1需求分析..............................................................1. 2设计要求............................................................2.总体设计.......................................................................2．1主程序的流程.....................................................3.详细设计（步骤及代码实现） ...................................3. 1判断运算符优先级..............................................3. 2中缀表达式转后缀表达式..................................3. 3后缀表达式求值.................................................. 4．测试结果 .................................................................... 5．心得体会 .................................................................... 6．参考文献 ....................................................................1.课题分析1．1需求分析（1）栈“后进先出”的特点。

表达式求值实验报告表达式求值实验报告一、引言表达式求值是计算机科学中一个重要的概念，它涉及到对数学表达式的计算和求解。

在本次实验中，我们将探讨表达式求值的相关算法和实现方法，并通过编程实现一个简单的表达式求值器。

二、算法原理1. 表达式的表示方法在计算机中，我们通常使用字符串来表示表达式。

例如，一个简单的数学表达式"2 + 3 * 4"可以表示为字符串"2+3*4"。

在实现表达式求值的算法时，我们需要将字符串中的数字和运算符进行分离，以便进行后续的计算。

2. 中缀表达式转后缀表达式为了方便计算，我们通常将中缀表达式转换为后缀表达式。

后缀表达式也称为逆波兰表达式，它的特点是运算符位于操作数的后面。

例如，上述的中缀表达式"2+3*4"可以转换为后缀表达式"234*+"。

转换的方法可以通过使用栈来实现。

3. 后缀表达式求值得到后缀表达式后，我们可以通过扫描表达式并使用栈来求解。

当遇到操作数时，将其压入栈中；当遇到运算符时，从栈中弹出相应数量的操作数进行计算，并将结果压入栈中。

最终，栈中的唯一元素即为表达式的求值结果。

三、实验过程1. 数据结构设计为了实现表达式求值器，我们需要设计相应的数据结构。

在本次实验中，我们选择使用栈来存储操作数和运算符。

2. 中缀表达式转后缀表达式首先，我们需要编写一个函数来将中缀表达式转换为后缀表达式。

该函数的实现可以通过使用栈和遍历字符串来实现。

具体的步骤如下：- 创建一个空栈和一个空字符串用于存储后缀表达式。

- 从左到右遍历中缀表达式的每个字符。

- 如果遇到操作数，直接将其添加到后缀表达式字符串中。

- 如果遇到运算符，将其与栈顶的运算符进行比较：- 如果栈为空或栈顶为左括号"("，则直接将运算符入栈。

- 如果栈顶的运算符优先级低于当前运算符，则将当前运算符入栈。

- 如果栈顶的运算符优先级高于或等于当前运算符，则将栈顶的运算符弹出并添加到后缀表达式字符串中，直到栈顶的运算符优先级低于当前运算符或栈为空。

数据结构表达式求值实验报告一、实验目的本次实验的主要目的是通过实现表达式求值的程序，深入理解数据结构和算法在解决实际问题中的应用。

具体包括掌握栈这种数据结构的操作和使用，熟悉表达式的转换和计算过程，提高编程能力和问题解决能力。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

三、实验原理表达式求值是程序设计中的一个常见问题，通常采用栈这种数据结构来实现。

表达式可以分为中缀表达式、后缀表达式和前缀表达式。

中缀表达式是我们日常使用的表达式形式，如“2 ＋3 4”，但直接对中缀表达式求值比较复杂。

而后缀表达式（如“2 3 4 ＋”）和前缀表达式（如“＋2 3 4”）求值相对简单。

因此，在实现表达式求值时，通常先将中缀表达式转换为后缀表达式，然后对后缀表达式进行求值。

转换过程中，使用两个栈，一个用于存储操作数，另一个用于存储运算符。

求值过程中，根据后缀表达式的特点，从左到右依次处理操作数和运算符，进行相应的计算。

四、实验步骤1、定义数据结构定义栈类，用于存储操作数和运算符。

定义一个结构体来表示操作数和运算符。

2、中缀表达式转后缀表达式从左到右扫描中缀表达式。

遇到操作数，直接输出。

遇到运算符，根据其优先级与栈顶运算符的优先级进行比较，决定入栈或出栈操作。

3、后缀表达式求值从左到右扫描后缀表达式。

遇到操作数，入栈。

遇到运算符，从栈中取出两个操作数进行计算，将结果入栈。

4、主函数输入中缀表达式。

调用转换函数和求值函数，输出计算结果。

五、实验代码｀｀｀cppinclude ＜iostream>include ＜stack>include ＜string>／／定义操作符的优先级int priority(char op) ｛if （op ＝＝＇＋＇｜｜ op ＝＝＇＇）return 1;if （op ＝＝＇＇｜｜ op ＝＝＇／＇）return 2;return 0;｝／／中缀表达式转后缀表达式std:：string infixToPostfix(std:：string infix) ｛std:：stack<char> opStack;std:：string postfix ＝＂＂；for （char c ： infix) ｛if （isdigit(c)）｛postfix ＋＝ c;｝ else if （c ＝＝＇（＇）｛｝ else if （c ＝＝＇）＇）｛while （！opStackempty(）＆＆ opStacktop(）！＝＇（＇）｛postfix ＋＝ opStacktop(）；opStackpop(）；｝opStackpop(）；／／弹出＇（＇｝ else ｛while （！opStackempty(）＆＆ priority(opStacktop(））＞＝priority(c)）｛postfix ＋＝ opStacktop(）；opStackpop(）；｝opStackpush(c)；｝｝while （！opStackempty(））｛postfix ＋＝ opStacktop(）；｝return postfix;｝／／后缀表达式求值int evaluatePostfix(std:：string postfix) ｛std:：stack<int> operandStack;for （char c ： postfix) ｛if （isdigit(c)）｛operandStackpush(c ＇0'）；｝ else ｛int operand2 ＝ operandStacktop(）；operandStackpop(）；int operand1 ＝ operandStacktop(）；operandStackpop(）；switch （c) ｛case ＇＋＇：operandStackpush(operand1 ＋ operand2)；break;case ＇＇：operandStackpush(operand1 operand2)；break;case ＇＇：operandStackpush(operand1 operand2)；break;case ＇／＇：operandStackpush(operand1 ／ operand2)；break;｝｝｝return operandStacktop(）；｝int main(）｛std:：string infixExpression;std:：cout ＜＜＂请输入中缀表达式: ＂；std:：cin ＞＞ infixExpression;std:：string postfixExpression ＝ infixToPostfix(infixExpression)；int result ＝ evaluatePostfix(postfixExpression)；std:：cout ＜＜＂表达式的计算结果为: ＂＜＜ result ＜＜ std:：endl;return 0;｝｀｀｀六、实验结果输入不同的中缀表达式，如“2 ＋3 4”“（ 2 ＋ 3 ）4”等，程序能够正确地将其转换为后缀表达式，并计算出结果。

竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告篇一：数据结构实验二——算术表达式求值实验报告《数据结构与数据库》实验报告实验题目算术表达式求值学院：化学与材料科学学院专业班级：09级材料科学与工程系pb0920603姓学邮名：李维谷号：pb09206285箱：指导教师：贾伯琪实验时间：20XX年10月10日一、需要分析问题描述：表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。

设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。

问题分析：在计算机中，算术表达式由常量、变量、运算符和括号组成。

由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。

因而在程序设计时，借助栈实现。

设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。

在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。

在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。

算法规定：输入形式：一个(:数据结构表达式求值实验报告)算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。

为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。

输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。

程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。

测试数据：正确输入：12*（3.6/3+4^2-1）#输出结果：194.4无定义运算：12*（3.6/（2^2-4）+1）#输出结果：表达式出错，除数为0，无意义错误输入：12+s#输出结果：eRRoR！二、概要设计拟采用两种类型的展分别对操作数和操作符进行操作。

实验报告姓名：黄雄镖学号：13331093院系专业：软件学院2013级教务4班完成日期：2014 年10 月20 日实验题目：实现一个较为通用的计算器需求分析：实现一个包含加减乘除运算的较为通用的计算器，操作数可能是负数，并且可能是多位数。

运算式中可以有括号和多余空格。

计算器对负号不敏感, 形如1+-1或者1+(-1)都是可以接受的。

概要设计思路: 将表达式的中缀表达式转换成后缀表达式，然后利用一个栈或者建立二叉树对后缀表达式进行求值。

由于多位数在转为后缀表达式时会分不清, 故在每个数和运算符后面加上一个空格作为区别在主程序中调用用栈求值的计算器类和用二叉树计算的计算器类, 输出算式的结果13331093_03.h里存放用栈求值的计算器类13331093_03_tree.h里存放用二叉树计算的计算器类13331093_03.h的类里主要包括:获得算术表达式的函数getexpression(string expression), expression为所要计算的算术表达式计算函数calculate(string num2, string num1, string op), 输入为两个数(字符串形式)和一个操作符, 返回值为计算结果(字符串形式)返回中缀表达式函数ShowMiddleExpression(), 返回的中缀表达式为字符串形式RidSpace(string origin)用于去除输入中多余的空格, 输入为要除去空格的算术表达式, 返回去掉空格的算术表达式MidToLast(string str)中缀表达式转后缀表达式获得后缀表达式函数GetLastExpression(), 返回的后缀表达式为字符串形式用栈执行计算后缀表达式函数exe(), 返回计算结果为字符串形式13331093_03_tree.h类里主要包括:获得算术表达式的函数getexpression(string expression), expression为所要计算的算术表达式计算函数calculate(string num2, string num1, string op), 输入为两个数(字符串形式)和一个操作符, 返回值为计算结果(字符串形式)返回中缀表达式函数ShowMiddleExpression(), 返回的中缀表达式为字符串形式RidSpace(string origin)用于去除输入中多余的空格, 输入为要除去空格的算术表达式, 返回去掉空格的算术表达式MidToLast(string str)中缀表达式转后缀表达式获得后缀表达式函数GetLastExpression(), 返回的后缀表达式为字符串形式生成一颗二叉树的函数makeTree(TNode *&p)后序遍历二叉树并计算的函数PostOrder(TNode *p), 返回计算结果为字符串形式a.调试过程遇到的问题与解决方案：遇到的问题:调试过程中出现程序崩溃的现象, 后来debug发现是没有考虑到执行运算过程中出现的-()的情况原因:没有考虑-()的情况, 导致栈为空的时候还弹出元素解决方案：特殊处理这种情况b.时间和空间复杂度：除去输入中空格的操作的时间复杂度为O(n),中缀表达式转后缀表达式的时间复杂度为O(n), 用栈执行运算的时间复杂度为O(n),后序遍历二叉树的时间复杂度为O(n) 所以用栈计算或者用二叉树计算的操作的时间复杂度为都是O(n)栈属于线性表, 故用栈计算的空间复杂度为O(n)用二叉树计算的空间复杂度也是O(n)主程序:输入一个整数m，代表有m个输入接下来有m行，每一行输入你要计算的式子13331093_03.h:含有用stack计算的计算器类用法:calculator c_stack 声明一个计算器对象c_stack.getexpression(expression) 把算术表达式存入计算器中expression为所要计算的算术表达式c_stack.GetLastExpression() 获取算术表达式的后缀表达式c_stack.exe() 获取计算结果13331093_03_tree.h:含有用二叉树计算的计算器类用法:calculator_tree c_tree 声明一个计算器对象c_tree.getexpression(expression) 把算术表达式存入计算器中expression为所要计算的算术表达式c_tree.GetLastExpression() 获取算术表达式的后缀表达式c_tree.makeTree(tree) 建立一棵二叉树c_tree.PostOrder(tree) 后序遍历二叉树并返回计算结果测试结果在主程序中调用用栈求值的计算器类和用二叉树计算的计算器类, 并对输入表达式进行两种方法所生成的后缀表达式和结果的对比测试代码在test.cpp中测试输入:11-(12.34)-11+-21+(-2)11 + 23 * 32/4-8-1.234/5 *(1 +3)2.333*4-(3+(-5))12345+5432.1/(-12345)-(100 ) * 0.5 -(-22.22)1234/-123+3.333-( 123*50 ) / 2.2测试结果如下:另外我用计算器算过, 结果是正确的实验心得通过这次实验, 我对栈和二叉树的理解加深了很多。

问题描述：四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。

一、需求分析：1、本程序是利用二叉树后序遍历来实现表达式的转换，同时可以使用实验三的结果来求解后缀表达式的值。

2、输入输出格式：输入格式：在字符界面上输入一个中缀表达式，回车表示结束。

请输入表达式：输入一个中缀表达式输出格式：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。

逆波兰表达式为：输出逆波兰表达式运算结果为：输出运算后的结果3、测试用例输入：21+23*（12-6）输出：21 23 12 6 -*+二、概要设计：抽象数据类型二叉树类BiTree算法的基本思想根据题目要求，利用栈计算，和二叉树存储，来计算表达式该算法的基本思想是：先利用栈进行计算，然后用二叉树进行存储，和实验三算法一样来计算逆波兰表达式的值程序的流程程序由三个模块组成：（1）输入模块：输入一个运算式（2）计算模块：利用栈进行表达式的计算，二叉树来存储。

（3 ）输出模块：屏幕上显示出后缀表达式和运算结果。

三、详细设计物理数据类型程序含有两个类，其中栈不再赘述，另一个类为二叉树class BiTree 包含私有成员struct BiTreeNode，根节点BiTreeNode *T;索引index; int number_of_point 优先级比较函数 compare(char a,char b);生成树的函数void InorderCreate(BiTreeNode *&T,char str[30][10],int start,int end);判断数字函数bool IsNumber(char a);求值函数double Operate(BiTreeNode *T);还有显示后缀表达式的函数void display(BiTreeNode *T) ;而公有成员函数则是对私有函数的重载，为方便使用，因为函数中普遍使用了递归的算法。