Парсер уравнения + решатель


Вот парсер уравнение, которое я написал. Мой фокус был на читабельность и перспектива добавления новых возможностей в будущем. Поскольку я как-то функциональном стиле, я тоже давал аннотации типов, особенно для более сложных случаев. Я знаю, что это не чисто функциональный, и это было отнюдь не ее целью. Однако я продолжаю верхнего уровня функции полностью чистый, или, по крайней мере, я на это надеюсь.

"use strict";

Object.defineProperties(Array.prototype, {
  head: { get() { return this[0] } },
  tail: { get() { return this.slice(1, this.length) } },
  last: { get() { return this[this.length - 1] } },
  init: { get() { return this.slice(0, this.length - 1) } },
})

const id = x => x
const pipe = (...fns) => arg => fns.reduce((stack, f) => f(stack), arg)

const FN = {
  /** trigonometric functions **/
  sin: f => Math.sin(f),
  cos: f => Math.cos(f),
  tan: f => Math.tan(f),
  sinh: f => Math.sinh(f),
  cosh: f => Math.cosh(f),
  tanh: f => Math.tanh(f),
  asin: f => Math.asin(f),
  acos: f => Math.acos(f),
  atan: f => Math.atan(f),
  asinh: f => Math.asinh(f),
  acosh: f => Math.acosh(f),
  atanh: f => Math.atanh(f),

  deg: f => f * 180/Math.PI,
  rad: f => f * Math.PI/180,

  /** exponentiation etc. **/
  exp: f => Math.exp(f),
  ln: f => Math.log(f),
  lg: f => Math.log10(f),
  sqrt: f => Math.sqrt(f),

  /** misc **/
  fac: i => {
    if (i !== Math.trunc(i)) { return undefined }
    const __fac = _i => _i === 0 ? 1 : _i * __fac(_i - 1)
    return __fac(i)
  },

}

const CONST = {
  e: Math.E,
  pi: Math.PI,
}


// --------------------------- equation linter ------------------------------ //

