【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