calculator string parser

calculator.coffee

# Expr ::= Term ('+' Term | '-' Term)*
# Term ::= Factor ('*' Factor | '/' Factor)*

# Factor ::= ['-'] (Number | '(' Expr ')')

# Number ::= Digit+

log = console.log.bind(console)

tokenize = (str)->
    cur = prev = 0
    pos = []
    while cur < str.length
        if str[cur].match(/[\+\-\*\/\(\)]/)
            pos.push [prev, cur] 
            prev = cur+1
        cur = cur + 1

    pos .push [prev, str.length]

    tokens = []
    _.each pos, (p)->
        tokens.push str[p[0]...p[1]]
        if p[1] < str.length
            tokens.push str[p[1]]

    tokens = _.compact tokens
    return tokens

class Parser   
    constructor: (@tokens) ->

    peek: ->
        @tokens[0] || null
    next: ->
        if @tokens.length > 0 then @tokens.shift() else null
    parse_expr:->
        term = @parse_term()
        while 1 
            peek = @peek()

            if peek is "+" and @next()
                term = term + @parse_term()

            else if peek is "-" and @next()
                term = term - @parse_term()

            else if peek is null
                return term

            else 
                throw "malformed"
    parse_term: ->
        factor = @parse_factor()
        while 1 
            peek = @peek()

            if peek is "*" and @next()
                factor = factor * @parse_factor()

            else if peek is "/" and @next()

                n = @parse_factor()
                if n is 0
                    throw "divide by zero"
                else
                    factor = factor / n
            else 
                return factor
    parse_factor: ->
        negate = if @peek() is "-" and @next() then -1 else 1

        if @peek() is "(" and @next()
            expr = []
            throw "incomplete brackets" if @tokens.indexOf(")") is -1

            expr.push next while (next = @next()) isnt ")"

            p = new Parser(expr)

            return negate * p.parse_expr() 

        else if not isNaN(parseFloat @peek())
            return negate * parseFloat @next()
        else
            throw "malformed expression"


test = (expr)->
    tokens = tokenize(expr)
    parser = new Parser(tokens)
    result = parser.parse_expr()
    log expr, "=", result, if result is eval(expr) then "correct!" else "wrong"

test "10/12"
test "-10/13-(12.3-3*2)/2*3+3-2*2.2"
test "10/1-2*3-(12.3-3*2)*2*3+3-2*2.2"

calculator.js

// for brackets
function parse(input, start) {
  let str = ''
  for (let i=start;i<input.length;i++) {
    if (input[i] === '(') {
      const [val, j] = parse(input, i+1)
      i = j
      str += val
    } else if (input[i] === ')') {
      return [evaluate(str), i]
    } else {
      str += input[i]
    }
  }
  return [evaluate(str), input.length - 1]
}

// no brackets now
function evaluate(str) {
  const re = /[-]?\d+(\.\d+)?/g
  const tokens = []
  let match = null
  while ((match = re.exec(str))!==null) {
    tokens.push(match[0])
    if (match.index + match[0].length < str.length) {
      re.lastIndex += 1
      tokens.push(str[match.index + match[0].length])
    }
  }

  let i = 0
  // calculate * and / first
  while (i< tokens.length) {
    if (i < tokens.length -1) {
      let op = tokens[i+1]
      if (op === '*' || op === '/') {
        tokens.splice(i, 3, doMath(tokens[i], op, tokens[i+2]))
      } else {
        i+=2
      }
    } else {
      break
    }
  }
  // calcualte + and - then
  while (tokens.length) {
    if (tokens.length === 1) {
      return tokens[0]
    }
    const [a, op, b] = [tokens.shift(), tokens.shift(), tokens.shift()]
    tokens.unshift(doMath(a, op, b))
  }
  return res

  function doMath(a, op, b) {
    a = Number(a)
    b = Number(b)

    switch (op) {
      case '+':
        return a + b
      case '-':
        return a - b
      case  '*':
        return a * b
      case '/':
        return a / b
      default:
        throw new Error('Unrecognized operator')
    }
  }
}

function calc(input) {
  const s = input.replace(/\s/g, '')
  return parse('(' + s + ')', 1)[0]
}