跟着B站学VUE2源码之第四课：AST抽象语法树

课程内容：

3个常见算法思想：指针思想、递归缓存和栈
AST的形成算法
手写AST及优化

AST抽象语法树：

1、本质上是个JS对象，作用是为了让模板语法变成正常的HTML语法
2、用js来表现HTML结构的东西实际上就是AST（抽象语法树）

虚拟节点和AST有什么关系？

1、vue底层（vue-loader)是在用字符串的视角来识别html标签
2、整个流程如下：
模板语法 => AST抽象语法树 => 渲染函数（h函数）=> 虚拟节点 => 经过diff和patch => 渲染成界面

AST的实现函数parse函数

parse函数的主函数，实现输入一个模板结构转换成包含dom信息的层级对象结构

parse函数的作用

算法储备

1、指针思想

JS中的指针就是下标位置，指正就是偏移量，第一个数的偏移量是0

算法题一： 试图寻找字符串当中连续重复次数最多的字符
let str = 'aaaaaaabbbbbbbccccccccccccccccccddddddddddddd'
// 定义指针
let i = 0
let j = 1
// 寻找最多的次数与字符
let maxRepeat = 0
let maxRepeatStr = ''
// 进入循环 
while (i <= str.length - 1) {
    if (str[i] !== str[j]) {
        // 与当前重复次数最多的进行比较 和赋值
        if (j - i > maxRepeat) {
            maxRepeat = j - i
            maxRepeatStr = str[i]
        }
        // 让指针i 追上指针J
        i = j
    }
    j++
}
console.log(maxRepeatStr + '重复了' +maxRepeat +'次');

2、递归深入-菲波那契数列

// 算法题二：递归深入，试着输出菲波那契数列的前十项 [1、1、2、3、5、8、13、21]

// 1. 简单实现
// 创建一个函数，返回功能下标为N的这项的数字
function feb1(n) {
    console.count('触发次数') // 触发次数: 99
    return n == 0 || n ==1 ? 1 : feb1(n-1) + feb1(n-2)
}

// 2. 利用缓存
// cache思想，利用缓存对象，解决大量重复计算的问题
let cache = {}
function feb2(n) {
    console.count('触发次数') // 触发次数: 19
    if (n in cache) {
        return cache[n]
    }
    let val = n == 0 || n ==1 ? 1 : feb2(n-1) + feb2(n-2)
    cache[n] = val
    return val
}

// 测试
let n = 0
while (n <= 6) {
    console.log(feb2(n));
    n++
}

3、递归深入-高维数组

小技巧：只要出现了规则复现，就可以使用递归。tips：规则复现

// 算法题三：将高维数组 变成一个key:value 和 children：arr的数组对象

// 1. 循环实现
let myArr = [1, 2, 3, [4, 5, [6, 7, 8, [9, 10]]]]
function fn(arr) {
    let resultArr = []
    for (let i = 0; i < arr.length; i++) {
        if (typeof arr[i] == 'number') {
            resultArr.push({
                'value': arr[i]
            })
        } else if (Array.isArray(arr[i])) {
            resultArr.push({
                'children': fn(arr[i])
            })
        }
    }
    return resultArr
}
// console.log(fn(myArr));

// 2. 使用映射map实现 item可能是数组也可能是数字
// 注意：写法一的递归次数要大大小于写法二
let myArr2 = [1, 2, 3, [4, 5, [6, 7, 8, [9, 10]]]]
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(myArr2));

4、栈

词法分析的时候需要经常要用到栈这个结构，是非常著名的数据结构，可以辅助来解决算法题目
JS中的栈，可以用数组模拟，只能使用push 和 pop 方法操作进栈和出栈。注意：栈是后进先出！

// 题目：smartRepeat函数
// 试编写“智能重复” 实现：将3[abc]变为abcabcabc、将3[2[a]2[b]]变为aabbaabbaabb