表達式二叉樹節點的數據可能是運算數或運算符，可以使用一個聯合體進行存儲；同時還需要一個變量來指示存儲的是運算數還是運算符，可以采用和棧方法求值中一樣的枚舉類型TokenType：

1 typedef enum 2 { 3 BEGIN, 4 NUMBER, 5 OPERATOR, 6 LEFT_BRAC, 7 RIGHT_BRAC 8 } TokenType; 9 10 class Token 11 { 12 public: 13 TokenType _type; 14 union 15 { 16 char op; 17 double num; 18 } _data; 19 };

　　二叉樹方法求值的Calculator類公有繼承自節點數據數據類型為Token類的BinaryTree類：

1 class Calculator : public BinaryTree<Token> 2 { 3 public: 4 void parseExpression(string expression) throw(string); 5 double calculate(); 6 7 private: 8 stack<char> _stkOperators; 9 stack<BinaryTreeNode<Token> *> _stkNodes; 10 stack<double> _stkNumbers; 11 12 static int priority(char op); 13 static double calculate(double d1, char op, double d2) throw(string); 14 15 void postOrder(BinaryTreeNode<Token> * node); 16 void calculateStack() throw(string); 17 void dealWithNumber(char *&pToken) throw(string); 18 void dealWithOperator(char *&pToken) throw(string); 19 void dealWithLeftBrac(char *&pToken) throw(string); 20 void dealWithRightBrac(char *&pToken) throw(string); 21 };

方法parseExpression()用來將表達式轉換為二叉樹，它需要兩個棧，一個用來存儲運算符，一個用來存儲指向子樹的指針；用來存儲浮點類型的棧僅在求值時使用。由于parseExpression方法需要訪問BinaryTreeNode類的私有成員，因此還要在BinaryTreeNode類中聲明Calculator類為友元類。

　　轉換過程與棧方法求值的運算壓棧過程基本相同，當遇到運算數時，生成一個新的節點并將它的指針壓入節點指針棧中；遇到運算符時比較當前運算符和運算符棧棧頂運算符的優先級，若運算符棧棧頂運算符的優先級較高，則為它生成一個新的節點，并從節點指針棧中彈出兩個節點指針，作為新節點的左子樹和右子樹，隨后將這個新節點的指針壓入節點指針棧中，將當前運算符壓入運算符棧中，否則只將當前運算符壓入運算符棧中。最后反復執行上述過程，直至運算符棧為空，節點指針棧的棧頂元素即為指向樹根節點的指針。表達式“1+2*3”和“1*2+3”的轉換過程如下圖：

?

使用代碼描述操作節點指針棧的過程：

1 void Calculator::calculateStack() throw(string) 2 { 3 BinaryTreeNode<Token> * node = new BinaryTreeNode<Token>(); 4 assert(node); 5 node->_data._type = OPERATOR; 6 node->_data._data.op = _stkOperators.top(); 7 _stkOperators.pop(); 8 assert(!_stkNodes.empty()); 9 node->_rightChild = _stkNodes.top(); 10 _stkNodes.pop(); 11 assert(!_stkNodes.empty()); 12 node->_leftChild = _stkNodes.top(); 13 _stkNodes.pop(); 14 _stkNodes.push(node); 15 }

　　根據數學規則以及最后清空運算符棧的過程，parseExpression()方法實現如下：

1 void Calculator::parseExpression(string expression) throw(string) 2 { 3 destory(); 4 while (!_stkNodes.empty()) 5 { 6 _stkNodes.pop(); 7 } 8 while (!_stkOperators.empty()) 9 { 10 _stkOperators.pop(); 11 } 12 TokenType lastToken = BEGIN; 13 14 char * pToken = &expression[0]; 15 while (*pToken) 16 { 17 switch (lastToken) 18 { 19 case BEGIN: 20 if (*pToken == '(') 21 { 22 // an expression begin with a left bracket 23 dealWithLeftBrac(pToken);; 24 lastToken = LEFT_BRAC; 25 } 26 else 27 { 28 // or a number 29 dealWithNumber(pToken); 30 lastToken = NUMBER; 31 } 32 break; 33 case NUMBER: 34 // after a number 35 if (*pToken == ')') 36 { 37 // it may be a right bracket 38 dealWithRightBrac(pToken); 39 lastToken = RIGHT_BRAC; 40 } 41 else 42 { 43 // it may be an operator 44 dealWithOperator(pToken); 45 lastToken = OPERATOR; 46 } 47 break; 48 case OPERATOR: 49 case LEFT_BRAC: 50 // after an operator or a left bracket 51 if (*pToken == '(') 52 { 53 // it may be a left bracket 54 dealWithLeftBrac(pToken); 55 lastToken = LEFT_BRAC; 56 } 57 else 58 { 59 // it may be a number 60 dealWithNumber(pToken); 61 lastToken = NUMBER; 62 } 63 break; 64 case RIGHT_BRAC: 65 // after a right bracket 66 if (*pToken == ')') 67 { 68 // it may be another right bracket 69 dealWithRightBrac(pToken); 70 lastToken = RIGHT_BRAC; 71 } 72 else 73 { 74 // it may be an perator 75 dealWithOperator(pToken); 76 lastToken = OPERATOR; 77 } 78 break; 79 } 80 } 81 82 while (!_stkOperators.empty()) 83 { 84 if (_stkOperators.top() == '(') 85 { 86 throw string("bad token '('"); 87 } 88 calculateStack(); 89 } 90 91 assert(!_stkNodes.empty()); 92 _root = _stkNodes.top(); 93 }

方法實現與棧方法求值的公有方法calculator()基本相同。開始調用的destory()方法繼承自BinaryTree類，用于釋放已占用的二叉樹節點空間，可以防止程序內存溢出。

轉載于:https://www.cnblogs.com/lets-blu/p/7289643.html

總結

以上是生活随笔為你收集整理的表达式求值（二叉树方法/C++语言描述）（二）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。