# 揭榜题目
# 01--递归与抽象源码语法树源码AST
# 什么是AST
抽象语法树（abstract syntax tree或者缩写为AST），或者语法树（syntax tree），是源代码的抽象语法结构的树形表示。它以树形的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。
本质就是数据结构与源码的一种映射结构！
# 要求
- 实现一个交互界面如下（页面样例图）
- 点击事件（1）当点击添加条件规则后，在界面上添加一个条件渲染模版
- 点击事件（2）当点击添加条件后，可通过对dialog的输入，生成一个条件规则，并添加到界面上
- 点击事件（3）当点击添加动作规则后，在界面上添加一个动作渲染模版
- 点击事件（4）当点击新增分支后，添加一个或者如果模版到界面上
- 点击事件（5）当点击保存后，将数据结构保存为一个字符串并输出到控制台
- 注意，添加动作中允许添加嵌套IF(递归)进入界面
# 核心
该案例核心是包含有两部分
如何实现一个递归组件？=> 借助框架(不建议手写，很麻烦)
AST如何设计？
以下是参考
[
{
"type": "if",
"conditions": [
{
"left": {
"libId": 1,
"varName": "a"
},
"operator": ">",
"right": {
"libId": 2,
"varName": "b"
}
},
{
"left": {},
"operator": "&&",
"right": {
"varName": "",
"libId": ""
}
},
{
"left": {
"varName": "a",
"libId": "7"
},
"operator": "!=",
"right": {
"varName": "a",
"libId": "7"
}
}
],
"body": [
{
"type": "calculate",
"received": {
"libId": "9",
"varName": "a"
},
"calculate": {
"left": {
"libId": "7",
"varName": "a"
},
"operator": "+",
"right": {
"libId": "7",
"varName": "a"
}
}
},
{
"type": "print",
"received": {
"libId": "7",
"varName": "a"
},
"calculate": {
"left": {},
"operator": "",
"right": {}
}
},
{
"type": "if",
"conditions": [],
"body": []
}
]
},
{
"type": "else if",
"conditions": [],
"body": []
},
{
"type": "else",
"body": []
}
]
解释一下，type字段用于判断if/else if/else 分支。body字段用于存储if/else if/else 分支的代码块。 condition字段用于存储判断条件，left为左值，operator为运算符，right为右值。left和right字段中libId代表该变量来自哪个库，varName代表该变量名。
上述代码将会映射为以下字符串
"if(#1#a#>#2#b#&#a#!=#7#a#){#9#a#=#7#a#+#7#a#;$#7#a#$;if(){}}else if(){}else{}"
解释一下，对于一个变量，需要通过#libId#varName#将其包裹起来。对于输出语句，需要使用$“输出内容”$将其包裹起来。
# 算法
这里给出了数据结构到字符串的映射代码和字符串到数据结构的代码。
// 数据结构转为字符串
export function mapStructureToString(structure) {
if (!Array.isArray(structure)) {
return "";
}
function mapConditionToString(condition) {
if (!condition || typeof condition !== "object") {
return "";
}
const left = (condition.left && condition.left.libId)
? `#${condition.left.libId}#${condition.left.varName || ""}#`
: "";
const operator = condition.operator || "";
const right = (condition.right && condition.right.libId)
? `#${condition.right.libId}#${condition.right.varName || ""}#`
: "";
return `${left}${operator}${right}`;
}
function mapBodyToString(body) {
if (!Array.isArray(body)) {
return "";
}
return body
.map((item) => {
if (item.type === "if" || item.type === "else if") {
const conditions = item.conditions
.map(mapConditionToString)
.join("")
const nestedBody = mapBodyToString(item.body);
return `${item.type}(${conditions}){${nestedBody}}`;
} else if (item.type === 'while') {
const conditions = item.conditions
.map(mapConditionToString)
.join("")
const nestedBody = mapBodyToString(item.body);
return `${item.type}(${conditions}){${nestedBody}}`;
} else if (item.type === "else") {
return `${item.type}{${mapBodyToString(item.body)}}`;
} else if (item.type === "calculate") {
const received = `#${item.received.libId}#${item.received.varName}#`;
const addStr = mapConditionToString(item.calculate)
return `#${received}=${addStr}`;
} else if (item.type === "print") {
const received = `#${item.received.libId}#${item.received.varName}#`;
return "$" + `${received}$`;
}
return "";
})
.join(";");
}
const result = structure
.map((item) => {
if (item.type === "if" || item.type === "else if") {
const conditions = item.conditions
.map(mapConditionToString)
.join("")
const body = mapBodyToString(item.body);
return `${item.type}(${conditions}){${body}}`;
} else if (item.type === "while") {
const conditions = item.conditions
.map(mapConditionToString)
.join("")
const body = mapBodyToString(item.body);
return `${item.type}(${conditions}){${body}}`;
} else if (item.type === "else") {
return `${item.type}{${mapBodyToString(item.body)}}`;
}
return "";
})
.join("");
return result;
}
// 字符串转数据结构
export function parseStringToStructure(inputString) {
const structure = [];
function parseCondition(token) {
const regex = /#(\d+)#(.*?)(==|!=|>|<|>=|<=|\&\&|\|\||[\+\-\*/!])#(\d+)#(.*?)\$/;
const matches = token.match(regex);
if (matches) {
return {
left: {
libId: parseInt(matches[1]),
varName: matches[2] || undefined,
},
operator: matches[3] || undefined,
right: {
libId: parseInt(matches[4]),
varName: matches[5] || undefined,
},
};
}
return {};
}
function parseCalculate(token) {
const arr =token.split('#')
return {
type: "calculate",
received: {
libId: arr[1],
varName: arr[2],
},
calculate: {
left: {
libId: arr[4],
varName: arr[5],
},
operator: arr[6],
right: {
libId: arr[7],
varName: arr[8],
}
},
};
}
function parsePrint(token) {
const arr = token.split('#')
console.log(arr)
return {
type: 'print',
received: {
libId: arr[1],
varName: arr[2]
},
calculate: {
left: {},
operator: "",
right: {}
}
};
}
const tokens = inputString.split(/(?<=\}|\]|;|{)/);
let stack = [];
let currentBlock = null;
for (let i = 0; i < tokens.length; i++) {
const token = tokens[i].trim();
console.log(token)
if (token.startsWith("if(") || token.startsWith("else if(")) {
const conditionsRegex = /\((.*?)\)/;
const conditionsMatch = token.match(conditionsRegex);
const conditions = conditionsMatch
? conditionsMatch[1].split(/(\&\&|\|\||==|!=|>|<|>=|<=)/)
: [];
const resConditions = []
let index = 0
conditions.forEach(element => {
if (element === '&&' || element === '||') {
resConditions.push({
left: {
},
operator: element,
right: {
}
})
} else if (element === '!') {
const mtr = conditions[index + 1].match(/#(\d+)#([a-zA-Z]+)/)
resConditions.push({
left: {
},
operator: element,
right: {
libId: mtr[1],
libName: mtr[2]
}
})
} else if (element === '') {
resConditions.push({})
} else if (element === '==' || element === '!=' || element === '>' || element === '<' || element === '>=' || element === '<=') {
const mtl = conditions[index - 1].match(/#(\d+)#([a-zA-Z]+)/)
const mtr = conditions[index + 1].match(/#(\d+)#([a-zA-Z]+)/)
resConditions.push({
left: {
libId: mtl[1],
libName: mtl[2]
},
operator: element,
right: {
libId: mtr[1],
libName: mtr[2]
}
})
}
index++
});
const newBlock = {
type: token.startsWith("if(") ? "if" : "else if",
conditions: resConditions,
body: [],
};
if (currentBlock) {
currentBlock.body.push(newBlock);
} else {
structure.push(newBlock);
}
stack.push(currentBlock);
currentBlock = newBlock;
} else if (token.startsWith("while")) {
const conditionsRegex = /\((.*?)\)/;
const conditionsMatch = token.match(conditionsRegex);
const conditions = conditionsMatch
? conditionsMatch[1].split(/(\&\&|\|\||==|!=|>|<|>=|<=)/)
: [];
const resConditions = []
let index = 0
conditions.forEach(element => {
if (element === '&&' || element === '||') {
resConditions.push({
left: {
},
operator: element,
right: {
}
})
} else if (element === '!') {
const mtr = conditions[index + 1].match(/#(\d+)#([a-zA-Z]+)/)
resConditions.push({
left: {
},
operator: element,
right: {
libId: mtr[1],
libName: mtr[2]
}
})
} else if (element === '') {
resConditions.push({})
} else if (element === '==' || element === '!=' || element === '>' || element === '<' || element === '>=' || element === '<=') {
const mtl = conditions[index - 1].match(/#(\d+)#([a-zA-Z]+)/)
const mtr = conditions[index + 1].match(/#(\d+)#([a-zA-Z]+)/)
resConditions.push({
left: {
libId: mtl[1],
libName: mtl[2]
},
operator: element,
right: {
libId: mtr[1],
libName: mtr[2]
}
})
}
index++
});
const newBlock = {
type: "while",
conditions: resConditions,
body: [],
}
if (currentBlock) {
currentBlock.body.push(newBlock);
} else {
structure.push(newBlock);
}
stack.push(currentBlock);
currentBlock = newBlock;
} else if (token.startsWith("else")) {
const newBlock = {
type: "else",
body: [],
};
if (currentBlock) {
currentBlock.body.push(newBlock);
} else {
structure.push(newBlock);
}
stack.push(currentBlock); // 将当前块压入栈中
currentBlock = newBlock;
} else if (token.startsWith("#")) {
if (token.includes("=")) {
currentBlock.body.push(parseCalculate(token));
}
} else if(token.startsWith('$')) {
currentBlock.body.push(parsePrint(token));
} else if (token === "{") {
} else if (token === "}") {
currentBlock = stack.pop();
}
}
return structure;
}
# 页面样例图
点击事件1后
点击事件2后
点击事件3后
点击事件4后
递归组件图片
← 招新