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

这篇文章主要浅谈一下四则运算和二叉树,因为总是见到把四则运算表达式用树的形式来展示，所以就想着给定一颗表达式树，计算它的结果出来,需要的朋友可以参考下

引言

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

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

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

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()

输出结果：

在这里插入图片描述