我正在编写一个使用递归来简化给定表达式的函数。
例如,一个表达式
{AnyOf: ["scope1", "scope2", "scope*"]}
可以简化为
{AnyOf: ["scope*"]}
首先使用实用函数 scopeCompare()
对作用域数组进行排序,然后使用 normalizeScopeSet()
从作用域数组中删除任何重复的存在或不需要的作用域。
我已经编写了一个函数,可以将表达式简化到这个级别:
{AnyOf: ["scope1", "scope2", "scope*"]}
但是,如果我有这样的表达式:
{AnyOf: ["scope1", {AllOf: ["scope2a", "scope2b, "scope2*", "scope3"]}]}
当前功能不起作用。上面的表达式可以简化为:
{AnyOf: ["scope1", {AllOf:["scope2*", "scope3"]}]}
这是我现在的功能:
const { normalizeScopeSet, scopeCompare } = require("./normalize");
exports.simplifyScopeExpression = scopeExpression => {
if (isScope(scopeExpression)) {
return scopeExpression;
} else if (isAnyOf(scopeExpression)) {
return scopeExpression;
} else if (isAllOf(scopeExpression)) {
return scopeExpression;
}
};
const isScope = scopeExpression => {
let exp = scopeExpression;
if (typeof exp === "string") {
return true;
} else if (Object.keys(exp) === "AnyOf") {
isAnyOf(scopeExpression);
}
else if(Object.keys(exp) === 'AllOf'){
isAllOf(scopeExpression);
}
};
const isAnyOf = scopeExpression => {
let exp = scopeExpression;
Object.keys(exp).forEach(item => {
let expression = exp[item].sort(scopeCompare);
exp[item] = normalizeScopeSet(expression);
});
return scopeExpression;
};
const isAllOf = scopeExpression => {
let exp = scopeExpression;
Object.keys(exp).forEach(item => {
let expression = exp[item].sort(scopeCompare);
exp[item] = normalizeScopeSet(expression);
});
return scopeExpression;
};
我想修改此函数,以便在我传递如下表达式时,我得到预期的简化表达式。
{AllOf: [{AllOf: ["scope1", "scope2"]}, {AllOf: ["scope2", "scope3"]}]}
应简化为{AllOf: ["scope1", "scope2", "scope3"]}
。{AllOf: [{AllOf: ["scope1", "scope2"]}, "scope2", "scope3"]}
应该简化为{AllOf: ["scope1", "scope2", "scope3"]}
。{AllOf: ["scope0", {AllOf: ["scope1", {AllOf: ["scope2", {AllOf: ["scope3, {AllOf: ["scope4", "scope5 "]}]}]}]}]}
应该简化为{AllOf: ["scope0", "scope1", "scope2", "scope3", "scope4", "scope5"]}
注意事项:
scopeCompare
函数对作用域进行排序,使得以 * 结尾的作用域排在具有相同前缀的任何其他作用域之前。例如,a* 出现在 a 和 ax 之前。
normalizeScopeSet
函数将规范化范围集。但是,它要求其输入已经使用 scopeCompare 进行了排序。
例如,对范围数组进行排序:
let scope = {AnyOf: ["scope1", "scope2", "scope*"]}
Object.keys(scope).forEach(item => {
let expression = exp[item].sort(scopeCompare);
exp[item] = normalizeScopeSet(expression);
})
给出输出
{AnyOf: ["scope*"]}
最佳答案
这是一个有趣的挑战。我已经设法(我认为)使某些东西起作用,但采用了不同的方法。虽然和你有一些相似之处。
// compress an array of patterns and strings
// remove duplicates *AND* strings matching any patterns
// compress(["scope10", "scope11", "scope11", "scope1*", "scope2", "scope2*", "scope2a"])
// => ["scope1*", "scope2*"]
//
// TODO: patterns could be optimised as well!
const compress = xs =>
Array.of(xs)
.map(xs => xs.filter((x, i, xs) => xs.indexOf(x) === i))
.map(xs =>
xs.reduce(([l, r], x) =>
x.endsWith('*')
? [ l.concat(x.slice(0, -1))
, r
]
: [ l
, r.concat(x)
],
[[], []]))
.map(([l, r]) =>
[ ...l.map(x => x + '*')
, ...r.filter(x => !l.some(y => x.startsWith(y)))
])
.pop();
// flatten expressions that belong to the same "namespace"
// flatten_expression("AllOf", ["scope1", {AllOf: ["scope2", "scope3"]}, {AnyOf: ["scope10*", "scope20*"]}])
//=> ["scope1", "scope2", "scope3", {AnyOf: ["scope10*", "scope20*"]}]
const flatten_expression = (key, exprs) =>
exprs.flatMap(expr =>
typeof expr === 'string' || expr[key] === undefined
? expr
: flatten_expression(key, expr[key]));
// Given an array of expressions
// compress all strings and simplify the rest
// reduce_expression(["scope1", "scope1*", {AnyOf: ["scope22", "scope2*", "scope3"]}])
// => ["scope1*", {AnyOf: ["scope2*", "scope3"]}]
const reduce_expression = xs =>
Array.of(xs)
.map(xs =>
xs.reduce(([l, r], x) =>
typeof x === 'string'
? [ l.concat(x)
, r
]
: [ l
, r.concat(x)
],
[[], []]))
.map(([l, r]) =>
[ ...compress(l)
, ...r.map(simplify_expression)
])
.pop();
// Simplify an entire object of expressions
const simplify_expression = o =>
Array.of(o)
.map(xs => Object.entries(xs))
.map(xs => xs.map(([k, v]) => [k, flatten_expression(k, v)]))
.map(xs => xs.map(([k, v]) => [k, reduce_expression(v)]))
.map(xs => Object.fromEntries(xs))
.pop();
console.log(
simplify_expression({AnyOf: ["scope1", "scope2", "scope*"]})
)
console.log(
simplify_expression({AnyOf: ["scope1", {AllOf: ["scope2a", "scope2b", "scope2*", "scope3"]}]})
)
console.log(
simplify_expression({AllOf: [{AllOf: ["scope1", "scope2"]}, {AllOf: ["scope2", "scope3"]}]})
)
console.log(
simplify_expression({AllOf: [{AllOf: ["scope1", "scope2"]}, "scope2", "scope3"]})
)
console.log(
simplify_expression({AllOf: ["scope0", {AllOf: ["scope1", {AllOf: ["scope2", {AllOf: ["scope3", {AllOf: ["scope4", "scope5"]}]}]}]}]})
)
关于javascript - 用于简化javascript中表达式的递归函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58967090/