// :: String -> String
const lintEqn = s => {

  const startWithPlus = s => s.replace(/($|\()(.)/g, `$1 + $2`)

  const condenseOperators = s => {
    while (/[\+\-]\s*[\+\-]/.test(s)) {
      s = s.replace(/\-\s*\-|\+\s*\+/g, '+')
           .replace(/\-\s*\+|\+\s*\-/g, '-')
    }
    return s
  }

  const separateTokens = s => s.split('').reduce(
    (acc, char) => /[\+\-\*\/\^\(\)]/.test(char) ? acc + ` ${char} ` : acc + char
    , '').replace(/\s+/g, ' ')

  const trimWhiteSpace = s => s.replace(/^\s*|\s*$/g, '')


  return pipe(
    startWithPlus,
    condenseOperators,
    separateTokens,
    trimWhiteSpace,
  )('+' + s)
}


// ------------------------------ main logic -------------------------------- //

// :: String -> StkTree 
//    StkTree   = [{op: String, num: StkBranch, fns[(Num -> Num)]}]
//    StkBranch = Num | StkTree
const buildStackTree = s => {

  const isFloat = s => /^ *-?\d+(\.\d+)?([eE][+-]?\d+)? *$/.test(s)
  const isConst = s => CONST.hasOwnProperty(s)
  const isDeg = s => /^\d+(\.\d+)?°$/.test(s)
  const isOp = c => /^[\+\-\*\/\^]$/.test(c)
  const isFn = s => FN.hasOwnProperty(s)

  const freshStack = () => ({
    op: undefined,
    num: undefined,
    fns: [id],
  })

  const acc = {
    tree: [freshStack()],
    targets: [],
  }
  acc.targets.push(acc.tree)

  return s.split(' ').reduce(({tree, targets}, tkn) => {

    const tgtTree = targets.last

    if (tgtTree.last.num !== undefined) {
      tgtTree.push(freshStack())
    }    
    const tgtStk  = tgtTree.last

    if (isOp(tkn)) {
      if (!tgtStk.op) {
        tgtStk.op = tkn
      } else {
        throw new Error(`Redundant operator: ${tkn}`)
      }

    } else if (isFloat(tkn)) {
      tgtStk.num = (parseFloat(tkn))

    } else if (isFn(tkn)) {
      tgtStk.fns.unshift(FN[tkn])

    } else if (isConst(tkn)) {
      tgtStk.num = CONST[tkn]

    } else if (isDeg(tkn)) {
      tgtStk.num = CONST.pi * parseFloat(tkn) / 180


      /** increase Nesting **/
    } else if (tkn === '(') {  

      const newBranch = [freshStack()]
      tgtStk.num = newBranch
      targets.push(newBranch)      

      /** decrease Nesting **/
    } else if (tkn === ')') {

      if (tgtStk.op || tgtStk.num || tgtStk.fns.length > 1) {
        throw new Error (`Denesting with unfinished operation`)
      }

      tgtTree.pop()
      targets.pop()

    } else {
      throw new Error(`Unparsable token: ${tkn}`)
    }

    return {tree, targets}
  }, acc).tree

}


// :: StkTree -> EqnTree
//    StkTree   = [{op: String, num: StkBranch, fns[(Num -> Num)]}]
//    StkBranch = Num | StkTree
//    EqnTree   = [[{b:EqnBranch, e:EqnBranch, efn:(Num -> Num), bfn:(Num -> Num)]]
//    EqnBranch = Num | EqnTree
const buildEqnTree = stackTree => {

  return stackTree.reduce((eqnTree, stk) => {

    const { op, fns } = stk
    const fullfn = pipe(...fns)
    const num = typeof stk.num === 'number' ? stk.num : buildEqnTree(stk.num)

    if (op === '+') {
      eqnTree.push([{ b: num, e: 1, bfn: fullfn, efn: id }])

    } else if (op === '-') {
      eqnTree.push([{ b: -num, e: 1, bfn: fullfn, efn: id }])

    } else if (op === '*') {
      eqnTree.last.push({ b: num, e: 1, bfn: fullfn, efn: id })

    } else if (op === '/') {
      eqnTree.last.push({ b: 1 / num, e: 1, bfn: fullfn, efn: id })

    } else if (op === '^') {
      eqnTree.last.last.e = num
      eqnTree.last.last.efn = fullfn

    } else {
      throw new Error(`Unknown operator: ${op}`)
    }

    return eqnTree
  }, [])
}

// spw = sum of product of powers
const evaluate = spw => {

  if (!(spw instanceof Object)) return spw

  return spw.reduce((s, pw) => {

    return s + pw.reduce((p, w) => {

      const b = typeof w.b === 'number' ? w.b : evaluate(w.b)
      const e = typeof w.e === 'number' ? w.e : evaluate(w.e)
      const {bfn, efn} = w

      return p * (bfn(b) ** efn(e))
    }, 1)

  }, 0)
};


// :: Num -> Num
const precisionRound = (f, p) => {
  const factor = 10 ** p
  return Math.round(f * factor) / factor
}

// :: String -> Num
const parse = s => {

  if (/[!"'§\$&\?,;:#]/.test(s)) {
    throw new Error('You may only enter numbers, operators, or functions')
  }

  const v = pipe(
    lintEqn,
    buildStackTree,
    buildEqnTree,
    evaluate,
  )(s)
  return typeof v === 'number' ? v : NaN
};

Я поставил акцент на том, что это принимает просто о любой строке, пользователь может бросить на нее. Таким образом, эти тесты мой парсер будет удовлетворять как сейчас:

const test = (string, expectation) => {
  const approx = f => precisionRound(f, 15)
  const result = parse(string)
  console.log(approx(result) === approx(expectation))
}

test('1+2',3)
test('1+2+3+4',10)
test('2*3',6)
test('2*3*4*5',120)
test('1+2*3+4',11)
test('1*2+3*4',14)
test('2^3',8)
test('2^3 + 1',9)
test('2^3 * 3',24)
test('1 + 2^3 * 3',25)
test('3^2 + 4*2',17)
test('12 - 3*4',0)
test('12 * 3/4',9)
test('14/7 + 6',8)

test('sin 0',0)
test('sin 0 +1',1)
test('cos 0',1)
test('cos 90°',0)
test('cos 180°',-1)
test('cos 0°',1)
test('ln e',1)
test('1^ln e',1)
test('e^1',Math.E)
test('e^3',Math.E ** 3)
test('3^e',3 ** Math.E)
test('e^e',Math.E ** Math.E)
test('e^ln e',Math.E)
test('ln exp 1',1)
test('lg 1000',3)

test('sin exp 3.721', Math.sin(Math.exp(3.721)))
test('exp sin 3.721', Math.exp(Math.sin(3.721)))
test('4^sin 3.721', 4 ** (Math.sin(3.721)))
test('sin 1 + exp 3.721', Math.sin(1) + Math.exp(3.721))

test(' --4',4)
test('-- 4',4)
test('- - 4',4)
test(' - - 4',4)
test(' -- 4',4)
test('- -4',4)
test('--4',4)
test(' -4',-4)
test('-4',-4)
test(' -4',-4)
test('- 4',-4)

test('1+2', 3)
test('1+2*3+4', 11)
test('4+(1+2)*(3+4)', 25)
test('2^(3*(1+2))', 512)

Моими главными задачами являются читаемость/ремонтопригодность кода. Я не знаю об оптимизации производительности, так что комментарии о том, что будет также интересно. Это мой первый проект на JS, так что любая форма обратной связи высоко ценится.



Комментарии
1 ответ

Ошибки, ошибки и точность.

Это не полноценный обзор, просто указываю на некоторые проблемы с кодом.

fac его багги

Функция факториал глючит и бросит вызов переполнения стека для отрицательных входов, и ошибочные значения для более чем 22. Также я не знаю, почему у вас все подчеркивания, похоже, вы не доверяете язык.


  fac: i => {
if (i !== Math.trunc(i)) { return undefined }
const __fac = _i => _i === 0 ? 1 : _i * __fac(_i - 1)
return __fac(i)
},

Будет лучше

  fac: i => {
if (i !== Math.trunc(i) || i < 0) { return NaN }
if (i > 22) { return undefined }
const fac = i => i === 0 ? 1 : i * fac(i - 1); // No need for underscores
return fac(i);
},

Однако есть только 23 допустимых ответов, так что лучший способ-это через поиск, а не опасные и медленные рекурсивное решение.

 // Declare all solutions outside the function 
const factorials = [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000,51090942171709440000];;

// Much quicker without worrying about being near the top of the call stack
fac: i => factorials[i] === undefined ? i > 22 ? undefined : NaN : factorials[i],

Точность тестирования несовершенна...

...потому что точность функция несовершенна. JavaScript используется с плавающей запятой, но вы обращаетесь с ними как с фиксированной точкой.

Рассмотрим "0.00000000000000013 * 2" (маленькое значение 1.3e-16) JavaScript будет счастливо возвращает правильное значение 2.6e-16

Я думаю, что вы пытаетесь исправить такие проблемы, как "0.00000000000000013 ** 2" JavaScript, которые будут вычислять будет 1.6899999999999998e-32 который имеет погрешность в 2е-48

Оба примера код будет круглый ноль, и тест будет пройден, даже если он полностью начинку операторы например approx(1.3e-16 * 2) === approx(1.3e-16 ** 2) это true что на самом деле на 16 порядков.

Вы лучше обеспечить функциональный тест с помощью JavaScript расчетную стоимость. Не тест с известным результатом test("2 * 3", 6) а расчетный результат test("2 * 3", 2 * 3) и удалить вызовы precisionRound .

Постоянная Эйлера

Глядя на код, это кажется мне, что значения, введенные в качестве экспонентов будут неправильно оценены (возможно бросить) например parse("1.2e-16 * 2") не получится. Хотя я не уверен, я не запустить код?

Триминг

В JavaScript есть функция обрезки, поэтому нет необходимости trimWhiteSpace

Таким образом


  return pipe(
startWithPlus,
condenseOperators,
separateTokens,
trimWhiteSpace,
)('+' + s)

становится

  return pipe(
startWithPlus,
condenseOperators,
separateTokens,
)('+' + s).trim()

Плюс +?

Почему добавить плюс? ваш код может легко добавить плюс в buildStackTree

Лучше parseFloat

Лучший способ разобрать поплавок Number(numberAsString) потому что parseFloat пытается исправить значения при создании Number не будет.

 console.log(parseFloat("10x")); // >> 10
console.log(Number("10x")); // >> NaN

console.log(parseFloat("10.0.0")); // >> 10
console.log(Number("10.0.0")); // >> NaN

Нравится JavaScript его

Посмотрите в предыдущем разделе, когда JavaScript разбирает строковое значение "10.0.0" не throw new Error("Too many decimal points!") а он возвращается NaN

Вы бросаете, где лучше Вариант NaN. Результаты искаженного уравнения в значение, которое не является числом, а не множеством ошибок, которые должны быть в ловушке.

Лично я бы убрал все проверки на ошибки, и пусть на JavaScript бросят, если он нужен (не думаю, что это было в данном случае), по большей части он вернется NaN на свои собственные.

И, Пожалуйста,...

...добавить точку с запятой ';' и снизить риск ошибки.

1
ответ дан 7 февраля 2018 в 12:02 Источник Поделиться