重新定义加法

作者: 不吃瓜的码农 | 来源:发表于2020-05-13 17:27 被阅读0次

重新定义加法
Deep Learning - 第二章-线性代数重要知识点复习-
近世代数理论基础18：环的定义及性质
向量空间
《情怀与理想》
2018-06-12
未来之镜
重新定义你的职业生涯
笑来写作课二期笔记
高等代数理论基础27：矩阵的运算

众所周知，js做算术运算是不精确的，0.1 + 0.2并不等于0.3。

0.1 + 0.2
因为公司业务的原因，我们常需要将宝石的价格、重量和尺寸进行单位换算。由于js的算术运算不精确，常导致计算后产生.99999这样的数。为了解决这个问题，我们引入了一个第三方库number-precision。number-precision是个小的库。它的主要思想是将小数转换为整数后再计算。因为我们业务中只用到四则运算，且数字都不会很大，用这个库足以覆盖所有场景，所以我选择了它。number-precision主要代码如下：

/**
 * @desc 解决浮动运算问题，避免小数点后产生多位数和计算精度损失。
 * 问题示例：2.3 + 2.4 = 4.699999999999999
 *         1.0 - 0.9 = 0.09999999999999998
 *         0.3 * 3 = 0.8999999999999999
 *         0.3 / 0.1 = 2.9999999999999996
 */

/**
 * 把错误的数据转正
 * strip(0.09999999999999998)=0.1
 */
function strip(num, precision) {
  return +parseFloat(num.toPrecision(precision || 12))
}

/**
 * 把小数放大成整数
 * @param {*number} num 输入数
 */
function float2Fixed(num) {
  return Number(num.toString().replace('.', ''))
}

/**
 * Return digits length of a number
 * @param {*number} num Input number
 */
function digitLength(num) {
  const decimal = num.toString().split('.')[1] || ''
  return decimal.length
}

/**
 * 精确乘法
 */
function multiply(num1, num2) {
  const num1Changed = float2Fixed(num1)
  const num2Changed = float2Fixed(num2)
  const baseNum = digitLength(num1) + digitLength(num2)
  const leftValue = num1Changed * num2Changed

  return leftValue / Math.pow(10, baseNum)
}

/**
 * 精确加法
 */
function plus(num1, num2) {
  const baseNum = Math.pow(10, Math.max(digitLength(num1), digitLength(num2)))
  return (multiply(num1, baseNum) + multiply(num2, baseNum)) / baseNum
}

/**
 * 精确减法
 */
function minus(num1, num2) {
  const baseNum = Math.pow(10, Math.max(digitLength(num1), digitLength(num2)))
  return (multiply(num1, baseNum) - multiply(num2, baseNum)) / baseNum
}

/**
 * 精确除法
 */
function divide(num1, num2) {
  const num1Changed = float2Fixed(num1)
  const num2Changed = float2Fixed(num2)
  return multiply(
    (num1Changed / num2Changed),
    strip(Math.pow(10, digitLength(num2) - digitLength(num1)))
  )
}

number-precision重新定义了加减乘除，我们在做计算的时候需要调用这些方法，比如计算：(1+2*(3-1))/2，我们需要这么写：

const {
  plus,
  minus,
  multiply,
  divide
} = require('number-precision')

const result = divide(plus(1, multiply(2, minus(3, 1))), 2)

是不是觉得很麻烦，还要仔细检查方法调用的顺序，不小心就写错了。
如果我们在写代码的时候还是写(1+2*(3-1))/2，代码在执行的时候，它被解释成divide(plus(1, multiply(2, minus(3, 1))), 2)执行就好了。
那么，让我们做点好玩的事情，用js写一个四则运算的解释器吧，用它把+-*/解释成number-precision对应的方法执行。

词法分析

我们只需要识别8种词法单元（token）：加号、减号、乘号、除号、左括号、右括号、数字、变量，分别用字符表示为：+,-,*,/,(,),n,v。
我们使用正则来识别token，并采用最长匹配原则。
首先，定义一个Grammar类，这个类很简单，它存储了表示token的字符，和识别token的正则。

class Grammar {
  constructor(token, pattern) {
    this.token = token
    this.pattern = pattern
  }
}

我们需要识别的8种token分别定义为：

