怎么判断字符串数组是否匹配访问策略树？

policy:="((student AND CS) OR (teacher AND xidian)) OR male"

attributes := []string{"student", "xidian", "CS", "male"}

如图，policy为包含与或门的访问策略树，attributes是属性集合，如何判断属性是否符合访问控制树呢？有没有相关的算法思想呢？当然有代码就更好了，最好是golang。急，有偿！

很明显在此例中是匹配策略树的。

搞了一整上午，终于搞出来个Go版本的。 

package main

import (
	"fmt"
	"regexp"
)

type node struct {
	option string
	str    string
	left   *node
	right  *node
}

func judgeTrue(root *node, maps map[string]bool) bool {
	if root.option != "" {
		if root.option == "AND" {
			return judgeTrue(root.left, maps) && judgeTrue(root.right, maps)
		} else {
			return judgeTrue(root.left, maps) || judgeTrue(root.right, maps)
		}
	} else {
		_, ok := maps[root.str]
		return ok
	}
}

func buildDecisionTree(policy string) *node {
	ra := `^\((.*)\){1}\s+(AND|OR){1}\s+\((.*)\){1}$`
	rb := `^([^\(\)]*){1}\s+(AND|OR){1}\s+\((.*)\){1}$`
	rc := `^\((.*)\){1}\s+(AND|OR){1}\s+([^\(\)]*){1}$`
	rd := `^([^\(\)]*){1}\s+(AND|OR){1}\s+([^\(\)]*){1}$`
	rlist := []string{ra, rb, rc, rd}
	var i int
	var flag bool = false
	var left, option, right string
	for i = 0; i < 4; i++ {
		regTemp := regexp.MustCompile(rlist[i])
		result := regTemp.FindAllStringSubmatch(policy, -1)
		if len(result) > 0 {
			left = regTemp.ReplaceAllString(policy, "$1")
			option = regTemp.ReplaceAllString(policy, "$2")
			right = regTemp.ReplaceAllString(policy, "$3")
			flag = true
		}
	}
	var root *node = &node{}
	if flag{
		root.left = buildDecisionTree(left)
		root.option = option
		root.right = buildDecisionTree(right)
	}else{
		root.str = policy
	}
	return root
}

func getMaps(inputList []string) map[string]bool{
	var maps map[string]bool = make(map[string]bool)
	for index:=range(inputList){
		maps[ inputList[index] ] = true
	}
	return maps
}

func main() {
	var policy string = "((student AND CS) OR (teacher AND xidian)) OR male"
	root:=buildDecisionTree(policy)
	attributes := []string{"student", "xidian", "CS", "male"}
	maps:=getMaps(attributes)
	ans:=judgeTrue(root, maps)
	fmt.Println(ans)
}

 有一个很巧妙的方法。把策略树字符串用正则替换成当前所用编程语言的逻辑表达式，

然后直接执行这个逻辑表达式。

以python为例：

import re

policy = "((student AND CS) OR (teacher AND xidian)) OR male"
attributes = {"student", "xidian", "CS", "male"}
policy = re.sub(r"\bAND\b","and",policy)
policy = re.sub(r"\bOR\b","or",policy)
policy = re.sub(r"\b(?!(?:and|or)\b)(\w+)\b",r"('\1' in attributes)",policy)
print(policy)
res = eval(policy)
print(res)

我试着写一个策略树的代码。

import re

class node:
    def __init__(self, haha="haha"):
        self.option = ""
        self.str = ""
        self.left = None
        self.right = None

def judgeTrue(root, sets):
    if root.option != "":
        if root.option == "AND":
            return judgeTrue(root.left, sets) and judgeTrue(root.right, sets)
        else:
            return judgeTrue(root.left, sets) or judgeTrue(root.right, sets)
    else:
        return (root.str in sets)

def buildDecisionTree(policy):
    ra = "\((.*)\) (AND|OR) \((.*)\)"
    rb = "\((.*)\)"
    ans = re.findall(ra, policy)
    root = node()
    if len(ans) > 0:
        left, option, right = ans[0]
        root.left = buildDecisionTree(left)
        root.option = option
        root.right = buildDecisionTree(right)
    else:
        root.str = policy
    return root

def main():
    sets = {"student", "xidian", "CS", "male"}
    policy = "(((student) AND (CS)) OR ((teacher) AND (xidian))) OR (male)"
    root = buildDecisionTree(policy)
    answer = judgeTrue(root, sets)
    print(answer)

if __name__ == '__main__':
    main()

刚开始写的时候用C++，发现C++里面的正则表达式返回值跟预期不一样。又推翻了用Python重新写了一遍。

学艺不精，没想明白怎么处理OR male时候怎么处理比较方便，所以一股脑把最小单元也改成了强制性加括号的(male)。

"(((student) AND (CS)) OR ((teacher) AND (xidian))) OR (male)"

policy.Where(v => attributes.Contains(v.Name))

好家伙……

代码改完了，现在不用强制要求每个叶节点都由括号包裹了。

import re

class node:
    def __init__(self, haha="haha"):
        self.option = ""
        self.str = ""
        self.left = None
        self.right = None

def judgeTrue(root, sets):
    if root.option != "":
        if root.option == "AND":
            return judgeTrue(root.left, sets) and judgeTrue(root.right, sets)
        else:
            return judgeTrue(root.left, sets) or judgeTrue(root.right, sets)
    else:
        return (root.str in sets)

def buildDecisionTree(policy):
    ra = r"^\((.*)\){1} (AND|OR){1} \((.*)\){1}$"
    rb = r"^([^\(\)]*){1} (AND|OR){1} \((.*)\){1}$"
    rc = r"^\((.*)\){1} (AND|OR){1} ([^\(\)]*){1}$"
    rd = r"^([^\(\)]*){1} (AND|OR){1} ([^\(\)]*){1}$"
    rlist = [ra, rb, rc, rd]
    ans = []
    for r in rlist:
        tempAns = re.findall(r, policy)
        if(len(tempAns) > 0):
            ans = tempAns
    root = node()
    if len(ans) > 0:
        left, option, right = ans[0]
        root.left = buildDecisionTree(left)
        root.option = option
        root.right = buildDecisionTree(right)
    else:
        root.str = policy
    return root

def main():
    sets = {"student", "xidian", "CS", "male"}
    policy = "((student AND CS) OR (teacher AND xidian)) OR male"
    root = buildDecisionTree(policy)
    answer = judgeTrue(root, sets)
    print(answer)

if __name__ == '__main__':
    main()