摘要：代碼實現測試代碼輸出解析標簽表達式基礎的表達式解析實現了，針對我們的標簽表達式多個字符組成一個標簽，以及去掉，加上的邏輯，稍作修改測試代碼輸出后綴表達式轉二叉樹分析根據后綴表達式的含義，符合表示前面兩個元素的運算。用戶標簽是個數組。

標簽是精細化運營必不可少的工具，常見的使用場景有標簽推送，千人千面的廣告展示等。在實際的業務中，標簽往往是通過交并差非運算組合在一起使用，比如：標簽組合是 A ∪ B ∩ C，需要判斷用戶在不在這個集合中。

以千人千面展示廣告為例，我們會有這樣的需求：

(美甲師或者美甲店主)且參與了開店計劃的廣州用戶展示A廣告。

(美甲師或者美甲店主)且參與了開店計劃的深圳用戶展示B廣告。

標簽說明：這里的標簽都是用戶標簽，英文標簽：美甲師( identity_1)、美甲店主( identity_2)、參與了開店計劃( shop_setup_user)、廣州( guangzhou)、深圳( shenzhen)。

首先，從需求可以得出廣告展示的標簽表達式：

A 廣告： (identity_1 ∪ identity_2) ∩ shop_setup_user ∩ guangzhou
B 廣告： (identity_1 ∪ identity_2) ∩ shop_setup_user ∩ shenzhen

為了方便表示「交并差非」所有運算，將「交并差非」分別用「*+-!」表示，其中運算沒有優先級區別，于是上面的表達式可以寫成：

A 廣告： (identity_1+identity_2)*shop_setup_user*guangzhou
B 廣告： (identity_1+identity_2)*shop_setup_user*shenzhen

分析：一個用戶包含多個標簽，判斷「一個用戶」是否存在「一個標簽運算的集合」中，從而來展示廣告，其核心就是：判斷一個并集集合與另一個(多個運算的)集合的交集關系。

結合「交并差非」的含義，以及(除了「!」)符號左右結合運算的原理，可以明確符號連接左右兩個的標簽(表達式)的含義：

由「+」連接的兩個標簽(表達式)是或的關系，只要有一個與用戶的標簽有交集即為true。

由「*」鏈接的兩個標簽(表達式)是交的關系，左右兩個都與用戶的標簽有交集才為true。

由「-」鏈接的兩個標簽(表達式)是交的關系，左邊與用戶的標簽有交集且右邊與用戶的標簽沒有交集，才為true。

「!」比較特殊，它是使得其后跟著的標簽(表達式)相反。

理清楚含義以后，可以看出只要用遞歸的方式對其左右運算，就可以得到「用戶是否在標簽表達式」集合里的結果。左右運算的一個很合適的數據結構就是二叉樹，大致思路就是：

將表達式轉成二叉樹

遞歸二叉樹判斷

關于表達式的解析，與基本的四則運算表達式解析基本一致，只不過我們的含義不一樣，以及沒有符號的優先級區別。

中綴表達式就是常說的算數表達式，比如：1+2*3/(2+1)。后綴表達式（也叫逆波蘭表示法）就是運算符在運算數之后的表達式，比如上述的表達式寫成：12321+/*+。也可是實現去掉括號的作用。轉化過程，會用到棧去保存運算符號。

轉化過程

可以看出轉化規則是，按順序讀取字符：

遇到操作數，寫入output。

遇到(+-*/，寫入操作符棧中。

