Appearance
前言
在Vue的开发过程中，我们经常会用到v-for指令，不得不说这个爽的一批，但是他是怎么转换成我们能看得到的DOM元素呢？
这时候我们就可以用AST抽象语法树作为中介，去协调这件事情
AST抽象语法树本质上就是一个JS对象。它把模板的语法，转为字符串的的样子，最后解析为AST。
咋一看就很眼熟啊，这不是之前学过的Vue源码解析之mustache模板引擎吗？将字符串模板收集起来变为tokens吗？对的
那问题来了，有转为模板语法的方法参考了，那转为真是DOM呢？那就需要虚拟DOM和Diff算法了？
snabbdom是著名的虚拟DOM库，是diff算法的鼻祖，Vue源码借鉴了snabbdom；之前也学习过Vue源码解析之虚拟DOM和diff算法
它们之间的关系图如下：
学习了前面两篇文章，学习到了很多的算法，譬如递归、栈、指针、obj['a.b.c']查找值，很有意思。
这次我们先学习相关的算法，在去学习AST抽象语法树
相关算法储备 - 指针思想
题目：试寻找字符串中，连续重复次数最多的字符。
js
var str = 'aaaabbbbbcccccccccccccdddddd'var str = 'aaaabbbbbcccccccccccccdddddd'思路：
- 设置两个指针，i表示对比指针，j为移动指针，通过移动去对比i
- 如果i和j指向的字一样，那么i不动，j后移
- 如果i和j指向的字不一样，此时说明它们之间的字都是连续相同的，让i追上j，j后移
答案
js
function findStrMax(str) {
// 指针
var i = 0;
var j = 1;
// 当前重复次数最多的次数
var maxRepeatCount = 0;
// 重复次数最多的字符串
var maxRepeatChar = '';
// 当i还在范围内的时候，应该继续寻找
while (i <= str.length - 1) {
// 看i指向的字符和j指向的字符是不是不相同
if (str[i] != str[j]) {
// console.log('报！！！' + i + '和' + j + '之间的文字连续相同！！都是字母' + str[i] + '它重复了' + (j - i) + '次');
// 和当前重复次数最多的进行比较
if (j - i > maxRepeatCount) {
// 如果当前文字重复次数（j - i）超过了此时的最大值
// 就让它成为最大值
maxRepeatCount = j - i;
// 将i指针指向的字符存为maxRepeatChar
maxRepeatChar = str[i];
}
// 让指针i追上指针j
i = j;
}
// 不管相不相同，j永远要后移
j++;
}
// 循环结束之后，就可以输出答案了
console.log(maxRepeatChar + '重复了' + maxRepeatCount + '次，是最多的连续重复字符');
return maxRepeatChar
}
console.log(findStrMax(str))function findStrMax(str) {
// 指针
var i = 0;
var j = 1;
// 当前重复次数最多的次数
var maxRepeatCount = 0;
// 重复次数最多的字符串
var maxRepeatChar = '';
// 当i还在范围内的时候，应该继续寻找
while (i <= str.length - 1) {
// 看i指向的字符和j指向的字符是不是不相同
if (str[i] != str[j]) {
// console.log('报！！！' + i + '和' + j + '之间的文字连续相同！！都是字母' + str[i] + '它重复了' + (j - i) + '次');
// 和当前重复次数最多的进行比较
if (j - i > maxRepeatCount) {
// 如果当前文字重复次数（j - i）超过了此时的最大值
// 就让它成为最大值
maxRepeatCount = j - i;
// 将i指针指向的字符存为maxRepeatChar
maxRepeatChar = str[i];
}
// 让指针i追上指针j
i = j;
}
// 不管相不相同，j永远要后移
j++;
}
// 循环结束之后，就可以输出答案了
console.log(maxRepeatChar + '重复了' + maxRepeatCount + '次，是最多的连续重复字符');
return maxRepeatChar
}
console.log(findStrMax(str))打印结果：
相关算法储备 - 递归深入
题目1：试输出斐波那契数列的前10项，即1、1、2、3、5、8、13、21、34、55。然后请思考，代码是否有大量重复的计算？应该如何解决重复计算的问题？
斐波那契数列就是当前需求的n项等于n-1 加 n-2项的和，如下图：
由上图可以看出，fib(2)计算的两次，fib(1)计算了三次，存在大量重复计算：
js
for (let i = 0; i <= 9; i++) {
console.log(fib(i));
}
function fib(n) {
console.count("次数")
return n == 0 || n == 1 ? 1 : fib(n - 1) + fib(n - 2)
}for (let i = 0; i <= 9; i++) {
console.log(fib(i));
}
function fib(n) {
console.count("次数")
return n == 0 || n == 1 ? 1 : fib(n - 1) + fib(n - 2)
}打印结果：
优化后：
js
// 缓存对象
var cache = {};
// 创建一个函数，功能是返回下标为n的这项的数字
function fib(n) {
console.count("次数")
// 判断缓存对象中有没有这个值，如果有，直接用
if (cache.hasOwnProperty(n)) {
return cache[n];
}
// 缓存对象没有这个值
// 看下标n是不是0或者是不是1，如果是，就返回常数1
// 如果不是，就递归
var v = n == 0 || n == 1 ? 1 : fib(n - 1) + fib(n - 2);
// 写入缓存。也就是说，每算一个值，就要把这个值存入缓存对象。
cache[n] = v;
return v;
}
for (let i = 0; i <= 9; i++) {
console.log(fib(i));
}
// 缓存对象
var cache = {};
// 创建一个函数，功能是返回下标为n的这项的数字
function fib(n) {
console.count("次数")
// 判断缓存对象中有没有这个值，如果有，直接用
if (cache.hasOwnProperty(n)) {
return cache[n];
}
// 缓存对象没有这个值
// 看下标n是不是0或者是不是1，如果是，就返回常数1
// 如果不是，就递归
var v = n == 0 || n == 1 ? 1 : fib(n - 1) + fib(n - 2);
// 写入缓存。也就是说，每算一个值，就要把这个值存入缓存对象。
cache[n] = v;
return v;
}
for (let i = 0; i <= 9; i++) {
console.log(fib(i));
}打印结果：
276变26直接10倍👍
数组方法：
js
function getFbnc(num) {
let fbnc = [];
fbnc[0] = 1;
fbnc[1] = 1;
for (let i = 2; i < num; i++) {
fbnc[i] = fbnc[i - 1] + fbnc[i - 2];
}
return fbnc;
}
getFbnc(10);function getFbnc(num) {
let fbnc = [];
fbnc[0] = 1;
fbnc[1] = 1;
for (let i = 2; i < num; i++) {
fbnc[i] = fbnc[i - 1] + fbnc[i - 2];
}
return fbnc;
}
getFbnc(10);题目2：试将高维数组[1, 2, [3, [4, 5], 6], 7, [8], 9]变为图中所示的对象
写法一：
js
var arr = [1, 2, 3, [4, 5],
[
[
[6], 7, 8
], 9
], 10
];
function convert(arr) {
// 准备一个结果数组
var result = [];
// 遍历传入的arr的每一项
for (let i = 0; i < arr.length; i++) {
// 如果遍历到的数字是number，直接放进入
if (typeof arr[i] == 'number') {
result.push({
value: arr[i]
});
} else if (Array.isArray(arr[i])) {
// 如果遍历到的这项是数组，那么就递归
result.push({
children: convert(arr[i])
});
}
}
return result;
}
const o = {
children: convert(arr)
}
console.log(o)var arr = [1, 2, 3, [4, 5],
[
[
[6], 7, 8
], 9
], 10
];
function convert(arr) {
// 准备一个结果数组
var result = [];
// 遍历传入的arr的每一项
for (let i = 0; i < arr.length; i++) {
// 如果遍历到的数字是number，直接放进入
if (typeof arr[i] == 'number') {
result.push({
value: arr[i]
});
} else if (Array.isArray(arr[i])) {
// 如果遍历到的这项是数组，那么就递归
result.push({
children: convert(arr[i])
});
}
}
return result;
}
const o = {
children: convert(arr)
}
console.log(o)打印结果：
写法二：
js
function convert(item){
if(typeof item == "number"){
return {
value:item
}
}else if(Array.isArray(item)){
return {
children:item.map(_item=>convert(_item))
}
}
}
console.log(convert(arr))function convert(item){
if(typeof item == "number"){
return {
value:item
}
}else if(Array.isArray(item)){
return {
children:item.map(_item=>convert(_item))
}
}
}
console.log(convert(arr))相关算法储备 - 栈
- 栈（stack）又名堆栈，它是一种运算受限的线性表，仅在表尾能进行插入和删除操作。这一端被称为栈顶，相对地，把另一端称为栈底。
- 向一个栈插入新元素又称作进栈、入栈或压栈；从一个栈删除元素又称作出栈或退栈。
- **后进先出（LIFO）**特点：栈中的元素，最先进栈的必定是最后出栈，后进栈的一定会先出栈
- JavaScript中，栈可以用数组模拟。需要限制只能使用push()和pop()，不能使用unshift()和shift()。即，数组尾是栈顶。
- 当然，可以用面向对象等手段，将栈封装的更好。
题目 :试编写“智能重复”smartRepeat函数，实现：
- 将3[abc]变为abcabcabc
- 将3[2[a]2[b]]变为aabbaabbaabb
- 将2[1[a]3[b]2[3[c]4[d]]]变为abbbcccddddcccddddabbbcccddddcccdddd 不用考虑输入字符串是非法的情况，比如：
- 2[a3[b]]是错误的，应该补一个1，即2[1[a]3[b]]
- [abc]是错误的，应该补一个1，即1[abc]
思路：
- 遍历每一个字符如果这个字符是数字，那么就把数字压栈，把空字符串压栈
- 遍历每一个字符如果这个字符是字母，那么此时就把栈顶这项改为这个字母
- 遍历每一个字符如果这个字符是]，那么就将数字弹栈，就把字符串栈的栈顶的元素重复刚刚的这个次数，弹栈，拼接到新栈顶上
在获取相应的数字的时候，我们可以用正则的方式去获取：
答案：
js
// 试编写“智能重复”smartRepeat函数，实现：
// 将3[abc]变为abcabcabc
// 将3[2[a]2[b]]变为aabbaabbaabb
// 将2[1[a]3[b]2[3[c]4[d]]]变为abbbcccddddcccddddabbbcccddddcccdddd
function smartRepeat(templateStr) {
// 指针
var index = 0;
// 栈1，存放数字
var stack1 = [];
// 栈2，存放临时字符串
var stack2 = [];
// 剩余部分
var rest = templateStr;
while (index < templateStr.length - 1) {
// 剩余部分
rest = templateStr.substring(index);
// 看当前剩余部分是不是以数字和[开头
if (/^\d+\[/.test(rest)) {
// 得到这个数字
let times = Number(rest.match(/^(\d+)\[/)[1]);
// 就把数字压栈，把空字符串压栈
stack1.push(times);
stack2.push('');
// 让指针后移，times这个数字是多少位就后移多少位加1位。
// 为什么要加1呢？加的1位是[。
index += times.toString().length + 1;
} else if (/^\w+\]/.test(rest)) {
// 如果这个字符是字母，那么此时就把栈顶这项改为这个字母
let word = rest.match(/^(\w+)\]/)[1];
stack2[stack2.length - 1] = word;
// 让指针后移，word这个词语是多少位就后移多少位
index += word.length;
} else if (rest[0] == ']') {
// 如果这个字符是]，那么就①将stack1弹栈，②stack2弹栈，③把字符串栈的新栈顶的元素重复刚刚弹出的那个字符串指定次数拼接到新栈顶上。
let times = stack1.pop();
let word = stack2.pop();
// repeat是ES6的方法，比如'a'.repeat(3)得到'aaa'
stack2[stack2.length - 1] += word.repeat(times);
index++;
}
console.log(index, stack1, stack2);
}
// while结束之后，stack1和stack2中肯定还剩余1项。返回栈2中剩下的这一项，重复栈1中剩下的这1项次数，组成的这个字符串。如果剩的个数不对，那就是用户的问题，方括号没有闭合。
return stack2[0].repeat(stack1[0]);
}
var result = smartRepeat('3[2[3[a]1[b]]4[d]]');
console.log(result);// 试编写“智能重复”smartRepeat函数，实现：
// 将3[abc]变为abcabcabc
// 将3[2[a]2[b]]变为aabbaabbaabb
// 将2[1[a]3[b]2[3[c]4[d]]]变为abbbcccddddcccddddabbbcccddddcccdddd
function smartRepeat(templateStr) {
// 指针
var index = 0;
// 栈1，存放数字
var stack1 = [];
// 栈2，存放临时字符串
var stack2 = [];
// 剩余部分
var rest = templateStr;
while (index < templateStr.length - 1) {
// 剩余部分
rest = templateStr.substring(index);
// 看当前剩余部分是不是以数字和[开头
if (/^\d+\[/.test(rest)) {
// 得到这个数字
let times = Number(rest.match(/^(\d+)\[/)[1]);
// 就把数字压栈，把空字符串压栈
stack1.push(times);
stack2.push('');
// 让指针后移，times这个数字是多少位就后移多少位加1位。
// 为什么要加1呢？加的1位是[。
index += times.toString().length + 1;
} else if (/^\w+\]/.test(rest)) {
// 如果这个字符是字母，那么此时就把栈顶这项改为这个字母
let word = rest.match(/^(\w+)\]/)[1];
stack2[stack2.length - 1] = word;
// 让指针后移，word这个词语是多少位就后移多少位
index += word.length;
} else if (rest[0] == ']') {
// 如果这个字符是]，那么就①将stack1弹栈，②stack2弹栈，③把字符串栈的新栈顶的元素重复刚刚弹出的那个字符串指定次数拼接到新栈顶上。
let times = stack1.pop();
let word = stack2.pop();
// repeat是ES6的方法，比如'a'.repeat(3)得到'aaa'
stack2[stack2.length - 1] += word.repeat(times);
index++;
}
console.log(index, stack1, stack2);
}
// while结束之后，stack1和stack2中肯定还剩余1项。返回栈2中剩下的这一项，重复栈1中剩下的这1项次数，组成的这个字符串。如果剩的个数不对，那就是用户的问题，方括号没有闭合。
return stack2[0].repeat(stack1[0]);
}
var result = smartRepeat('3[2[3[a]1[b]]4[d]]');
console.log(result);手写实现AST抽象语法树
基本思路： 跟上面的的算法题的思路大同小异的。首先要有一个指针index，用while进行遍历，移动index，用正则去判断和捕获到开始标签和结束标签 ，还要捕获标签内的内容文本，同样也要准备两个栈，一个是存放标签的栈，一个是存放当前这个标签所存放的内容集合tag、children、attrs那些内容。
思路图：
index.js
js
import parse from './parse.js';
var templateString = `<div>
<h3 class="aa bb cc" data-n="7" id="mybox">你好</h3>
<ul>
<li>A</li>
<li>B</li>
<li>C</li>
</ul>
</div>`;
const ast = parse(templateString);
console.log(ast);import parse from './parse.js';
var templateString = `<div>
<h3 class="aa bb cc" data-n="7" id="mybox">你好</h3>
<ul>
<li>A</li>
<li>B</li>
<li>C</li>
</ul>
</div>`;
const ast = parse(templateString);
console.log(ast);parse.js
js
import parseAttrsString from './parseAttrsString.js';
// parse函数，主函数
export default function (templateString) {
// 指针
var index = 0;
// 剩余部分
var rest = '';
// 开始标记
var startRegExp = /^\<([a-z]+[1-6]?)(\s[^\<]+)?\>/;
// 结束标记
var endRegExp = /^\<\/([a-z]+[1-6]?)\>/;
// 抓取结束标记前的文字
var wordRegExp = /^([^\<]+)\<\/[a-z]+[1-6]?\>/;
// 准备两个栈
var stack1 = [];
var stack2 = [{ 'children': [] }];
while (index < templateString.length - 1) {
rest = templateString.substring(index);
// console.log(templateString[index]);
if (startRegExp.test(rest)) {
// 识别遍历到的这个字符，是不是一个开始标签
let tag = rest.match(startRegExp)[1];
let attrsString = rest.match(startRegExp)[2];
// console.log('检测到开始标记', tag);
// 将开始标记推入栈1中
stack1.push(tag);
// 将空数组推入栈2中
stack2.push({ 'tag': tag, 'children': [], 'attrs': parseAttrsString(attrsString) });
// 得到attrs字符串的长度
const attrsStringLength = attrsString != null ? attrsString.length : 0;
// 指针移动标签的长度加2再加attrString的长度，为什么要加2呢？因为<>也占两位
index += tag.length + 2 + attrsStringLength;
} else if (endRegExp.test(rest)) {
// 识别遍历到的这个字符，是不是一个结束标签
let tag = rest.match(endRegExp)[1];
// console.log('检测到结束标记', tag);
let pop_tag = stack1.pop();
// 此时，tag一定是和栈1顶部的是相同的
if (tag == pop_tag) {
let pop_arr = stack2.pop();
if (stack2.length > 0) {
stack2[stack2.length - 1].children.push(pop_arr);
}
} else {
throw new Error(pop_tag + '标签没有封闭！！');
}
// 指针移动标签的长度加3，为什么要加2呢？因为</>也占3位
index += tag.length + 3;
} else if (wordRegExp.test(rest)) {
// 识别遍历到的这个字符，是不是文字，并别不能是全空
let word = rest.match(wordRegExp)[1];
// 看word是不是全是空
if (!/^\s+$/.test(word)) {
// 不是全是空
// console.log('检测到文字', word);
// 改变此时stack2栈顶元素中
stack2[stack2.length - 1].children.push({ 'text': word, 'type': 3 });
}
// 指针移动标签的长度加3，为什么要加2呢？因为</>也占3位
index += word.length;
} else {
index++;
}
}
// 此时stack2就是我们之前默认放置的一项了，此时要返回这一项的children即可
return stack2[0].children[0];
};import parseAttrsString from './parseAttrsString.js';
// parse函数，主函数
export default function (templateString) {
// 指针
var index = 0;
// 剩余部分
var rest = '';
// 开始标记
var startRegExp = /^\<([a-z]+[1-6]?)(\s[^\<]+)?\>/;
// 结束标记
var endRegExp = /^\<\/([a-z]+[1-6]?)\>/;
// 抓取结束标记前的文字
var wordRegExp = /^([^\<]+)\<\/[a-z]+[1-6]?\>/;
// 准备两个栈
var stack1 = [];
var stack2 = [{ 'children': [] }];
while (index < templateString.length - 1) {
rest = templateString.substring(index);
// console.log(templateString[index]);
if (startRegExp.test(rest)) {
// 识别遍历到的这个字符，是不是一个开始标签
let tag = rest.match(startRegExp)[1];
let attrsString = rest.match(startRegExp)[2];
// console.log('检测到开始标记', tag);
// 将开始标记推入栈1中
stack1.push(tag);
// 将空数组推入栈2中
stack2.push({ 'tag': tag, 'children': [], 'attrs': parseAttrsString(attrsString) });
// 得到attrs字符串的长度
const attrsStringLength = attrsString != null ? attrsString.length : 0;
// 指针移动标签的长度加2再加attrString的长度，为什么要加2呢？因为<>也占两位
index += tag.length + 2 + attrsStringLength;
} else if (endRegExp.test(rest)) {
// 识别遍历到的这个字符，是不是一个结束标签
let tag = rest.match(endRegExp)[1];
// console.log('检测到结束标记', tag);
let pop_tag = stack1.pop();
// 此时，tag一定是和栈1顶部的是相同的
if (tag == pop_tag) {
let pop_arr = stack2.pop();
if (stack2.length > 0) {
stack2[stack2.length - 1].children.push(pop_arr);
}
} else {
throw new Error(pop_tag + '标签没有封闭！！');
}
// 指针移动标签的长度加3，为什么要加2呢？因为</>也占3位
index += tag.length + 3;
} else if (wordRegExp.test(rest)) {
// 识别遍历到的这个字符，是不是文字，并别不能是全空
let word = rest.match(wordRegExp)[1];
// 看word是不是全是空
if (!/^\s+$/.test(word)) {
// 不是全是空
// console.log('检测到文字', word);
// 改变此时stack2栈顶元素中
stack2[stack2.length - 1].children.push({ 'text': word, 'type': 3 });
}
// 指针移动标签的长度加3，为什么要加2呢？因为</>也占3位
index += word.length;
} else {
index++;
}
}
// 此时stack2就是我们之前默认放置的一项了，此时要返回这一项的children即可
return stack2[0].children[0];
};parseAttrsString.js
js
// 把attrsString变为数组返回
export default function (attrsString) {
if (attrsString == undefined) return [];
console.log(attrsString);
// 当前是否在引号内
var isYinhao = false
// 断点
var point = 0;
// 结果数组
var result = [];
// 遍历attrsString，而不是你想的用split()这种暴力方法
for (let i = 0; i < attrsString.length; i++) {
let char = attrsString[i];
if (char == '"') {
isYinhao = !isYinhao;
} else if (char == ' ' && !isYinhao) {
// 遇见了空格，并且不在引号中
console.log(i);
if (!/^\s*$/.test(attrsString.substring(point, i))) {
result.push(attrsString.substring(point, i).trim());
point = i;
}
}
}
// 循环结束之后，最后还剩一个属性k="v"
result.push(attrsString.substring(point).trim());
// 下面的代码功能是，将["k=v","k=v","k=v"]变为[{name:k, value:v}, {name:k, value:v}, {name:k,value:v}];
result = result.map(item => {
// 根据等号拆分
const o = item.match(/^(.+)="(.+)"$/);
return {
name: o[1],
value: o[2]
};
});
return result;
}// 把attrsString变为数组返回
export default function (attrsString) {
if (attrsString == undefined) return [];
console.log(attrsString);
// 当前是否在引号内
var isYinhao = false
// 断点
var point = 0;
// 结果数组
var result = [];
// 遍历attrsString，而不是你想的用split()这种暴力方法
for (let i = 0; i < attrsString.length; i++) {
let char = attrsString[i];
if (char == '"') {
isYinhao = !isYinhao;
} else if (char == ' ' && !isYinhao) {
// 遇见了空格，并且不在引号中
console.log(i);
if (!/^\s*$/.test(attrsString.substring(point, i))) {
result.push(attrsString.substring(point, i).trim());
point = i;
}
}
}
// 循环结束之后，最后还剩一个属性k="v"
result.push(attrsString.substring(point).trim());
// 下面的代码功能是，将["k=v","k=v","k=v"]变为[{name:k, value:v}, {name:k, value:v}, {name:k,value:v}];
result = result.map(item => {
// 根据等号拆分
const o = item.match(/^(.+)="(.+)"$/);
return {
name: o[1],
value: o[2]
};
});
return result;
}总结
好像先从算法开始引用，后面的更好理解了一些