神一样的少年就是我
2021-03-06 23:15
采纳率: 50%
浏览 126

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

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

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

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

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

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

5条回答 默认 最新

  • ProfSnail 2021-03-07 14:31
    已采纳

    搞了一整上午,终于搞出来个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)
    }
    
    1 打赏 评论
  • 天际的海浪 2021-03-07 03:09

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

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

    以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)
    1 打赏 评论
  • ProfSnail 2021-03-07 00:06

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

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

    打赏 评论
  • 歇歇 2021-03-07 00:22
    policy.Where(v => attributes.Contains(v.Name))
    打赏 评论
  • ProfSnail 2021-03-07 03:00

    好家伙……

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

    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()
    
    打赏 评论

相关推荐 更多相似问题