calculator.ts

calculator.ts

type Pattern<T> = (i: number, s: string) => null | [number, T]

interface TokenBase {
  type: string
}

interface NumberToken extends TokenBase {
  type: "number",
  value: number
}

interface OperatorToken extends TokenBase {
  type: "operator",
  value: string,
  priority: number
}

type Token = NumberToken | OperatorToken
type Lexed = (Token | Lexed)[]

function lex(src: string, bracket?: boolean, i = 0): [number, Lexed] | null {
  const res:Lexed = []
  let currentBracket:Lexed | null = null

  const decimal:Pattern<Token> = (i,s) => {
    const m = s.slice(i).match(/^(?:[1-9][0-9]+|[0-9])(?:\.[0-9]+)?/)
    return m ? [
      i + m[0].length,
      {
        type: "number",
        value: parseFloat(m[0])
      }
    ] : null
  }

  const operator:Pattern<Token> = (i,s) => {
    const m = s.slice(i).match(/^(?:\+|-|\*|\/)/)
    return m ? [
      i + m[0].length,
      {
        type: "operator",
        value: m[0],
        priority: {"+": 0, "-": 0, "*": 1, "/": 1}[m[0]] || 0
      }
    ] : null
  }

  for (;i < src.length;){
    const tkn = decimal(i, src) || operator(i, src)
    if (tkn == null){
      if (src[i] == "("){
        const tkns = lex(src, true, i+=1)
        if (!tkns)return null;
        i = tkns[0];
        (currentBracket || res).push(tkns[1])
      }else if (bracket && src[i] == ")"){
        return [i+=1, res]
      }else{
        const m = src.slice(i).match(/^\s+/)
        if (!m)return null;
        i += m[0].length
      }
    }else{
      i = tkn[0];
      (currentBracket || res).push(tkn[1])
    }
    const prevOperator = (res.at(-2))
    if (((prev:any): prev is OperatorToken => (prev)?.type == "operator")(prevOperator)){
      if ((res.at(-4) as any)?.type == "operator" && (res.at(-4) as any).priority > prevOperator.priority){
        const operatorI = res.length - 5
        res.splice(operatorI,0, res.splice(operatorI,3))
      }else if ((res.at(-4) as any)?.type == "operator" && (res.at(-4) as any).priority < prevOperator.priority){
        const operatorI = res.length - 3
        res.splice(operatorI,0, res.splice(operatorI,3))
      }
    }
  }
  if (res.length == 0)return null;
  return [i, res];
}

function calc(lexed?: Lexed) {
  if (lexed == null)return null;
  const stack: number[] = []

  function evaluate(x: Token | Lexed | undefined){
    if (x == null)return null;
    if (x instanceof Array){
      const res = calc(x)
      if (res == null)return null;
      stack.push(res)
      return res
    }else if (x.type == "number"){
      stack.push(x.value)
      return x.value
    }else if (x.type == "operator"){
      const v = evaluate((lexed as Lexed).shift())
      if (!v || typeof v != "number")return null;
      stack.pop() // スタックに残ったvの値を捨てる
      if (x.value == "+"){
        stack.push((stack.pop() ?? 0) + v)
      }else if (x.value == "-"){
        stack.push((stack.pop() ?? 0) - v)
      }else if (x.value == "*"){
        stack.push((stack.pop() ?? 0) * v)
      }else if (x.value == "/"){
        stack.push((stack.pop() ?? 0) / v)
      }else return null;
      return stack.at(-1)
    }
    return 0
  }

  for (let i = 0; i < lexed.length; i++){
    const x = lexed[i]
    if (x instanceof Array){
      if (!evaluate(x))return null;
      lexed.splice(i, 1, {type: "number", value: stack.pop() ?? 0})
    }
  }
  while(lexed.length){
    const x = lexed.shift()
    const res = (evaluate(x))
    if (res == null)return null;
  }
  return stack.at(-1)
}

const l = lex("1 + 3 * (2 + 1)")?.[1]
console.log(calc(l))