【C++】朝花夕拾—

【C++】朝花夕拾——表达式树

表达式树:

　　　　　　　叶子是操作数，其余结点为操作符，是二叉树的其中一种应用

====================我是分割线======================

一棵表达式树如下图：　

　　若是对它做中序遍历，则可以得到中缀表达式

　　　　　　做后序遍历，则可以得到后缀表达式

已知树的结点可以表示成：

1 struct TreeNode {
2      object element;
3      TreeNode* leftChild;
4      TreeNode* rightChild;
5  };

用后缀表达式构建一棵表达式树：

　　思路：（与后缀表达式计算四则运算结构相似）

　　　　　1. 一一读入输入字符串

　　　　　2. 若是操作数，则初始化为结点后入栈

　　　　　3. 若是操作符，则从栈中弹出两个结点（新结点的左右子树），与刚读入的操作符结合起来构建新结点，然后入栈

　　　　　重复1~3，最后栈内有一棵表达式树的root结点

code实现：

 1 #include<iostream>
 2 #include <string>
 3 #include<stack>
 4 
 5 using namespace std;
 6 
 7 struct TreeNode{
 8     char element;
 9     TreeNode* leftChild;
10     TreeNode* rightChild;
11     TreeNode(char ch, TreeNode* l, TreeNode* r) {
12         element = ch;
13         leftChild = l;
14         rightChild = r;
15     }
16     TreeNode() {
17         element = '0';
18         leftChild = 0;
19         rightChild = 0;
20     }
21 };
22 
23 //测试函数——输出树
24 void drawTree(TreeNode* root, bool infix) {
25     if (infix) {
26         if (root) {
27             //中序遍历
28             drawTree(root->leftChild, infix);
29             cout << root->element;
30             drawTree(root->rightChild, infix);
31         }
32         else return;
33     }
34     else {
35         if (root) {
36             //后序遍历
37             drawTree(root->leftChild, infix);
38             drawTree(root->rightChild, infix);
39             cout << root->element;
40         }
41         else return;
42     }
43 }
44 
45 int main() {
46     string input;
47     stack<TreeNode> expressionTree;
48     while (cin >> input) {
49         if (input == "0") break;
50         for (int i = 0; i < input.size();) {
51             char ch = input[i++];
52             if (ch >= '0' && ch <= '9') {
53                 TreeNode leaves;
54                 leaves.element = ch;
55                 expressionTree.push(leaves);
56             }
57             else {
58                 //出栈，成为新结点右子树
59                 TreeNode* right = new TreeNode(expressionTree.top().element, expressionTree.top().leftChild, expressionTree.top().rightChild);
60                 expressionTree.pop();
61 
62                 ////出栈，成为新结点左子树
63                 TreeNode* left = new TreeNode(expressionTree.top().element, expressionTree.top().leftChild, expressionTree.top().rightChild);
64                 expressionTree.pop();
65 
66                 //新结点入栈
67                 TreeNode leave(ch, left, right);
68                 expressionTree.push(leave);
69             }
70         }
71         TreeNode* root = &expressionTree.top();
72         expressionTree.pop();
73         drawTree(root, true);
74     }
75     return 0;
76 }
77 
78 //NULL 与 0 的概念

局限性：

　　1. 假设所有输入合法，无空格等非法符号输入

　　2. 测试输出函数不能还原优先级，12+3* 的表达式树测试输出将是 1+2*3，而并非（1+2）*3，如果需要，可以在结构体中再加上一个优先级判断，若子结点的操作符优先级小于父结点，则输出时子树的表达式需要最后要整体放到一个括号内。

一些bugs:

　　关于NULL、0 和 nullptr的学习：

　　　　1. NULL是宏

　　　　2. C中对于NULL的定义为 #define NULL ((void *)0)

　　　　3. C++中对于NULL的定义为0

　　　　　　#ifdef __cplusplus
　　　　　　#define NULL 0
　　　　　　#else
　　　　　　#define NULL ((void *)0)
　　　　　　#endif

　　　　4. C++11中对于nullptr的定义　　　　　　

 1 const
 2 class nullptr_t
 3 {
 4 public:
 5     template<class T>
 6     inline operator T*() const
 7         { return 0; }
 8 
 9     template<class C, class T>
10     inline operator T C::*() const
11         { return 0; }
12  
13 private:
14     void operator&() const;
15 } nullptr = {};

　　　　5. 由于C++中的定义，在重载函数时容易出错

 1 //NULL  0   nullptr
 2 #include <iostream>
 3 #include <stdio.h>
 4 
 5 using namespace std;
 6 
 7 int f(void* ptr) {
 8     return 2;
 9 }
10 
11 int f(int num) {
12     return 3;
13 }
14 
15 int main() {
16     int result1 = f(0);
17     //int result2 = f(NULL);
18     int result3 = f(nullptr);
19     cout << "result1 = " << result1 << endl;
20     //cout << "result2 = " << result2 << endl;
21     cout << "result3 = " << result3 << endl;
22     return 0;
23 }

　　　　当我把17行的注释符去掉时：编译错误

　　　　最后运行的结果如下：

　　　　说明C++11标准中，nullptr的调用在重载时不会又歧义，而0则会在重载时调用int形参的函数

　　　　在C++中，可以的话，尽量用nullptr为空指针赋值

　　　　文章推荐：

　　　　　　http://www.cppblog.com/airtrack/archive/2012/09/16/190828.html