Skip to content

Mitaka Club

四則演算を再帰下降で書く(TypeScript)

TypeScript の練習がてら先日 Rust で書いた四則演算パーサーを TypeScript で書き直した。TypeScript はほぼ書いたことないしそもそも Node(ES6) もそれほどすらすら書けるわけではないのでもっといい書き方ありそう。

テストをどう書くのかが定番を知らないので assert を使ったが、一つ fail すると後続処理は行われないようだったのでちょっと使い勝手が悪かった。

エラーハンドリングも同様に定番を知らないので、参考に記載の記事を参考にしつつ戻り値に Union Type を使って Error オブジェクトを返すようにした。

import assert from "assert";

class SyntaxError extends Error {}
class UnreachableError extends Error {}

function lexer(s: string): string[] | SyntaxError {
  let ret = [];
  let num = [];

  for (const c of s.split('')) {
    if (c === '+' || c === '-' || c === '*' || c === '/' || c === '(' || c === ')') {
      if (num.length !== 0) {
        ret.push(num.join(''));
        num = [];
      }
      ret.push(c);
    } else if (c === ' ') {
      if (num.length !== 0) {
        ret.push(num.join(''));
        num = [];
      }
    } else if (!Number.isNaN(Number.parseFloat(c))) {
      num.push(c);
      continue;
    } else {
      return new SyntaxError();
    }
  }

  if (num.length !== 0) {
    ret.push(num.join(''));
  }

  return ret;
}

assert.deepEqual(lexer('12 + 4'), ['12', '+', '4']);
assert.deepEqual(lexer('12 - 4'), ['12', '-', '4']);
assert.deepEqual(lexer('12 * 4'), ['12', '*', '4']);
assert.deepEqual(lexer('12 / 4'), ['12', '/', '4']);
assert.deepEqual(lexer('(11 + 1) * 4'), ['(', '11', '+', '1', ')', '*', '4']);

class Parser {
  idx: number;
  tokens: string[];

  constructor(tokens: string[]) {
    this.idx = 0;
    this.tokens = tokens;
  }

  consume() {
    this.idx += 1;
  }

  number(): number | UnreachableError {
    let num = Number.parseFloat(this.tokens[this.idx]);
    if (Number.isNaN(num)) {
      return new UnreachableError();
    } else {
      this.consume();
      return num;
    }
  }

  factor(): number | UnreachableError {
    const token = this.tokens[this.idx];
    if (!Number.isNaN(Number.parseFloat(token))) {
      return this.number();
    }

    if (token === '(') {
      this.consume();
      const expr = this.expr();
      if (expr instanceof UnreachableError) {
        return expr;
      }
      
      const token = this.tokens[this.idx];
      if (token === ')') {
        this.consume();
        return expr;
      } else {
        return new UnreachableError();
      }
    }

    return new UnreachableError();
  }

  term(): number | UnreachableError {
    let left = this.factor();
    if (left instanceof UnreachableError) {
      return left;
    }

    while (this.idx < this.tokens.length) {
      const op = this.tokens[this.idx];
      if (op === '*' || op === '/') {
        this.consume();
      } else {
        break
      }

      const right = this.factor();
      if (right instanceof UnreachableError) {
        return right;
      }
      if (op === '*') {
        left *= right;
      } else if (op === '/') {
        left /= right;
      }
    }

    return left;
  }

  expr(): number | UnreachableError {
    let left = this.term();
    if (left instanceof UnreachableError) {
      return left;
    }

    while (this.idx < this.tokens.length) {
      const op = this.tokens[this.idx];
      if (op === '+' || op === '-') {
        this.consume();
      } else {
        break;
      }

      const right = this.term();
      if (right instanceof UnreachableError) {
        return right;
      }
      if (op === '+') {
        left += right;
      } else if (op === '-') {
        left -= right;
      }
    }

    return left;
  }
}

assert.equal(new Parser(['12', '+', '4']).expr(), 16);
assert.equal(new Parser(['12', '-', '4']).expr(), 8);
assert.equal(new Parser(['12', '*', '4']).expr(), 48);
assert.equal(new Parser(['12', '/', '4']).expr(), 3);
assert.equal(new Parser(['12', '+', '4', '*', '3']).expr(), 24);
assert.equal(new Parser(['12', '-', '4', '-', '3']).expr(), 5);
assert.equal(new Parser(['(', '12', '+', '4', ')', '*', '3']).expr(), 48);

参考