浅谈一下四则运算和二叉树

引言

前几天忽然想到了四则运算和二树有没有关系，然后在网络上检索了一下，发现还真的有四则运算和二叉树。

因为总是见到把 四则运算表达式 用 树 的形式来展示，所以就想着给定一颗表达式树，计算它的结果出来。

这里是我待会会用到的三颗表达式树，下面是它的表达式：

1
1+2
(6/2)+(2*(9-10)

这里我设计一个简单的数据结构，一个普通的节点如下：

一个 root 节点，表示树的根。然后是下面的子节点。kind 的类型为 INT、ADD、MIN、MUL 和 DIV。即整数、+、-、* 和 /。然后是 value，它只有在 kind 为 INT 时有意义。然后是 left 和 right，左右子节点，如果有的话，就一直这样递归表示下去。

{
   "root": {
       "kind": "INT",
       "value": 1
   }
},
{
   "root": {
       "kind": "ADD",
       "value": "+",
       "left": {
           "kind": "INT",
           "value": 1
       },
       "right": {
           "kind": "INT",
           "value": 2
       }
   }
},

from typing import Dict, Union

def computer(tree: Dict[str, Union[str, int, Dict[str, int]]]) -> int:
   if not tree:
       return 0
   kind = tree.get("kind")
   value = tree.get("value")

print(f"{kind} ==> {value}")

if kind == 'INT':
       return value  # type: ignore
   left_val = computer(tree.get("left"))  # type: ignore
   right_val = computer(tree.get("right"))  # type: ignore

if kind == 'ADD':
       return left_val + right_val
   elif kind == 'MIN':
       return left_val - right_val
   elif kind == 'MUL':
       return left_val * right_val
   elif kind == 'DIV':
       return left_val // right_val
   else:
       print(type)
       raise Exception("unexcepted operator")

if __name__ == "__main__":
   # 测试的树
   test_trees = [
       {
           "root": {
               "kind": "INT",
               "value": 1
           }
       },
       {
           "root": {
               "kind": "ADD",
               "value": "+",
               "left": {
                   "kind": "INT",
                   "value": 1
               },
               "right": {
                   "kind": "INT",
                   "value": 2
               }
           }
       },
       {
           "root": {
               "kind": "ADD",
               "value": "+",
               "left": {
                   "kind": "DIV",
                   "value": "/",
                   "left": {
                       "kind": "INT",
                       "value": 6
                   },
                   "right": {
                       "kind": "INT",
                       "value": 2
                   }
               },
               "right": {
                   "kind": "MUL",
                   "value": "*",
                   "left": {
                       "kind": "INT",
                       "value": 2
                   },
                   "right": {
                       "kind": "MIN",
                       "value": "-",
                       "left": {
                           "kind": "INT",
                           "value": 9
                       },
                       "right": {
                           "kind": "INT",
                           "value": 10
                       }
                   }
               }
           }
       }
   ]

# 计算
   for test_tree in test_trees:
       print(computer(test_tree["root"]))
       print()

输出结果：

这里只是简单的尝试一下，计算基本是没有问题的。问题的关键在于把表达式转成树的结构，我还没有想好怎么处理，所以我就把后半部分写出来了。

来源：https://blog.csdn.net/qq_40734247/article/details/128107562