中缀表达式求值实验报告

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%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。