以我所主，为我所用

公式编辑器

10分钟阅读

  • 如何设计公式解析引擎以确保高效的字符串解析与逻辑计算? 核心答案关键词:
    • 语法树(AST)
    • 正则表达式、
    • 递归下降解析
    • 词法分析
    • 运算符优先级处理
    • 缓存机制
  • TDD|TDD]在公式编辑器中的应用,具体带来了哪些好处? 核心答案关键词:
    • 单元测试、代码质量保证、bug 提前捕获、测试覆盖率提升、重构安全性、及时暴露问题。把 TDD 这个文件说明白即可，核心还是团队协作
  • 实时函数信息提示功能是如何设计的?如何保证提示信息的准确性和性能? 核心答案关键词:
    • 异步数据加载
    • 缓存机制
    • 动态提示
    • 函数语法分析
    • 性能优化(debounce)
    • TypeScript 类型定义
  • 如何通过模块化封装提高组件复用性,具体在项目中采取了哪些技术措施? 核心答案关键词: 高阶组件(HOC)、函数式编程、组件解耦、通用库、props/slots 传递、单一职责原则
  • 在自动化发布流程中,如何设计 CI/CD 流程以保证快速且稳定的部署? 核心答案关键词: GitHub Actions、自动化部署、持续集成、持续交付、版本控制、回滚机制
  • 如何处理公式输入的错误提示与校验,确保用户输入的准确性? 核心答案关键词: 表单验证、即时反馈、正则表达式校验、错误提示组件、用户体验优化、输入校验逻辑

下面的只有部分有做过，不是很好写

  • 如何确保公式计算的正确性和精确度?如何解决大数据量计算问题? 核心答案关键词: 数学精度控制(BigDecimal)、异步计算、Web Worker 使用、缓存策略、性能瓶颈处理
  • 公式编辑器的性能优化方向有哪些?如何避免因公式计算导致的性能问题? 核心答案关键词: 计算延迟(debounce)、懒计算、Web Worker 分离计算、虚拟 DOM、计算缓存

首先构造最简单的场景，只管测试通过

class FormulaCalculator {
  calculate(formula: string):number {
    if(formula.startsWith('SUM')){
      const args = formula.substring('SUM'.length + 1,formula.length-1).split(',').map(Number)
      return args.reduce((prev,curt)=>prev+curt,0)
    }
 
    if(formula.startsWith('AVERAGE')){
      const args = formula.substring('AVERAGE'.length + 1,formula.length - 1).split(',').map(Number)
      return args.reduce((prev,curt)=>prev+curt,0)/args.length
    }
    return 0
  }
}
 
describe('formula', () => {
  const calculator = new FormulaCalculator();
  it('should calculate with SUM', () => {
    expect(calculator.calculate('SUM(1,2)')).toEqual(3);
  });
 
  it('should calculate with average',()=>{
    expect(calculator.calculate('AVERAGE(1,2)')).toEqual(1.5)
  })
});

现在我们有了多个 if 条件，这是一个明显的代码坏味道，我们可以快速重构成如下样子

class Functions {
  static SUM(args: number[]) {
    return args.reduce((prev, curt) => prev + curt, 0);
  }
 
  static AVERAGE(args: number[]) {
    return args.reduce((prev, curt) => prev + curt, 0) / args.length;
  }
}
 
class FormulaCalculator {
  calculate(formula: string): number {
    if (formula.startsWith('SUM')) {
      const args = formula
        .substring('SUM'.length + 1, formula.length - 1)
        .split(',')
        .map(Number);
      return Functions['SUM'](args);
    }
 
    if (formula.startsWith('AVERAGE')) {
      const args = formula
        .substring('AVERAGE'.length + 1, formula.length - 1)
        .split(',')
        .map(Number);
      return Functions['AVERAGE'](args);
    }
    return 0;
  }
}
 
describe('formula', () => {
  const calculator = new FormulaCalculator();
  it('should calculate with SUM', () => {
    expect(calculator.calculate('SUM(1,2)')).toEqual(3);
  });
 
  it('should calculate with average', () => {
    expect(calculator.calculate('AVERAGE(1,2)')).toEqual(1.5);
  });
});

