C#-二叉树表达式计算

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

很早以前就写过双栈的表达式计算.

这次因为想深入学一下二叉树,网上都是些老掉牙的关于二叉树的基本操作.

感觉如果就学那些概念,没意思也不好记忆.于是动手写了一个表达式计算的应用例子.

这样学习印象才深嘛.

我喜欢逆过来贴代码~

这是运行结果:

cal() 是节点类里的计算方法,从根节点调用,递归所有子节点进行计算.Left,Right分别是左右子节点.

1      public double cal()
2         {
3             if (this.isDig==false)
4             {
5                 return CAL(Fuhao, Left.cal() , Right.cal() );
6             }
7             return value;
8         }

下面的CAL(大写)的是静态的计算方法,根据不同符号进行不同计算.

 1  public static double CAL(int FUHAO, double l, double r)
 2         {
 3             switch (FUHAO)
 4             {
 5                 case ADD:
 6                     return l + r;
 7                 case SUB:
 8                     return l - r;
 9                 case MUL:
10                     return l * r;
11                 case DIV:
12                     return l / r;
13             }
14             return 0;
15         }

看到这,是不是觉得很简单呢?

没错,二叉树在计算表达式时非常简单,但难点在于如何构建这个表达式树.

写程序最重要的就是严谨强大的逻辑思维能力.

在写下面的方法时,我经历了很多次debug.大概修改了10次,才完成..可见我的逻辑能力还是很不足.

下面这个方法包含大量逻辑判断,可能不好理解,也许某些判断可以简化优化,而且我默认第一位是数字,也就是不支持第一位是括号的表达式.

 1     public static BNode CreateTree(List<string> zf)
 2         {
 3             var fh=new List<string>{"+","-","*","/"};
 4             var kh = new List<string> { "(", ")" };
 5            BNode CurN=null;
 6            BNode TempCur = null;
 7             foreach (var a in zf)
 8             {
 9                 if (fh.Contains(a))
10                 {//是符号
11                     int tfuhao=fh.IndexOf(a);       //偷懒写法,取得符号值,0-3分别代表+-*/
12                     int tfhvalue=tfuhao/2;          //符号优先值,+-为0.*/为1,判断符号优先,这里写的很偷懒
13                     if (CurN.Parent != null)
14                     {
15                         if (CurN.Parent.FuhaoValue < tfhvalue) 
16                             //当前节点的父节点符号<新节点符号,即新加的符号优先级比较高.
17                         {
18                             var tp = CurN.Parent;
19                             var t = CurN;
20                             CurN = new BNode { Parent=tp,Left=t , isDig = false,  Fuhao = tfuhao,FuhaoValue=tfhvalue };
21                             tp.Right = CurN;
22                             t.Parent = CurN;
23                         }
24                         else if (CurN.Parent.FuhaoValue >= tfhvalue)
25                             //新加的符号优先级不高于当前节点的父节点符号,
26                         {
27                             BNode tp = CurN;
28                             while (tp.isKuoHao || tp.isDig  ||  tp.FuhaoValue != tfhvalue)
29                               //循环取得与新加节点优先级相同的节点.
30                             {
31                                 if (tp.Parent != null)
32                                     tp = tp.Parent;
33                                 else
34                                     break;
35                             }
36                             if (tp.Parent == null)
37                             {
38                                 CurN = new BNode {  Left = tp, isDig = false, Fuhao = tfuhao, FuhaoValue = tfhvalue };
39                                 tp.Parent = CurN;
40                             }
41                             else
42                             {
43                                 var p = tp.Parent;
44                                 CurN = new BNode { Parent = p, Left = tp, isDig = false, Fuhao = tfuhao, FuhaoValue = tfhvalue };
45                                 p.Right = CurN;
46                                 tp.Parent = CurN;
47                             }
48                         }
49                     }
50                     else
51                     {
52                         var t = CurN;
53                         CurN = new BNode { isDig = false, Fuhao = tfuhao, FuhaoValue = tfhvalue, Left = CurN };
54                         t.Parent = CurN;
55                     }
56                    
57                 }
58                 else if (kh.Contains(a))
59                 {//是括号
60                     if (a == "(")
61                     {
62                         TempCur = CurN;
63                         CurN = null;
64                     }
65                     else if (a == ")")
66                     {
67                        var top= CurN.GetTop();
68                        top.Parent = TempCur;
69                        TempCur.Right = top;
70                        CurN = top;
71                        CurN.isKuoHao = true;
72                     }
73                 }
74                 else
75                 {//是数字
76                     if (CurN == null)
77                         CurN = new BNode { value = double.Parse(a) };
78                     else if (CurN.isDig == false)
79                     {
80                         var t= CurN;
81                         CurN = new BNode { value = double.Parse(a), Parent=t };
82                         t.Right = CurN;
83                     }
84                 }
85             }
86 
87             return CurN;
88         }

其实写起来也没什么太大难度,只要把所有情况的处理都考虑到就行.

最后是2个辅助函数.

FenGe:我比较偷懒,事先把字符串里的数字和符号分隔开了,这样就不用一位一位的去取判断是数字或者符号.

Cal:使用时唯一需要接触的函数.

 1    public static double Cal(string expresstion)
 2         {
 3            var a= FenGe(expresstion);
 4            var zfs = a.Split('|' ,StringSplitOptions.RemoveEmptyEntries);
 5           var t= BNode.CreateTree(zfs.ToList());
 6           var root= t.GetTop();
 7           var result = root.cal();
 8             return result;
 9         }
10 
11         public static string FenGe(string exp)
12         {
13             var ys = new List<string> { "\\d*\\.?\\d+", "[+\\-\\*/\\(\\)]{1}" };
14             ys.ForEach(a =>
15             {
16                 var r = new Regex(a);
17                exp= r.Replace(exp, b => b.Value + "|", int.MaxValue);
18             });
19             return exp;
20         }

1 　　public BNode GetTop()
2         {
3             if (Parent != null)
4                 return Parent.GetTop();
5             return this;
6         }