实验五 基于二叉树的表达式求值 一、实验目的 1.掌握二叉树的二叉链表存储表示和二叉树的遍历等基本算法。 2.掌握根据中缀表达式创建表达式树的算法。 3.掌握基于表达式树的表达式求值算法。 二、实验内容 问题描述 输入一个表达式(表达式中的数均为小于 10 的正整数)，利用二叉树来表示该 表达式，创建表达式树，然后利用二叉树的遍历操作求表达式的值。 三、实验实习设备及开发环境 Visual studio 2022 四．实验实习过程步骤（注意是主要关键步骤，不是所有步骤，适当文字+截图说明） Fucntion1：建立一个存放运算符的运算符栈和一个存放操作数的树栈。并且写出一系列有关栈操作的函数。因为这里是一个字符栈，一个树栈，所以很多功能都需要写两个函数。

Function2：比较运算符的优先级的函数，通过建一个二维数组，然后通过对应运算符的下标，然后找到对应优先级。

Function3：对表达式进行计算。

Function4：二叉树的创建函数。首先创建操作符栈OPRT，然后初始化。然后创建一个树栈存放子树OPND。然后将’=’压入OPRT来结束运算。然后读取字符串，当读入的是数字的时候，我们将创建一个子树，将数字作为data存储在子树中，然后压入栈中（这里因为读取的是字符串，很可能读取的是多位的数字，所以我们需要将数字合并）。如果读取到的是运算符，我们将比较运算符栈的栈顶元素和这个元素的优先级，如果是栈顶元素大于字符串中的运算符，那么我们就开始进行运算，将栈顶元素弹出，同时弹出两个操作数的子树，然后将他们合并成为一棵树，然后压入操作数栈中。如果是小于，则直接压入运算符数栈中，读取下一位。如果是等于就弹出运算符栈中的栈顶元素，然后读取下一位。

Function5：树的计算函数，利用递归进行运算。

Function6：主函数先建立一个操作数栈指针，然后指向最后得到的操作数栈。取这个操作数栈的栈顶元素，然后进行树的计算，得到结果。

五、实验实习结果及分析 试验成功，但是当我进行这种计算的时候计算的结果就不正确了。我觉得是优先级的问题，然后加了括号，但是结果还是-5，目前没找到问题所在。解决了，是在减法的时候，减数和被减数的顺序不对。

六．实验遇到的问题及解决办法，实验心得体会及对此实验的意见或建议（有就写，无可不写）。