淺談一下四則運算和二叉樹

更新時間：2023年04月06日 09:45:36 作者：CrazyDragon_King

這篇文章主要淺談一下四則運算和二叉樹,因為總是見到把?四則運算表達式?用?樹?的形式來展示，所以就想著給定一顆表達式樹，計算它的結(jié)果出來,需要的朋友可以參考下

引言

前幾天忽然想到了四則運算和二樹有沒有關(guān)系，然后在網(wǎng)絡(luò)上檢索了一下，發(fā)現(xiàn)還真的有四則運算和二叉樹。

因為總是見到把 四則運算表達式 用樹的形式來展示，所以就想著給定一顆表達式樹，計算它的結(jié)果出來。

這里是我待會會用到的三顆表達式樹，下面是它的表達式：

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

這里我設(shè)計一個簡單的數(shù)據(jù)結(jié)構(gòu)，一個普通的節(jié)點如下：

一個 root 節(jié)點，表示樹的根。然后是下面的子節(jié)點。kind 的類型為 INT、ADD、MIN、MUL 和 DIV。即整數(shù)、+、-、* 和 /。然后是 value，它只有在 kind 為 INT 時有意義。然后是 left 和 right，左右子節(jié)點，如果有的話，就一直這樣遞歸表示下去。

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

輸出結(jié)果：

在這里插入圖片描述