摘要：代碼實(shí)現(xiàn)測(cè)試代碼輸出解析標(biāo)簽表達(dá)式基礎(chǔ)的表達(dá)式解析實(shí)現(xiàn)了，針對(duì)我們的標(biāo)簽表達(dá)式多個(gè)字符組成一個(gè)標(biāo)簽，以及去掉，加上的邏輯，稍作修改測(cè)試代碼輸出后綴表達(dá)式轉(zhuǎn)二叉樹分析根據(jù)后綴表達(dá)式的含義，符合表示前面兩個(gè)元素的運(yùn)算。用戶標(biāo)簽是個(gè)數(shù)組。

標(biāo)簽是精細(xì)化運(yùn)營(yíng)必不可少的工具，常見(jiàn)的使用場(chǎng)景有標(biāo)簽推送，千人千面的廣告展示等。在實(shí)際的業(yè)務(wù)中，標(biāo)簽往往是通過(guò)交并差非運(yùn)算組合在一起使用，比如：標(biāo)簽組合是 A ∪ B ∩ C，需要判斷用戶在不在這個(gè)集合中。

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

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

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

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

首先，從需求可以得出廣告展示的標(biāo)簽表達(dá)式：

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

為了方便表示「交并差非」所有運(yùn)算，將「交并差非」分別用「*+-!」表示，其中運(yùn)算沒(méi)有優(yōu)先級(jí)區(qū)別，于是上面的表達(dá)式可以寫成：

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

分析：一個(gè)用戶包含多個(gè)標(biāo)簽，判斷「一個(gè)用戶」是否存在「一個(gè)標(biāo)簽運(yùn)算的集合」中，從而來(lái)展示廣告，其核心就是：判斷一個(gè)并集集合與另一個(gè)(多個(gè)運(yùn)算的)集合的交集關(guān)系。

結(jié)合「交并差非」的含義，以及(除了「!」)符號(hào)左右結(jié)合運(yùn)算的原理，可以明確符號(hào)連接左右兩個(gè)的標(biāo)簽(表達(dá)式)的含義：

由「+」連接的兩個(gè)標(biāo)簽(表達(dá)式)是或的關(guān)系，只要有一個(gè)與用戶的標(biāo)簽有交集即為true。

由「*」鏈接的兩個(gè)標(biāo)簽(表達(dá)式)是交的關(guān)系，左右兩個(gè)都與用戶的標(biāo)簽有交集才為true。

由「-」鏈接的兩個(gè)標(biāo)簽(表達(dá)式)是交的關(guān)系，左邊與用戶的標(biāo)簽有交集且右邊與用戶的標(biāo)簽沒(méi)有交集，才為true。

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

理清楚含義以后，可以看出只要用遞歸的方式對(duì)其左右運(yùn)算，就可以得到「用戶是否在標(biāo)簽表達(dá)式」集合里的結(jié)果。左右運(yùn)算的一個(gè)很合適的數(shù)據(jù)結(jié)構(gòu)就是二叉樹，大致思路就是：

將表達(dá)式轉(zhuǎn)成二叉樹

遞歸二叉樹判斷

關(guān)于表達(dá)式的解析，與基本的四則運(yùn)算表達(dá)式解析基本一致，只不過(guò)我們的含義不一樣，以及沒(méi)有符號(hào)的優(yōu)先級(jí)區(qū)別。

中綴表達(dá)式就是常說(shuō)的算數(shù)表達(dá)式，比如：1+2*3/(2+1)。后綴表達(dá)式（也叫逆波蘭表示法）就是運(yùn)算符在運(yùn)算數(shù)之后的表達(dá)式，比如上述的表達(dá)式寫成：12321+/*+。也可是實(shí)現(xiàn)去掉括號(hào)的作用。轉(zhuǎn)化過(guò)程，會(huì)用到棧去保存運(yùn)算符號(hào)。

轉(zhuǎn)化過(guò)程

可以看出轉(zhuǎn)化規(guī)則是，按順序讀取字符：

遇到操作數(shù)，寫入output。

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

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

循環(huán)讀取結(jié)束后，將操作符棧逐個(gè)彈出拼在output后即可。

代碼實(shí)現(xiàn)(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);
}

//測(cè)試代碼
$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] => *
)

解析標(biāo)簽表達(dá)式

基礎(chǔ)的表達(dá)式解析實(shí)現(xiàn)了，針對(duì)我們的標(biāo)簽表達(dá)式(多個(gè)字符組成一個(gè)標(biāo)簽)，以及去掉「/」，加上「!」的邏輯，稍作修改：

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);
}

//測(cè)試代碼
$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] => *
)

分析：根據(jù)后綴表達(dá)式的含義，符合表示前面兩個(gè)元素的運(yùn)算。因此在遍歷時(shí)，可以利用一個(gè)棧去暫存標(biāo)簽表達(dá)式，當(dāng)遍歷到符號(hào)，就彈出兩個(gè)標(biāo)簽作為其運(yùn)算的左右元素，形成一個(gè)新的節(jié)點(diǎn)放回到棧中，如此循環(huán)就能形成一個(gè)完整的二叉樹。

//轉(zhuǎn)后綴表達(dá)式的方法
...


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


//后綴表達(dá)式數(shù)組轉(zhuǎn)成二叉樹
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;
}


//測(cè)試代碼
$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] =>
        )

)

回顧一下符號(hào)的含義：

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

說(shuō)明：

這里函數(shù)傳入?yún)?shù)設(shè)計(jì)為「用戶標(biāo)簽」和上一步構(gòu)成的「樹」。

「用戶標(biāo)簽」是個(gè)數(shù)組。

判斷邏輯先簡(jiǎn)單判斷是否存在于「用戶標(biāo)簽」數(shù)組中。

實(shí)現(xiàn)

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

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;
}

//測(cè)試代碼
//$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)

在實(shí)際的業(yè)務(wù)中，標(biāo)簽組合會(huì)更加復(fù)雜。除了「標(biāo)簽」與「標(biāo)簽」組合，還可會(huì)有「標(biāo)簽」與「標(biāo)簽組」，「用戶標(biāo)簽」與「設(shè)備標(biāo)簽」。下面談?wù)勥@些需求如何支持。

標(biāo)簽組實(shí)質(zhì)也是通過(guò)標(biāo)簽的運(yùn)算組合在一起，舉個(gè)例子：
標(biāo)簽組1：Atag1+Atag2*Atag3
標(biāo)簽組2：Btag4-[標(biāo)簽組1]
結(jié)果：Btag4-(Atag1+Atag2*Atag3)

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

除了「判斷標(biāo)簽組是否包含用戶」這個(gè)需求，還有另外一個(gè)需求也很常用：「判斷標(biāo)簽表達(dá)式包含多少用戶」，這個(gè)需求除了邏輯還涉及到數(shù)據(jù)庫(kù)的設(shè)計(jì)，實(shí)現(xiàn)方案跟實(shí)際場(chǎng)景也有關(guān)系，就不在這里討論啦。

以上的代碼段為縮減版，可能存在問(wèn)題哈，如有錯(cuò)漏望指正。