在这里，我们发现，两个判断逻辑，除了函数名本身以外，并没有任何区别，如果要进行重构，我们所有的函数计算步骤都可以划分为

  1. 解析函数名称
    • 函数名称只能为大写字母组合
    • 函数名称后面只能跟 ’(’
  2. 解析参数列表
    • 参数列表只能在 ’()’ 包裹
    • 通过正则表达式识别数字类型参数
  3. 转义参数列表
  4. 获取函数名称对应的计算逻辑

在这里我们会发现，在 TDD 的开发模式下，我们即使一开始并不知道的词法分析和语法分析的概念，但是随着任务功能的划分，功能的实现会天然的贴近词法分析与语法分析。

如果是一个基础不那么好的开发者，并没有进行词法分析和语法分析的代码技术能力的呢，那就去寻求帮助，TDD 的任务列表，以及测试用例，就是一个极好的沟通上下文，可以最快速准确地，向团队中的其他人，表明“自己哪里不会，需要哪些帮助”。这其实体现了我们平时真正的开发成本，并不在与要花多少时间写出功能，更多的是要花多少时间

我们可以先去实现词法分析部分

export class Lexer {
  analyse(source: Iterator<string>) {
    const tokens: Token[] = []
    const it = new PeekIterator(source, '\0')
 
    while (it.hasNext()) {
      const c = it.next()
      if (c === '\0') {
        break
      }
      const lookahead = it.peek()
 
      if (c === ' ' || c === '\n' || c === '\r') {
        continue
      }
 
      if (c === '(' || c === ')') {
        tokens.push(new Token(TokenType.BRACKET, c))
        continue
      }
 
      if (c === '"' || c === "'") {
        it.putBack()
        tokens.push(Token.makeString(it))
        continue
      }
 
      if (AlphabetHelper.isLetter(c)) {
        it.putBack()
        const lastToken = tokens[tokens.length - 1] || null
        const newToken = Token.makeVarOrFunction(it)
        if(newToken.getType() !== TokenType.FUNCTION) {
          tokens.push(newToken)
          continue
        } else if(lastToken && lastToken.getType() !== TokenType.OPERATOR && lastToken.getValue()!=='('){
          throw new FormulaError({'errCode':ERRORCode.UNEXPECTED_FUNCTION_NAME})
        } else {
          tokens.push(newToken)
          continue
        }
      }
 
      if (AlphabetHelper.isNumber(c)) {
        it.putBack()
        tokens.push(Token.makeNumber(it))
        continue
      }
 
	  throw LexicalException.fromChar(c)
    }
    return tokens
  }
}

词法分析缓存机制设计：

export class PeekIterator<T> {
  private it: Iterator<T>
  private stackPutBacks = new LinkedList()
  private queueCache = new LinkedList()
  private endToken: T = null
  constructor(it: Iterator<T>, endToken?: T) {
    this.it = it
    // 需要putBack的元素
    this.stackPutBacks = new LinkedList()
 
    // 基于时间窗口的缓存
    this.queueCache = new LinkedList()
 
    if (endToken) {
      this.endToken = endToken
    }
  }
 
  peek(): T {
    if (this.stackPutBacks.length > 0) {
      return this.stackPutBacks.tail
    }
 
    const val = this.next()
    this.putBack()
    return val
  }
 
  // 缓存:A -> B -> C -> D
  // 放回:D -> C -> B -> A
  putBack(): void {
    if (this.queueCache.length > 0) {
      this.stackPutBacks.push(this.queueCache.pop())
    }
  }
 
  hasNext(): boolean {
    return !!this.endToken || !!this.peek()
  }
 
  next(): T {
    let val = null
 
    if (this.stackPutBacks.length > 0) {
      val = this.stackPutBacks.pop()
    } else {
      val = this.it.next().value
      if (val === undefined) {
        const tmp = this.endToken
        this.endToken = null
        val = tmp
      }
    }
 
    // 处理缓存
    while (this.queueCache.length > CACHE_SIZE - 1) {
      this.queueCache.shift()
    }
    this.queueCache.push(val)
 
    return val
  }
}

语法树解析，先构造基本的语法节点结构

export abstract class ASTNode {
  /** 树结构 */
  protected children: ASTNode[] = []
  protected parent: ASTNode = null
  /** 关键信息 */
  protected lexeme: Token = null // 词法单元
  protected type: ASTNodeType = null // 节点类型
  protected returnType:ASTNodeReturnType = null // 节点返回值类型
  protected label: string = null // 备注（标签）
  constructor(
    type: ASTNodeType = null,
    label: string = null
  ) {
    this.type = type
    this.label = label
  }
 
  getChild(index: number) {
    return this.children[index] || null
  }
 
  addChild(node: ASTNode) {
    node.parent = this
    this.children.push(node)
  }
 
  getChildren() {
    return this.children
  }
 
  getParent() {
    return this.parent
  }
 
  setLexeme(token: Token) {
    this.lexeme = token
  }
 
  getLexeme() {
    return this.lexeme
  }
 
  setLabel(label: string) {
    this.label = label
  }
 
  getLabel() {
    return this.label
  }
 
  setType(type: ASTNodeType) {
    this.type = type
  }
 
  getType() {
    return this.type
  }
 
}

至于运算符优先级，我们通过二维表格处理

export const PriorityTable: (OperatorType | (string & {}))[][] = [
  [OperatorType.MULTIPLICATION, OperatorType.DIVISION, OperatorType.REMAINDER],
  [OperatorType.ADDITON, OperatorType.SUBTRACTION],
  [
    OperatorType.GREATER_THAN,
    OperatorType.LESS_THAN,
    OperatorType.GREATER_THAN_OR_EQUAL,
    OperatorType.LESS_THAN_OR_EQUAL,
  ],
  [OperatorType.EQUALITY, OperatorType.INEQUALITY],
];

最终的解析

export class Expr extends ASTNode {
  constructor() {
    super();
  }
 
  static fromToken(type: ASTNodeType, token: Token) {
    const expr = new Expr();
    expr.label = token.getValue();
    expr.lexeme = token;
    expr.type = type;
    return expr;
  }
 
  static parse(it: PeekTokenIterator) {
    return Expr.E(it, 0);
  }
 
  static E(it: PeekTokenIterator, k: number): ASTNode {
    if (k < PriorityTable.length - 1) {
      return Expr.combine(
        it,
        () => Expr.E(it, k + 1),
        () => Expr.E_(it, k)
      );
    } else {
      return Expr.race(
        it,
        () =>
          Expr.combine(
            it,
            () => Expr.F(it),
            () => Expr.E_(it, k)
          ),
        () =>
          Expr.combine(
            it,
            () => Expr.U(it),
            () => Expr.E_(it, k)
          )
      );
    }
  }
 
  // E_(k) -> op(k) E(k+1) E_(k) | ε
  static E_(it: PeekTokenIterator, k: number) {
    const token = it.peek();
    const value = token.getValue();
 
    if (PriorityTable[k] && PriorityTable[k].indexOf(value) !== -1) {
      it.nextMatchByValue(value);
      const expr = Expr.fromToken(ASTNodeType.BINARY_EXPR, token);
      expr.addChild(
        Expr.combine(
          it,
          () => Expr.E(it, k + 1),
          () => Expr.E_(it, k)
        )
      );
 
      return expr;
    }
    return null;
  }
 
  static U(it: PeekTokenIterator) {
    const token = it.peek();
    const value = token.getValue();
 
    if (value === "(") {
      it.nextMatchByValue("(");
      const expr = Expr.parse(it);
      it.nextMatchByValue(")");
      return expr;
    } else if (value === "++" || value === "--" || value === "!") {
      const t = it.peek();
      it.nextMatchByValue(value);
 
      const expr = Expr.fromToken(ASTNodeType.UNARY_EXPR, t);
      expr.addChild(Expr.parse(it));
      return expr;
    }
    return null;
  }
 
  static F(it: PeekTokenIterator) {
    const factor = Factor.parse(it);
    if (factor === null) {
      return null;
    }
    if (it.hasNext() && it.peek().getValue() === "(") {
      return CallExpr.parse(it, factor);
    }
    return factor;
  }
 
  static combine(it: PeekTokenIterator, funcA: () => any, funcB: () => any) {
    if (!it.hasNext()) {
      return null;
    }
    const a = funcA();
    if (a === null) {
      return null;
      // return it.hasNext() ? funcB() : null
    }
    const b = it.hasNext() ? funcB() : null;
    if (b === null) {
      return a;
    }
 
    const expr = Expr.fromToken(ASTNodeType.BINARY_EXPR, b.lexeme);
    expr.addChild(a);
    expr.addChild(b.getChild(0));
    return expr;
  }
 
  static race(it: PeekTokenIterator, funcA: () => any, funcB: () => any) {
    if (!it.hasNext()) {
      return null;
    }
    const a = funcA();
    if (a === null) {
      return funcB();
    }
    return a;
  }
}

关系图谱

反向链接