JavaScriptで演算子の優先順位を考慮した数式評価を実装する方法

問題

文字列として与えられた数式を受け取り、その計算結果を数値として返すJavaScript関数を作成します。

この関数では、以下の数学演算子をサポートする必要があります。

• 除算 /（浮動小数点除算として扱う）
• 加算 +
• 減算 -
• 乗算 *

演算子は常に左から右へ評価され、* と / は + と - よりも優先的に処理されなければなりません。また、単項マイナス（負数の扱い）にも対応しています。

アルゴリズムのポイント

この実装では、有名な「操車場アルゴリズム（Shunting Yard Algorithm）」の考え方を利用しています。これは、中置記法（人間が普段書く数式の形式）の式を、コンピュータが評価しやすい逆ポーランド記法（後置記法）に変換しながら計算を行う手法です。

主な流れは次のとおりです。

1. 数式から空白を取り除き、1文字ずつ走査します。
2. 数字や小数点はそのまま蓄積し、演算子が出現したタイミングで数値トークンとして出力キューに追加します。
3. 各演算子には優先度（pred）と結合規則（assoc）を定義しておきます。+ と - は優先度2、* と / は優先度3、単項の negate は優先度4です。
4. スタック上の演算子と優先度を比較しながら、適切な順序で出力キューへ移動させることで、優先順位と左結合・右結合のルールを正しく反映します。
5. 最後に、出力キューを先頭から読み込みながらスタックで値を積み上げ・取り出すことで計算結果を求めます。

なお、「-」が単項マイナス（符号反転）なのか二項演算子（減算）なのかは、式の先頭にあるか、直前の文字が演算子や開き括弧かどうかで判定しています。

コード例

以下が実際のコードです。

const exp = '6 - 4';
const findResult = (exp = '') => {
    const digits = '0123456789.';
    const operators = ['+', '-', '*', '/', 'negate'];
    const legend = {
        '+': { pred: 2, func: (a, b) => { return a + b; }, assoc: "left" },
        '-': { pred: 2, func: (a, b) => { return a - b; }, assoc: "left" },
        '*': { pred: 3, func: (a, b) => { return a * b; }, assoc: "left" },
        '/': { pred: 3, func: (a, b) => {
            if (b != 0) { return a / b; } else { return 0; }
        }, assoc: "left" },
        'negate': { pred: 4, func: (a) => { return -1 * a; }, assoc: "right" }
    };
    exp = exp.replace(/\s/g, '');
    let operations = [];
    let outputQueue = [];
    let ind = 0;
    let str = '';
    while (ind < exp.length) {
        let ch = exp[ind];
        if (operators.includes(ch)) {
            if (str !== '') {
                outputQueue.push(new Number(str));
                str = '';
            }
            if (ch === '-') {
                if (ind == 0) {
                    ch = 'negate';
                } else {
                    let nextCh = exp[ind+1];
                    let prevCh = exp[ind-1];
                    if ((digits.includes(nextCh) || nextCh === '(' || nextCh === '-') &&
                        (operators.includes(prevCh) || exp[ind-1] === '(')) {
                        ch = 'negate';
                    }
                }
            }
            if (operations.length > 0) {
                let topOper = operations[operations.length - 1];
                while (operations.length > 0 && legend[topOper] &&
                ((legend[ch].assoc === 'left' && legend[ch].pred <= legend[topOper].pred) ||
                (legend[ch].assoc === 'right' && legend[ch].pred < legend[topOper].pred))) {
                    outputQueue.push(operations.pop());
                    topOper = operations[operations.length - 1];
                }
            }
            operations.push(ch);
        } else if (digits.includes(ch)) {
            str += ch
        } else if (ch === '(') {
            operations.push(ch);
        } else if (ch === ')') {
            if (str !== '') {
                outputQueue.push(new Number(str));
                str = '';
            }
            while (operations.length > 0 && operations[operations.length - 1] !== '(') {
                outputQueue.push(operations.pop());
            }
            if (operations.length > 0) { operations.pop(); }
        }
        ind++;
    }
    if (str !== '') { outputQueue.push(new Number(str)); }
    outputQueue = outputQueue.concat(operations.reverse())
    let res = [];
    while (outputQueue.length > 0) {
        let ch = outputQueue.shift();
        if (operators.includes(ch)) {
            let num1, num2, subResult;
            if (ch === 'negate') {
                res.push(legend[ch].func(res.pop()));
            } else {
                let [num2, num1] = [res.pop(), res.pop()];
                res.push(legend[ch].func(num1, num2));
            }
        } else {
            res.push(ch);
        }
    }
    return res.pop().valueOf();
};
console.log(findResult(exp));

出力結果

2

この例では「6 - 4」を評価しているため、正しく 2 が出力されます。

さらに複雑な式、たとえば「2 + 3 * 4」のような場合でも、乗算が加算より先に評価され、結果は14となります。「(2 + 3) * 4」のように括弧を含む式にも対応しており、括弧内が優先的に計算されます。ゼロ除算の場合は安全のため0を返すようになっている点にも注目してください。