# 基于C++实现的表达式计算
# 一、使用说明
## 1.1 操作手册
运行程序后，进入欢迎界面，首先要输入中缀表达式。
第一步，输入中缀表达式。
第三步，进行具体操作。
### 1.1.1 波兰表达式
在第一行输出波兰表达式，例如：
### 1.1.2 中缀表达式
在第二行输出中缀表达式，例如：
### 1.1.3 逆波兰表达式
在第三行输出逆波兰表达式，例如：
# 二、概述
## 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) | 前序遍历 | 开始前序遍历的节点 | |
# 四、体会
这道题让我练习了树这个数据结构，并从这个题目中我明白了二叉树的前中后序遍历是怎么一回事。并明白了计算机是怎么从我们输入的中缀表达式计算出值得。收益颇多。
