# 表达式计算
# 一、使用说明
## 1.1 操作手册
运行程序后,进入欢迎界面,首先要输入中缀表达式。
第一步,输入中缀表达式。
![](http://www.writebug.com/myres/static/uploads/2021/10/19/93994aee251a05f65a8a2fa2de277554.writebug)
![](http://www.writebug.com/myres/static/uploads/2021/10/19/05df4f03efece72c34b16c6511f73bde.writebug)
第三步,进行具体操作。
### 1.1.1 波兰表达式
在第一行输出波兰表达式,例如:
![](http://www.writebug.com/myres/static/uploads/2021/10/19/a4cc372851225d798fe471dcf7a9eae2.writebug)
### 1.1.2 中缀表达式
在第二行输出中缀表达式,例如:
![](http://www.writebug.com/myres/static/uploads/2021/10/19/1bd15fd0b3346ce0aec3671c73cb921e.writebug)
### 1.1.3 逆波兰表达式
在第三行输出逆波兰表达式,例如:
![](http://www.writebug.com/myres/static/uploads/2021/10/19/05df4f03efece72c34b16c6511f73bde.writebug)
# 二、概述
## 2.1 程序设计目的
运用树的知识对于表达式生成一个二叉树,通过树的前中后序遍历来输出波兰表达式、中缀表达式和逆波兰表达式。
## 2.2 算法思路
本题的算法非常简单,针对不同的类型有不同的优先级,通过运算符栈和数字栈两个数据结构将表达式最终表达成一个树。遇到数字直接进入数字栈,遇到运算符则判定运算符栈栈顶运算符和当前运算符的优先级大小,判定是否出栈运算或是入栈。如果运算符出栈就从数字栈取两个数值生成节点,然后再压回数字栈,直到表达式解析完。
## 2.3 数据结构
每一个树的节点都是一个结构体,整个树是一个类,采用树形的数据结构。
# 三、函数接口
## 3.1 node结构体
| 成员 | 功能 |
| ----------------- | -------- |
| Char data | 存储节点内容 |
| Node \*leftChild | 指向节点的左子树 |
| Node \*rightChild | 指向节点的右子树 |
## 3.2 Tree接口
| 成员函数名 | 功能 | 参数 | 返回值类型 |
| -------------------------------- | ------------------ | --------- | ------------ |
| Tree() | 默认构造函数,使根节点指向NULL。 | | |
| Tree(const string s) | 生成表达式树 | 一个中缀表达式 | |
| Node * buildTree(const string s) | 生成表达式树的核心函数 | 一个中缀表达式 | Node * |
| Node * create() | 初始化节点 | | 一个已经分配了空间的节点 |
| Node * getRoot() | 获取根节点 | | Node * |
| void PostOrder(Node * node) | 后序遍历 | 开始后序遍历的节点 | |
| void InOrder(Node * node) | 前序遍历 | 开始前序遍历的节点 | |
# 四、体会
这道题让我练习了树这个数据结构,并从这个题目中我明白了二叉树的前中后序遍历是怎么一回事。并明白了计算机是怎么从我们输入的中缀表达式计算出值得。收益颇多。