四則演算器 (JavaScript ver.)

calculate.js

/*
  四則演算器プログラムです．
  ex.) caluculate('1+2*3'); // => 7
       caluculate('(1+2)*3') // => 9

  * 有理数は未実装
*/


// 演算子たち
var operator = {
  '+': function(x, y) { return x + y; },
  '-': function(x, y) { return x - y; },
  '*': function(x, y) { return x * y; },
  '/': function(x, y) { return x / y; }
};

// 演算子の優先順位たち
var priority = {
  '+': 1,
  '-': 1,
  '*': 2,
  '/': 2
};

// 構文木のコンストラクタ
var Tree = function(val, left, right) {

  var obj = {};

  obj.val = val;
  obj.right = right ? right : null;
  obj.left = left ? left : null;

  obj.isLeaf = function() {
    return obj.right === null && obj.left === null;
  };

  return obj;
};


// 構文木を解釈して計算結果を返す関数
var traverse = function(tree) {
  // 葉の場合は数値型にして自身の値を返す
  if (tree.isLeaf()) return parseInt(tree.val);
  // それ以外の場合は左右の子ノードに自身の演算子を適用する
  return new Tree(operator[tree.val](traverse(tree.left), traverse(tree.right))).val;
};

// 字句解析関数
var tokenizer = function(expr) {
  var reg = /[\-\\+\\*\\/\\(\\)]/g;
  var _expr = expr.replace(reg, ' $& ').trim();
  return _expr.split(/\s+/);
};

// トークンのリストから構文木を組み立てる関数
var parser = function(tokens) {
  if (tokens.length === 0) return null;
  if (tokens.length === 1) return new Tree(tokens.pop());

  // 両端に不要括弧があったら除去
  if (tokens.indexOf('(') === 0 && tokens.lastIndexOf(')') === tokens.length-1) {
      tokens = tokens.slice(1, tokens.length-1);
  }

  var index = indexOfLowerPriority(tokens);
  var left = tokens.slice(0, index);
  var right = tokens.slice(index + 1, tokens.length);

  return new Tree(tokens[index], parser(left), parser(right));
};

// トークンのリストを走査して優先順位が一番小さい演算子のインデックスを取得する関数
var indexOfLowerPriority = function(tokens) {
  var bracketCount = 0;
  var minIndex = 0, minVal = Infinity;

  for (var i = 0; i < tokens.length; i++) {
    var v = tokens[i];
    if (v === '(') bracketCount++;
    if (v === ')') bracketCount--;
    // 括弧の中は無視する
    if (bracketCount === 0 && priority[v] < minVal) {
      minIndex = i;
      minVal = priority[v];
    }
  }

  return minIndex;
};


// 計算式の文字列を受け取って計算結果を返します．
var caluculate = function(expr) {
  var tokenList = tokenizer(expr);
  var tree = parser(tokenList);
  var result = traverse(tree);

  return result;
};


console.log(caluculate('1+2*3'));
console.log(caluculate('(1+2)*3'));

すばらしい

素晴らしいサンプルありがとうございます。

使っていて気づいたのですが、caluculate('(3 + 2) + (1 + 1)') や caluculate('((3))') のような式でエラーが発生しました。

L64 の部分ですが

  if (tokens.indexOf('(') === 0 && tokens.lastIndexOf(')') === tokens.length-1) {
      tokens = tokens.slice(1, tokens.length-1);
  }

下記のようにするのが正しいと思われます。

    while (tokens.indexOf('(') === 0 && tokens.lastIndexOf(')') === tokens.length-1 &&
     indexOfLowerPriority(tokens) == 0) {
      tokens = tokens.slice(1, tokens.length-1);
  }

あと、caluculate は、calculate が正しいスペルですね ^^