深圳网站建设提供服务公司,阿里巴巴网站建设教程,wordpress 删除emjo,WordPress用quic协议表达式二叉树节点的数据可能是运算数或运算符#xff0c;可以使用一个联合体进行存储#xff1b;同时还需要一个变量来指示存储的是运算数还是运算符#xff0c;可以采用和栈方法求值中一样的枚举类型TokenType#xff1a; 1 typedef enum2 {3 BEGIN,4 NUMBER,5 … 表达式二叉树节点的数据可能是运算数或运算符可以使用一个联合体进行存储同时还需要一个变量来指示存储的是运算数还是运算符可以采用和栈方法求值中一样的枚举类型TokenType 1 typedef enum2 {3 BEGIN,4 NUMBER,5 OPERATOR,6 LEFT_BRAC,7 RIGHT_BRAC8 } 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 BinaryTreeToken2 {3 public:4 void parseExpression(string expression) throw(string);5 double calculate();6 7 private:8 stackchar _stkOperators;9 stackBinaryTreeNodeToken * _stkNodes;
10 stackdouble _stkNumbers;
11
12 static int priority(char op);
13 static double calculate(double d1, char op, double d2) throw(string);
14
15 void postOrder(BinaryTreeNodeToken * 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类为友元类。 转换过程与栈方法求值的运算压栈过程基本相同当遇到运算数时生成一个新的节点并将它的指针压入节点指针栈中遇到运算符时比较当前运算符和运算符栈栈顶运算符的优先级若运算符栈栈顶运算符的优先级较高则为它生成一个新的节点并从节点指针栈中弹出两个节点指针作为新节点的左子树和右子树随后将这个新节点的指针压入节点指针栈中将当前运算符压入运算符栈中否则只将当前运算符压入运算符栈中。最后反复执行上述过程直至运算符栈为空节点指针栈的栈顶元素即为指向树根节点的指针。表达式“12*3”和“1*23”的转换过程如下图 使用代码描述操作节点指针栈的过程 1 void Calculator::calculateStack() throw(string)2 {3 BinaryTreeNodeToken * node new BinaryTreeNodeToken();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
