四则运算和二叉树-创新互联

前几天忽然想到了四则运算和二树有没有关系,然后在网络上检索了一下,发现还真的有四则运算和二叉树。因为总是见到把 四则运算表达式 用 树 的形式来展示,所以就想着给定一颗表达式树,计算它的结果出来。

成都创新互联公司专注为客户提供全方位的互联网综合服务,包含不限于成都网站制作、成都做网站、怀宁网络推广、成都小程序开发、怀宁网络营销、怀宁企业策划、怀宁品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们大的嘉奖;成都创新互联公司为所有大学生创业者提供怀宁建站搭建服务,24小时服务热线:18980820575,官方网址:www.cdcxhl.com

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

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

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

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


文章题目:四则运算和二叉树-创新互联
网页网址:http://myzitong.com/article/degghs.html