/* 数字 */
new Grammar('n', /(?:[0-9]\.|[1-9][0-9]+\.|\.[0-9]|[0-9])[0-9]*/)
/* 变量 */
new Grammar('v', /[A-z_$][A-z0-9_$]*/)
/* 加号 */
new Grammar('+', /\+/)
/* 减号 */
new Grammar('-', /-/)
/* 乘号 */
new Grammar('*', /\*/)
/* 除号 */
new Grammar('/', /\//)
/* 左括号 */
new Grammar('(', /\(/)
/* 右括号 */
new Grammar(')', /\)/)

然后写一个词法分析器，它读入字符串，输出token序列。

class LexicalAnalyzer {
  constructor(grammars) {
    this.grammars = grammars
    this.tokens = []
  }

  parse(str) {
    this.tokens.length = 0
    return this.analyze(str)
  }

  analyze(str) {
    // 忽略空白字符
    str = str.trim()
    let value = ''
    let type = ''
    for (const grammar of this.grammars) {
      const rst = grammar.pattern.exec(str)

      // 找出最长匹配
      if (rst && rst.index === 0 && rst[0].length > value.length) {
        value = rst[0]
        type = grammar.token
      }
    }

    if (!type) throw new Error(`词法错误：'${str}' 包含无法识别的字符`)

    this.tokens.push({
      type,
      value,
    })
    const nextStr = str.replace(value, '')

    if (nextStr) {
      // 通过递归，识别下一个单词
      this.analyze(nextStr)
    }

    return [...this.tokens]
  }
}

看看效果：

词法分析

语法分析

词法分析后，我们需要分析语法。
首先，我们需要给出上下文无关文法，来描述我们的语法规则：

E -> n
E -> v
E -> P
P -> (S)
S -> E
S -> E + S
S -> E - S
S -> E * S
S -> E / S

其中每一行，我们称之为一个产生式，产生式中->左边的大写字符是非终结符，上面的文法中有3个非终结符：E、P和S。非终结符可由产生式中->右边的式子推导（扩展）。产生式右边的式子由非终结符和终结符组成，终结符就是词法分析中得到的token。
S是文法的开始符号，从S开始，我们应用文法中的规则，递归展开非终结符，直到只剩下终结符为止，最终生成四则运算语法规则集合。
下面是根据规则完全展开S的方式之一：

 S
  -> E * S              // 展开`S`
  -> P * S              // 展开`E`
  -> (S) * S            // 展开`P`
  -> (E - S) * S        // 展开`S`
  -> (n - S) * S        // 展开`E`
  -> (n - E) * S        // 展开`S`
  -> (n - n) * S        // 展开`E`
  -> (n - n) * E        // 展开`S`
  -> (n - n) * n        // 展开`E`

这表明(n-n)*n在语法上有效。
也就是说，用词法分析得到的token序列，如果能通过文法推导出来，那就是有效语法。我们可以使用非确定性下推自动机（NPDA）来判断输入是否语法正确。

NPDA

状态图

如图所示，NPDA使用栈存储推导过程中的非终结符和终结符，并在4个状态间转移。图中，每个圆圈代表一个状态，箭头指示了NPDA从一个状态转移到另一个状态。引起状态转移的事件显示在表示状态转移的横线上方，状态转移时所采取的动作显示在横线下方。
为了更直观的看NPDA是如何工作，我们假设输入是0.1+0.2，经过词法分析后得到token序列n+n。下面是NPDA的一个可能执行：

状态	是否接受	栈的内容	剩余输入	动作
1	否		n+n	应用规则①，S入栈，转移到状态2
2	否	S	n+n	应用规则②，S出栈，E+S入栈
2	否	E+S	n+n	应用规则②，E出栈，n入栈
2	否	n+S	n+n	应用规则③，读取n，n出栈
2	否	+S	+n	应用规则③，读取+，+出栈
2	否	S	n	应用规则②，S出栈，E入栈
2	否	E	n	应用规则②，E出栈，n入栈
2	否	n	n	应用规则③，读取n， n出栈
2	否			应用规则④，转移到状态3
3	是

从状态图中可以看到，NPDA每次转移，要么是状态变化，要么是栈变化，所以转移实际上是从一个状态+栈到另一个状态+栈。为了方便，我们用配置表示一个状态和一个栈的组合。

const STUCK = Symbol('stuck')

class Configuration {
  constructor(state, stack) {
    this.state = state
    this.stack = stack
  }

  isStuck() {
    return this.state === STUCK
  }

  stuck() {
    this.state = STUCK
    return this
  }
}

配置中的栈，我们也定义一个类，方便操作：

class Stack {
  constructor(...items) {
    this.items = items
  }

  getTop() {
    return this.items[0]
  }

  getItems() {
    return [...this.items]
  }

  pop() {
    return this.items.shift()
  }

  push(...items) {
    return this.items.unshift(...items)
  }
}

有了配置之后，我们还需要一种规则类型，来告诉NPDA，配置间应该如何转移。一条规则由当前配置、输入符号和下一个配置组成。通过NPDA的当前配置和读取的符号，我们能找到它能应用的规则，并应用规则将NPDA转移到下一个配置。规则类定义如下：

class PDARule {
  constructor(state, character, popCharacter, nextState, pushCharacters) {
    this.state = state
    this.character = character
    this.popCharacter = popCharacter
    this.nextState = nextState
    this.pushCharacters = pushCharacters
  }

  appliesTo(configuration, character) {
    return configuration.stack.getTop() === this.popCharacter &&
      configuration.state === this.state &&
      character === this.character
  }

  follow(configuration) {
    return new Configuration(this.nextState, this.nextStack(configuration))
  }

  nextStack(configuration) {
    const stack = new Stack(...configuration.stack.getItems())

    stack.pop()
    stack.push(...this.pushCharacters)

    return stack
  }
}

一个NPDA里会有很多规则，我们可以把所有规则封装到一个规则手册里。

class NPDABook {
  constructor(rules) {
    this.rules = rules
  }

  nextConfigurations(configuration, character) {
    const rules = this.findRules(configuration, character)

    return rules.map(rule => rule.follow(configuration))
  }

  findRules(configuration, character) {
    return this.rules.filter(v => v.appliesTo(configuration, character))
  }

  appliesTo(configuration, character) {
    return this.rules.some(v => v.appliesTo(configuration, character))
  }

  followFreeMoves(configurations) {
    return configurations.flatMap(configuration => {
      if (this.appliesTo(configuration, null)) {
        return this.followFreeMoves(this.nextConfigurations(configuration, null))
      }

      return configuration
    })
  }
}

NPDA读取token并使用规则手册不断转移，其中有一些规则不需要读取token，我们称这种规则为自由移动，当NPDA当前配置能应用自由移动规则时，会立即应用自由移动规则转移，之后再读取下一个token。如果NPDA读取token后发现无可用规则，则会被置为阻塞状态，终止运行。

class NPDA {
  constructor(configurations, acceptedStates, ruleBook) {
    this.acceptedStates = acceptedStates
    this.ruleBook = ruleBook
    this.configurations = ruleBook.followFreeMoves(configurations)
  }

  isAccepted() {
    return this.configurations.some(
      configuration => this.acceptedStates.some(v => v === configuration.state)
    )
  }

  readToken(token) {
    const {
      configurations,
      ruleBook,
    } = this
    const character = token.type

    this.configurations = configurations.flatMap(configuration => {
      if (ruleBook.appliesTo(configuration, character)) {
        return ruleBook.followFreeMoves(
          ruleBook.nextConfigurations(configuration, character)
        )
      }

      return configuration.stuck()
    })
  }

  readTokens(tokens) {
    for (const token of tokens) {
      this.readToken(token)
      if (this.configurations.every(v => v.isStuck())) break;
    }
  }
}

最后，把NPDA封装一下，每次语法分析实例化一个NPDA。

class NPDADesign {
  constructor(startState, bottomChar, acceptedStates, rulebook) {
    this.startState = startState
    this.bottomChar = bottomChar
    this.acceptedStates = acceptedStates
    this.rulebook = rulebook
  }

  isAccepted(tokens) {
    const npda = new NPDA(
      [new Configuration(this.startState, new Stack(this.bottomChar))],
      this.acceptedStates,
      this.rulebook
    )

    npda.readTokens(tokens)
    return npda.isAccepted()
  }
}

运行一下，看看效果：

语法分析

规约

仅仅识别一个句子是否语法正确是不够的，我们还需要将四则运算表达式最终规约成一个数。我们将借助抽象语法树（AST）帮我们完成这个任务。AST只包含有用节点：+、-、*、/、n、v。每个节点，我们需要知道它的类型、优先级和值。我们可以这样定义节点：

class Node {
  constructor(token, precedence, value) {
    this.token = token
    this.precedence = precedence
    this.value = value
  }
}

四则运算的AST比较简单，因为+、-、*、/都是二目运算符，所以我们可以用二叉树定义四则运算的AST。

const stringify = () => {
  const lines = []
  const vLine = []

  function replaceChar(str, index, char) {
    return str.substring(0, index) +
    char +
    str.substring(index + 1, str.length)
  }

  return function appendLine(tree, padding = '|—— ', prePadding = '') {
    if (!tree) return ''
    lines.push(`${padding}${tree.token}`)
    if (prePadding) {
      vLine.push([prePadding.length, '|'])
    } else {
      vLine.pop()
    }
    let leftPadding = `${new Array(padding.length + 1).join(' ')}|—— `
    let rightPadding = `${new Array(padding.length + 1).join(' ')} —— `

    vLine.forEach(([index, char]) => {
      leftPadding = replaceChar(leftPadding, index, char)
      rightPadding = replaceChar(rightPadding, index, char)
    })

    appendLine(tree.leftChild, leftPadding, padding)
    appendLine(tree.rightChild, rightPadding)
    return lines.join('\n')
  }
}

class Tree {
  constructor(root) {
    this.root = root
    this.leftChild = null
    this.rightChild = null
  }

  get precedence() {
    return this.root.precedence
  }

  get token() {
    return this.root.value
  }

  toString() {
    return stringify()(this)
  }
}

在语法分析时，我们这样构建AST：

初始状态时，AST为空；
读取token时，我们用这个token实例化一个节点，并用这个节点作为根节点实例化一棵新树。将新树合并到AST。

合并算法：

当AST为空时，使用新树作为AST；
当新树的优先级（树的优先级即其根节点优先级）大于AST优先级时，将AST的右子树替换成AST的右子树与新树合并后的树；
否则，将AST作为新树的左子树，并使用新树作为新的AST。

代码如下：

function compose(oldTree, newTree) {
  if (!oldTree) return newTree

  if (newTree.precedence > oldTree.precedence) {
    oldTree.rightChild = compose(oldTree.rightChild, newTree)
    return oldTree
  }

  newTree.leftChild = oldTree
  return newTree
}

每种树定义好规约方法，最后封装如下：

class Num extends Tree {
  constructor(value, precedence) {
    super(new Node('n', 3 + precedence, value))
  }

  reduce() {
    return this.root.value
  }
}

class Variable extends Tree {
  constructor(value, precedence) {
    super(new Node('v', 3 + precedence, value))
  }

  reduce(env) {
    if (!env || !Object.prototype.hasOwnProperty.call(env, this.root.value)) {
      throw new Error(`Uncaught ReferenceError: ${this.root.value} is not defined`)
    }

    return env[this.root.value]
  }
}

class Plus extends Tree {
  constructor(value, precedence) {
    super(new Node('+', 1 + precedence, value))
  }

  reduce(env) {
    return plus(this.leftChild.reduce(env), this.rightChild.reduce(env))
  }
}

class Minus extends Tree {
  constructor(value, precedence) {
    super(new Node('-', 1 + precedence, value))
  }

  reduce(env) {
    return minus(this.leftChild.reduce(env), this.rightChild.reduce(env))
  }
}

class Multiply extends Tree {
  constructor(value, precedence) {
    super(new Node('*', 2 + precedence, value))
  }

  reduce(env) {
    return multiply(this.leftChild.reduce(env), this.rightChild.reduce(env))
  }
}

class Divide extends Tree {
  constructor(value, precedence) {
    super(new Node('/', 2 + precedence, value))
  }

  reduce(env) {
    return divide(this.leftChild.reduce(env), this.rightChild.reduce(env))
  }
}

function parser() {
  let tree
  let precedence = 0
  return function (token) {
    switch (token.type) {
      case '+':
        tree = compose(tree, new Plus(token.value, precedence))
        break
      case '-':
        tree = compose(tree, new Minus(token.value, precedence))
        break
      case '*':
        tree = compose(tree, new Multiply(token.value, precedence))
        break
      case '/':
        tree = compose(tree, new Divide(token.value, precedence))
        break
      case 'n':
        tree = compose(tree, new Num(token.value, precedence))
        break
      case 'v':
        tree = compose(tree, new Variable(token.value, precedence))
        break
      case '(':
        precedence += 3
        break
      case ')':
        precedence -= 3
        break
      default:
        break
    }

    return tree
  }
}

最后，把parser插入到NPDA，修改后如下：

class NPDADesign {
  constructor(startState, bottomChar, acceptedStates, rulebook, parser) {
    this.startState = startState
    this.bottomChar = bottomChar
    this.acceptedStates = acceptedStates
    this.rulebook = rulebook
    this.parser = parser
  }

  reduce(tokens, env) {
    const npda = new NPDA(
      [new Configuration(this.startState, new Stack(this.bottomChar))],
      this.acceptedStates,
      this.rulebook,
      this.parser()
    )

    npda.readTokens(tokens)

    return npda.reduce(env)
  }
}

class NPDA {
  constructor(configurations, acceptedStates, ruleBook, parser) {
    this.acceptedStates = acceptedStates
    this.ruleBook = ruleBook
    this.configurations = ruleBook.followFreeMoves(configurations)
    this.parser = parser
    this.ast = null
  }

  isAccepted() {
    return this.configurations.some(
      configuration => this.acceptedStates.some(v => v === configuration.state)
    )
  }

  readToken(token) {
    const {
      configurations,
      ruleBook,
    } = this
    const character = token.type

    if (configurations.some(configuration => ruleBook.appliesTo(configuration, character))) {
      this.ast = this.parser(token)
    }

    this.configurations = configurations.flatMap(configuration => {
      if (ruleBook.appliesTo(configuration, character)) {
        return ruleBook.followFreeMoves(
          ruleBook.nextConfigurations(configuration, character)
        )
      }

      return configuration.stuck()
    })
  }

  readTokens(tokens) {
    for (const token of tokens) {
      this.readToken(token)
      if (this.configurations.every(v => v.isStuck())) throw new Error(`语法错误：Unexpected token '${token.value}'`)
    }
  }

  reduce(env) {
    if (!this.isAccepted()) throw new Error('语法错误')
    return this.ast.reduce(env)
  }
}

完成了，看看工作得怎样：

重新定义四则运算
至此，我们完成了重新定义四则运算的工作，终于0.1+0.2=0.3了。我们甚至可以写中文做四则运算，只需要将词法分析稍改一下：

const lexicalAnalyzer = new LexicalAnalyzer([
    new Grammar('n', /(?:[0-9]\.|[1-9][0-9]+\.|\.[0-9]|[0-9])[0-9]*/),
    new Grammar('v', /[A-z_$][A-z0-9_$]*/),
    new Grammar('+', /加/),
    new Grammar('-', /减/),
    new Grammar('*', /乘/),
    new Grammar('/', /除/),
    new Grammar('(', /\(/),
    new Grammar(')', /\)/)
])

我们就可以这样：

中文加法

重新定义加法
众所周知，js做算术运算是不精确的，0.1 + 0.2并不等于0.3。因为公司业务的原因，我们常需要将宝石的价格...
Deep Learning - 第二章-线性代数重要知识点复习-
向量空间为了定义向量空间，首先需要定义向量的加法和标量乘法运算：将集合 V 上的加法定义为一个函数，要求对于 ...
近世代数理论基础18：环的定义及性质
环的定义及性质定义定义：设R为一个非零集合,在R上定义了两种代数运算,分别称为加法和乘法,记作和,且加法和乘法...
向量空间
定义:向量空间是一个集合，该集合的元素都是向量，定义了加法和标量乘法。集合对加法运算封闭，集合中任意向量，他们的...
《情怀与理想》
九零后在重新定义生活的过程中，重新定义了出行方式，重新定义了餐饮，重新定义了创新，重新定义了财富，重新定义了成功，...
2018-06-12
js中浮点型运算方法一：有js自定义函数 //加法函数，用来得到精确的加法结果 //说明：javascript的...
未来之镜
未来之镜一书中将Google工作模式：重新定义一切分解为，重新定义管理，重新定义人才，重新定义团队，重新定义创新和...
重新定义你的职业生涯
许多过去我们习以为常的东西都需要再思考，如重新定义组织、重新定义团队、重新定义工作，重新定义……当这一切被重新定义...
笑来写作课二期笔记
|第二节:一切源自于定义一切源自于定义我们重新定义语言元素我们重新定义写作的目标我们重新定义有效沟通我们重新定...
高等代数理论基础27：矩阵的运算
矩阵的运算加法定义：给定两个矩阵 , 称为A与B的和,记作注： 1.矩阵的加法即矩阵对应元素相加,相加的矩阵...