遇到)，從非空的操作符棧，中彈出一項；若項不為(，則寫至輸出，若項為(，則退出循環。

循環讀取結束后，將操作符棧逐個彈出拼在output后即可。

代碼實現(PHP)

function expressionToSuffixExpressionArray($expression)
{
    $charArray = array_reverse(str_split($expression));
    $operationArray = [];
    $output = [];

    while (($c = array_pop($charArray)) != "") {
        if (in_array($c, ["(", "+", "-", "*", "/"])) {
            array_push($operationArray, $c);
        } elseif (in_array($c, [")"])) {
            while ($op = array_pop($operationArray)) {
                if ($op == "(") {
                    break;
                }
                array_push($output, $op);
            }
        } else {
            array_push($output, $c);
        }
    }

    return array_merge($output, $operationArray);
}

//測試代碼
$expression = "3*(2+1)";
$result = expressionToSuffixExpressionArray($expression);

echo "expression: {$expression}" . PHP_EOL;
print_r($result);

輸出：

expression: 3*(2+1)
Array
(
    [0] => 3
    [1] => 2
    [2] => 1
    [3] => +
    [4] => *
)

解析標簽表達式

基礎的表達式解析實現了，針對我們的標簽表達式(多個字符組成一個標簽)，以及去掉「/」，加上「!」的邏輯，稍作修改：

function expressionToSuffixExpressionArray($expression)
{
    $charArray = array_reverse(str_split($expression));
    $operationArray = [];
    $output = [];

    $expression = "";
    while (($c = array_pop($charArray)) != "") {
        if (in_array($c, ["(", "+", "-", "*"])) {
            if (!empty($expression)) {
                array_push($output, $expression);
                $expression = "";
            }
            array_push($operationArray, $c);
        } elseif (in_array($c, [")"])) {
            if (!empty($expression)) {
                array_push($output, $expression);
                $expression = "";
            }
            while ($op = array_pop($operationArray)) {
                if ($op == "(") {
                    break;
                }
                array_push($output, $op);
            }
        } elseif (in_array($c, ["!"])) {
            if (!empty($expression)) {
                array_push($output, $expression);
                $expression = "";
            }
            array_push($output, $c);
        } else {
            $expression .= $c;
        }
    }

    return array_merge($output, $operationArray);
}

//測試代碼
$expression = "(identity_1+identity_2)*shop_setup_user*guangzhou";
$result = expressionToSuffixExpressionArray($expression);

echo "expression: {$expression}" . PHP_EOL;
print_r($result);

輸出：

expression: (identity_1+identity_2)*shop_setup_user*guangzhou
Array
(
    [0] => identity_1
    [1] => identity_2
    [2] => +
    [3] => shop_setup_user
    [4] => guangzhou
    [5] => *
    [6] => *
)

分析：根據后綴表達式的含義，符合表示前面兩個元素的運算。因此在遍歷時，可以利用一個棧去暫存標簽表達式，當遍歷到符號，就彈出兩個標簽作為其運算的左右元素，形成一個新的節點放回到棧中，如此循環就能形成一個完整的二叉樹。

//轉后綴表達式的方法
...


//基礎節點
class TreeNode
{
    public static function create(string $root = "")
    {
        return [
            "root" => $root,
            "left" => "",
            "right" => "",
            "opposite" => false,
        ];
    }
}


//后綴表達式數組轉成二叉樹
function suffixExpressionArrayToBinaryTree($suffixExpressionArray)
{
    $stack = [];
    $suffixExpressionArray = array_reverse($suffixExpressionArray);

    while ($item = array_pop($suffixExpressionArray)) {
        if (in_array($item, ["+", "-", "*"])) {
            $node = TreeNode::create($item);
            $node["right"] = array_pop($stack);
            $left = array_pop($stack);
            if ($left["root"] == "!") {
                $node["right"]["opposite"] = true;
                $node["left"] = array_pop($stack);
            } else {
                $node["left"] = $left;
            }

            array_push($stack, $node);
        } else {
            array_push($stack, TreeNode::create($item));
        }
    }

    return $stack;
}


//測試代碼
$expression = "(identity_1+identity_2)*shop_setup_user*guangzhou";
$result = expressionToSuffixExpressionArray($expression);

echo "expression: {$expression}" . PHP_EOL;
print_r($result);

$tree = suffixExpressionArrayToBinaryTree($result);
print_r($tree);

輸出：

Array
(
    [0] => Array
        (
            [root] => *
            [left] => Array
                (
                    [root] => +
                    [left] => Array
                        (
                            [root] => identity_1
                            [left] =>
                            [right] =>
                            [opposite] =>
                        )

                    [right] => Array
                        (
                            [root] => identity_2
                            [left] =>
                            [right] =>
                            [opposite] =>
                        )

                    [opposite] =>
                )

            [right] => Array
                (
                    [root] => *
                    [left] => Array
                        (
                            [root] => shop_setup_user
                            [left] =>
                            [right] =>
                            [opposite] =>
                        )

                    [right] => Array
                        (
                            [root] => guangzhou
                            [left] =>
                            [right] =>
                            [opposite] =>
                        )

                    [opposite] =>
                )

            [opposite] =>
        )

)

回顧一下符號的含義：

由「+」連接的兩個標簽(表達式)是或的關系，只要有一個與用戶的標簽有交集即為true。
由「*」鏈接的兩個標簽(表達式)是交的關系，左右兩個都與用戶的標簽有交集才為true。
由「-」鏈接的兩個標簽(表達式)是交的關系，左邊與用戶的標簽有交集且右邊與用戶的標簽沒有交集，才為true。
「!」比較特殊，它是使得其后跟著的標簽(表達式)相反。

說明：

這里函數傳入參數設計為「用戶標簽」和上一步構成的「樹」。

「用戶標簽」是個數組。

判斷邏輯先簡單判斷是否存在于「用戶標簽」數組中。

實現

//接上面的代碼
//...

function isContained(array $userTags, array $rootNode): bool
{
    $result = false;
    if (in_array($rootNode["root"], ["+", "-", "*"])) {
        switch ($rootNode["root"]) {
            case "+":
                $result = (isContained($userTags, $rootNode["left"]) || isContained(
                        $userTags,
                        $rootNode["right"]
                    ));
                break;
            case "-":
                $result = ((isContained(
                            $userTags,
                            $rootNode["left"]
                        ) === true) && (isContained(
                            $userTags,
                            $rootNode["right"]
                        ) === false));
                break;
            case "*":
                $result = (isContained($userTags, $rootNode["left"]) && isContained(
                        $userTags,
                        $rootNode["right"]
                    ));
                break;
        }
    } else {
        $result = in_array($rootNode["root"], $userTags);
    }

    if ($rootNode["opposite"]) {
        $result = !$result;
    }

    return $result;
}

//測試代碼
//$tree 是上一步的tree
$userTags1 = ["tag1", "tag2", "identity_1", "guangzhou", "shop_setup_user"];
$result1 = isContained($userTags1, $tree[0]);

$userTags2 = ["tag1", "tag2", "identity_2", "shop_setup_user"];
$result2 = isContained($userTags2, $tree[0]);

$userTags3 = ["tag1", "tag2", "identity_3", "guangzhou", "shop_setup_user"];
$result3 = isContained($userTags3, $tree[0]);

var_dump($result1, $result2, $result3);

輸出：

bool(true)
bool(false)
bool(false)

在實際的業務中，標簽組合會更加復雜。除了「標簽」與「標簽」組合，還可會有「標簽」與「標簽組」，「用戶標簽」與「設備標簽」。下面談談這些需求如何支持。

標簽組實質也是通過標簽的運算組合在一起，舉個例子：
標簽組1：Atag1+Atag2*Atag3
標簽組2：Btag4-[標簽組1]
結果：Btag4-(Atag1+Atag2*Atag3)

假如有用戶標簽與設備標簽組合，目前沒做過這樣的需求哈，如果要做可以考慮isContained的參數用一個「包含用戶標簽數組和設備標簽數組的對象」代替數組，然后標簽表達式中的標簽帶上前綴：用戶標簽(u|)、設備標簽(d|)。
舉個例子：
標簽表達式：(u|identity_1+u|identity_2)*u|shop_setup_user*d|guangzhou
判斷時，根據前綴來選擇使用用戶標簽還是設備標簽做判斷。

除了「判斷標簽組是否包含用戶」這個需求，還有另外一個需求也很常用：「判斷標簽表達式包含多少用戶」，這個需求除了邏輯還涉及到數據庫的設計，實現方案跟實際場景也有關系，就不在這里討論啦。

以上的代碼段為縮減版，可能存在問題哈，如有錯漏望指正。