算术表达式解析系列之优先级爬升法

本篇是算术是表达式解析系列文章之一,上篇:算术表达式解析系列之逆波兰表示法

建议先阅读上篇,本篇不重复介绍一些基本的概念。

再这篇文章里面,将介绍一种完全不同的解决方案,Precedence Climbing Method,下称优先级攀爬算法。 这种算法,在手写一些表达式解析器的时候,经常会使用。

下面简单概括下实现:

  1. 解析录入的原始字符串,输出 token 流
  2. 逐个读取 token,根据算符不同,执行不同的操作

下面开始实现,代码使用 ts 做演示。

目标跟上一篇的相似,提供一样的运算符,不过再几个方面做了强化:

  1. 数值支持更多的形式,例如: 10, -10, 0.5e2 等等等等
  2. 提供完整的 Tokenize 实现,直接录入原始表达式字符串,即可运算出结果
  3. 提供更友好的错误提示,包括指示出错误出现的行号列号

实现 tokenize

tokenize 是将原始字符串录入,转换成一个个 token 的过程。

转换成 token 的目的,是为了简化后续的处理步骤。

实现 tokenize 有很多方法,这里使用手工实现,遍历读取字符进行分析。

首先实现一个简单的流抽象类,用于后续读取原始输入和 tokens。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
abstract class Stream<T> {
  // 当前流过的位置
  private _count = 0

  get count() {
    return this._count
  }

  set count(n: number) {
    this._count = n
  }

  /**
   * 获取缓冲数据抽象方法
   */
  abstract buffer(): any

  /**
   * 是否流干
   */
  drained(): boolean {
    return this.peek() == null
  }

  /**
   * 流到下一个元素
   */
  junk(): void {
    this.count += 1
  }

  /**
   * 流到下一个元素,返回当前元素
   */
  next(): T {
    const e = this.peek()
    if (e != null) this.junk()
    return e
  }

  /**
   * 当前元素
   */
  peek(): T {
    return this.buffer()[this.count]
  }

  /**
   * 读 N 个元素(不移动当前位置)
   * @param n
   */
  npeek(n: number): T[] {
    const count = this.count
    const list = []
    while (n--) {
      list.push(this.next())
    }
    this.count = count
    return list
  }
}

实现一个字符流,接受表达式源码,返回一个流对象,方便管理对字符的读取。

READ MORE...

算术表达式解析系列之逆波兰表示法

假如我们有这样的一个需求,接受一个用户录入的算术表达式,解析并计算出结果。

其中,这个表达式中,可以存在:

  1. 数,表示参与计算的对象
  2. 运算符(可以是自定义的运算符),表示不同的计算
  3. 括号,表示对计算顺序的干预

那可以怎么做?

本系列文章,将提供几种不同的解决方案。本篇将介绍一种常见的方案:“逆波兰表示法”。

首先我们先了解一些概念。

中缀表示法

中缀表示法,应该是我们最常接触的算术表示法了。该表示法,操作符位于两个操作数中间,因此而得名。

【例 1】:

1
(10 + 15 - 20) * 30 / 40 ^ 2

这就是一个使用中缀表示法的例子。

在中缀表示法中,括号可以改变一个表达式的计算顺序。

(1 - 1) - 11 - (1 - 1) 是完全不同的。所以, 1 - 1 - 1 这样的表达式,对于计算机来说,是存在 解析的歧义的,处理起来相对麻烦。

READ MORE...

使用 Vue 实现一个虚拟列表

大列表问题

因为 DOM 性能瓶颈,大型列表存在难以克服的性能问题。 因此,就有了 “局部渲染” 的优化方案,这就是虚拟列表的核心思想。

虚拟列表的实现,需要重点关注的问题一有以下几点:

  1. 可视区域的计算方法
  2. 可视区域的 DOM 更新方案
  3. 事件的处理方案

下面逐一分解说明。

可视区域计算

可视区域的计算,就是使用当前视口的高度、当前滚动条滚过的距离,得到一个可视区域的坐标区间。 算出可视区域的坐标区间之后,在去过滤出落在该区间内的列表项,这个过程,列表项的坐标也是必须能算出的。

思考以下情况,

  1. 我们的视口高度为 100px
  2. 我们当前已经滚动了 100px
  3. 我们的列表项,每一项高度为 20px

根据这些条件,我们可以计算出,当前可视区域为第 11 项至第 20 项。

1
2
3
4
5
6
7
8
9
10
11
12
13
  01 - 05,可视区域上方
+----+-----------+--------
| 06 | 100 ~ 120 |
+----+-----------+
| 07 | 120 ~ 140 |
+----+-----------+
| 08 | 140 ~ 160 | 可视区域
+----+-----------+
| 09 | 160 ~ 180 |
+----+-----------+
| 10 | 180 ~ 200 |
+----+-----------+--------
  11 - N,可视区域下方

这是因为列表项高度是固定的,我们可以通过简单的四则运算算出已经滚动过去的 100px 中,已经滚动走了 5 个列表项,因此可视区域是从第 6 项开始,而视口高度为 100px,能容纳 100 / 20 即 5 个条目。

上面例子的情况非常简单,也不存在性能问题,因此实际上并没有展开讨论的价值。 而还有另一种复杂很多的情况,那就是,列表项高度不固定,根据内容决定高度。

此时,我们就没办法直接使用四则运算一步到位算出可视区域对应的条目了。

而必须实现一种机制,记录所有列表项的坐标,再通过检查列表项是否落在视口内。

下面重点讨论该问题。

READ MORE...

JavaScript 中的 “相等” 算法

整理笔记本时,看到以往一些对 JavaScript 中 “相等” 关系的记录。 尽管这是一个被说烂了的话题,但写一篇资料整理总结,当作复习下也不错。

JavaScript 的 “相等” 比较算法,按严格程度来排,有以下几种:

  1. == 双等号
  2. === 三等号
  3. SameValueZero 算法
  4. SameValue 算法

下面逐个介绍它们的特点。


== 双等号

在 JavaScript 中,使用 == 来判断相等,是一种不严格的比较。

关于双等号,最广为人知的一点,就是在比较不同类型的值时,JavaScript 会进行自动转型。

如果不明白其转型规则,可能会出现让人匪夷所思的结果。

举例来说:

1
2
3
'' == false // true
'  ' == false // true
'' == ' ' // false

具体的转型规则如下:

  1. 两边是对象(引用类型),比较内存地址是否相同。
  2. 一边是原始类型,一边是对象,则将对象转换成原始类型再比较
  3. 两边都是原始类型:
    • 3.1. 一边是 Symbol,则返回 false
    • 3.2. 两边类型一样,直接比较值
    • 3.3. 一边为 undefinednull,则比较另一边是否也为 undefinednull
    • 3.4. 一边为 “数字” 或者 “布尔值”,则以 “数字” 进行比较
READ MORE...