Sort an expression like "abc(d)(ef)(ghi)"

common.js

import {isArray, cloneDeep} from 'lodash'


export class ExtendableError extends Error {
  constructor(message) {
    super(message)
    this.name = this.constructor.name
    this.message = message
    Error.captureStackTrace(this, this.constructor.name)
  }
}


class _ParseError extends ExtendableError {
  constructor(message) {
    super(message)
    this.name = 'SortedExpression.ParseError'
  }
}


export class SortedExpression {
  constructor(inputString, throwExceptions=false) {
    const _constructor = () => {
      this.parsed = this._parseInput(inputString)
      this.sorted = this._sorted()
    }

    if(throwExceptions) {
      _constructor()
    } else {
      try {
        _constructor()
      }
      catch(err) {
        if(err instanceof SortedExpression.ParseError) {
          console.error(err.message)
        } else {
          throw err
        }
      }
    }
  }

  _findSelected(value, index, list) {
    const selected = (index != null && list != null && list[index+1] === '*')
    if(isArray(value)) {
      return {value: value.map(this._findSelected, this).filter((x) => x), selected}
    }
    else if(value === '*') {
      return null
    }
    else {
      return {value, selected}
    }
  }

  _parseInput(inputString) {
    const string = inputString.trim().toUpperCase()
    let cursor = [[]]

    for(let i in string) {
      let chr = string[i]

      if(chr === '(') {
        let _new = []
        cursor[cursor.length-1].push(_new)
        cursor.push(_new)
        continue
      }

      if(chr === ')') {
        if(cursor.length === 1) {
          throw new SortedExpression.ParseError(
            `Tried to close group before opening. Unexpected: ")" at "${i}"`)
          return
        }
        cursor.pop()
        continue
      }

      cursor[cursor.length-1].push(chr)
    }

    const openGroups = (cursor.length - 1)
    if(openGroups) {
      throw new SortedExpression.ParseError(
        `${openGroups} opened (and not closed) groups. Expecting: ")" at "${string.length}"`)
      return
    }

    return this._findSelected(cursor[0])
  }

  _sorted() {
    let parsed = cloneDeep(this.parsed)

    function _deepSort(obj) {
      if(isArray(obj.value)) {
        obj.value.forEach(_deepSort)
        obj.value.sort((a, b) => {
          let _a, _b
          [_a, _b] = [a, b].map((obj2) => {
            if(isArray(obj2.value)) {
              // Always put lists behind chars and sort by length
              return obj2.value.length + 1000
            }
            return obj2.value.charCodeAt(0)  // a (97) to z (122)
          })
          return _a - _b
        })
      }
    }

    _deepSort(parsed)

    return parsed
  }

  hasSelection() {
    let hasSelection = false

    function _findSelection(obj) {
      if(obj.selected) {
        hasSelection = true
        return false  // break
      }
      if(isArray(obj.value)) {
        obj.value.forEach(_findSelection)
      }
    }

    _findSelection(this.sorted)

    return hasSelection
  }

  toString(selections=true) {
    if(this.sorted == null) {
      return
    }

    function _deepJoin(sum, obj) {
      const sel = (selections && obj.selected ? '*' : '')
      if(isArray(obj.value)) {
        return `${sum}(${obj.value.reduce(_deepJoin, '')})${sel}`
      }
      return sum + obj.value + sel
    }

    const str = _deepJoin('', this.sorted)
    return str.substring(1, str.length-1)
  }
}
SortedExpression.ParseError = _ParseError