逆ポーランド記法

dentaku.js

/**
 * Word型
 * @typedef {object} Word
 * @prop {string} type - ワードの種類
 * @prop {number} priority? - ワード(演算子)の優先度(大きいほど高い)
 * @prop {number} value? - ワード(数値)の値
 */


/**
 * Expr型
 * @typedef {Word[]} Expr
 */


/**
 * 文字列をワードに変換
 * @param {string} e
 * @return {Word}
 */
const getWord = (e) => {
    if (e.match(/^[0-9]+$/g)) {
        return { type: 'Number', value: Number(e) };
    } else if (e === '+') {
        return { type: 'Plus', priority: 2 };
    } else if (e === '-') {
        return { type: 'Minus', priority: 2 };
    } else if (e === '*') {
        return { type: 'Mul', priority: 1 };
    } else if (e === '/') {
        return { type: 'Div', priority: 1 };
    } else if (e === '(') {
        return { type: 'LP', priority: 3 };
    } else if (e === ')') {
        return { type: 'RP', priority: 3 };
    } else {
        throw new Error(`wrong chars "${e}": [0-9]+|[+-*/()]`);
    }
}


/**
 * 演算を実行
 * @param {Word} op
 * @param {Word} a
 * @param {Word} b
 * @return {Word}
 */
const evaluator = (op, a, b) => {
    let v = 0;
    if (op.type === 'Plus') {
        v = a.value + b.value;
    } else if (op.type === 'Minus') {
        v = a.value - b.value;
    } else if (op.type === 'Mul') {
        v = a.value * b.value;
    } else if (op.type === 'Div') {
        v = Math.floor(a.value / b.value);
    } else {
        throw new Error(`undefined eval "${op.type}"`);
    }
    return { type: 'Number', value: v };
}


/**
 * 中置記法のstringから空白区切りでWordの配列に変換
 * @param {string} line
 * @return {Expr}
 */
const getInfixExpr = (line) => line.split(' ').map(e => getWord(e))


/**
 * 中置記法から後置記法に変換する
 * @param {Expr} expr
 * @return {Expr}
 */
const infixExpr2postfixExpr = (expr) => {
    const p = [], s = [];
    for (const w of expr) {
        if (w.type === "Number") {
            p.push(w);
        } else if (w.type === "LP") {
            s.push(w);
        } else if (w.type === "RP") {
            while (s.length > 0) {
                const v = s.pop();
                if (v.type === "LP") {
                    break;
                }
                p.push(v);
            }
        } else {
            while (s.length > 0) {
                const v = s.pop();
                if (v.priority > w.priority) {
                    s.push(v);
                    break;
                } else {
                    p.push(v);
                }
            }
            s.push(w);
        }
    }
    while (s.length > 0) {
        p.push(s.pop());
    }
    return p;
};


/**
 * 後置記法の式を計算する
 * @param {Expr} expr
 * @return {Word}
 */
const calcPostfixExpr = (expr) => {
    const s = [];
    for (const w of expr) {
        if (w.type === "Number") {
            s.push(w);
        } else {
            const b = s.pop(), a = s.pop();
            s.push(evaluator(w, a, b));
        }
    }
    return s.pop();
}

/**
 * ワード(数値)の値を取り出す
 * @param {Word} word
 */
const getValue = (word) => word.value;


/**
 * main関数
 */
(async () => {
    const reader = require('readline').createInterface({ input: process.stdin });
    for await (const line of reader) {
        console.log(getValue(calcPostfixExpr(infixExpr2postfixExpr(getInfixExpr(line)))));
    }
    reader.close();
})().catch(e => console.log(e));

dentaku.lmn

functional.use.
line = io.read_line(io.stdin, I), io.free_port(I).
line(Str) :- words = filter(lambda(X, X>32), string.explode(Str)).


phase1.
getInfixExpr = {
  W = [40 | T] :- W = [word(lp, priority(3)) | T].
  W = [41 | T] :- W = [word(rp, priority(3)) | T].
  W = [43 | T] :- W = [word(plus, priority(2)) | T].
  W = [45 | T] :- W = [word(minus, priority(2)) | T].
  W = [42 | T] :- W = [word(mul, priority(1)) | T].
  W = [47 | T] :- W = [word(div, priority(1)) | T].
  W = [N | T] :- N1=N-48 | W = [word(number, value(N1)) | T].
}.
getInfixExpr({$p, @r}), words(X), phase1 
  :- ground(X) |  getInfixExpr({$p, words(X), @r}).
getInfixExpr({$p, words(X),  @r}/) 
  :- ground(X) |  getInfixExpr({$p, @r}), words(X), phase2. 



infixExpr2postfixExpr = {
  p = [], s = [].
  
  forloop =  {
    rploop = {
      p = A, s = [word(lp, priority(N)) | B], flag 
        :- ground(A), ground(B), int(N) | p = A, s = B.
      p = A, s = [word(plus, priority(N)) | B], flag 
        :- ground(A), ground(B), int(N) | p = [word(plus, priority(N)) | A], s = B, flag.
      p = A, s = [word(minus, priority(N)) | B], flag 
        :- ground(A), ground(B), int(N) | p = [word(minus, priority(N)) | A], s = B, flag.
      p = A, s = [word(mul, priority(N)) | B], flag 
        :- ground(A), ground(B), int(N) | p = [word(mul, priority(N)) | A], s = B, flag.
      p = A, s = [word(div, priority(N)) | B], flag 
        :- ground(A), ground(B), int(N) | p = [word(div, priority(N)) | A], s = B, flag.
    }.
      
    elseloop = {
      word(W, priority(N)), p = A, s = [word(V, priority(M)) | B], flag 
        :- ground(W), ground(V), int(N),int(M), M>N | word(W, priority(N)), p = A, s = [word(V, priority(M)) | B].
      word(W, priority(N)), p = A, s = [word(V, priority(M)) | B], flag 
        :- ground(W), ground(V), int(N),int(M), M=<N | word(W, priority(N)), p = [word(V, priority(M)) | A], s = B, flag.
    }.
  
    p = A, s = B, words([word(number, value(N)) | T]) 
      :- ground(A),ground(B), ground(T), int(N) | p = [word(number, value(N)) | A], s = B, words = T.
    p = A, s = B, words([word(lp, priority(N)) | T]) 
      :- ground(A),ground(B), ground(T), int(N) | p = A, s = [word(lp, priority(N)) | B], words = T.
    p = A, s = B, words([word(rp, priority(N)) | T]), rploop={$x, @r} 
      :- ground(A),ground(B), ground(T), int(N) | rploop={$x, p = A, s = B, flag, @r}, words = T.
    p = A, s = B, words([word(plus, priority(N)) | T]), elseloop={$x, @r} 
      :- ground(A),ground(B), ground(T),int(N) | elseloop={$x, word(plus, priority(N)), p = A, s = B, flag, @r}, words = T.
    p = A, s = B, words([word(minus, priority(N)) | T]), elseloop={$x, @r} 
      :- ground(A),ground(B), ground(T),int(N) | elseloop={$x, word(minus, priority(N)), p = A, s = B, flag, @r}, words = T.
    p = A, s = B, words([word(mul, priority(N)) | T]), elseloop={$x, @r} 
      :- ground(A),ground(B), ground(T),int(N) | elseloop={$x, word(mul, priority(N)), p = A, s = B, flag, @r}, words = T.
    p = A, s = B, words([word(div, priority(N)) | T]), elseloop={$x, @r} 
      :- ground(A),ground(B), ground(T),int(N) | elseloop={$x, word(div, priority(N)), p = A, s = B, flag, @r}, words = T.

    elseloop={$x, p = A, s = B, word(W, priority(N)), @r}/ 
      :-  ground(A), ground(B), ground(W), int(N) | elseloop={$x, @r}, p = A, s = [word(W, priority(N)) | B].
    rploop={$x, p = A, s = B, @r}/ 
      :-  ground(A), ground(B) | rploop={$x, @r}, p = A, s = B.
  }.
  
  whileloop = {
    p = A, s = [H | B] 
      :- ground(A), ground(B), ground(H) | p = [H | A], s = B.
  }.
  
  phase1.
  p = A, s = B, words(X), forloop({$x, @r}), phase1 
    :- ground(A), ground(B), ground(X) | forloop({$x,p = A, s = B, words(X), @r}).
  forloop({$x,p = A, s = B, words(X), @r}/) 
    :- ground(A), ground(B), ground(X) | p = A, s = B, words(X), forloop({$x, @r}), phase2.
  
  p = A, s = B, whileloop({$x, @r}), phase2 
    :- ground(A), ground(B) | whileloop({$x, p = A, s = B, @r}).
  whileloop({$x, p = A, s = B, @r}/) 
    :- ground(A), ground(B) | p = A, s = B, whileloop({$x, @r}), phase3.
  
  phase3, words = X, p = [H | A] 
    :-  ground(X), ground(H), ground(A) | phase3, words = [H | X], p = A.
  phase3, p = [] 
    :- p = [].
}.
infixExpr2postfixExpr({$p, @r}), words(X), phase2 
  :- ground(X) |  infixExpr2postfixExpr({$p, words(X), @r}).
infixExpr2postfixExpr({$p, words(X),  @r}/) 
  :- ground(X) |  infixExpr2postfixExpr({$p, @r}), words(X), phase3. 



calcPostfixExpr = {
  s = [].
  words([word(number, value(N)) | T]), s = V 
    :- ground(T), ground(V), int(N) | words = T, s = [N | V].
  words([word(plus, priority(N)) | T]), s = [B, A | V]
    :- ground(T), ground(V),int(A), int(B), int(N), C=A+B | words = T, s = [C | V].
  words([word(minus, priority(N)) | T]), s = [B, A | V]
    :- ground(T),ground(V), int(A), int(B), int(N), C=A-B | words = T, s = [C | V].
  words([word(mul, priority(N)) | T]), s = [B, A | V]
    :- ground(T), ground(V),int(A), int(B), int(N), C=A*B | words = T, s = [C | V].
  words([word(div, priority(N)) | T]), s = [B, A | V]
    :- ground(T), ground(V),int(A), int(B), int(N), C=A/B | words = T, s = [C | V].
  words = [], s = [N | V] :- ground(V), int(N) | res=N.
}.
phase3, words(X), calcPostfixExpr({$p, @r}) 
  :- ground(X) | calcPostfixExpr({$p, words(X), @r}).
calcPostfixExpr({$p, res(N), @r}) 
  :- int(N) | calcPostfixExpr({$p, @r}), res(N).
res(N) 
  :- int(N) | I = io.print_char(io.stdout, N), I2 = io.print_line(I, ""), io.free_port(I2).

test_dentaku.sh

#!/bin/bash

. assert.sh # https://github.com/lehmannro/assert.sh
assert "echo '1 + 2' | node dentaku.js" "3"
assert "echo '3 - 2' | node dentaku.js" "1"
assert "echo '2 - 3' | node dentaku.js" "-1"
assert "echo 2 \* 3 | node dentaku.js" "6"
assert "echo '2 / 3' | node dentaku.js" "0"
assert "echo '3 / 2' | node dentaku.js" "1"
assert "echo 10 + 2 \* 3 | node dentaku.js" "16"
assert "echo \( 10 + 2 \) \* 3 | node dentaku.js" "36"
assert "echo '1 + ( ( 200 + 800 ) - ( 100 / 3 ) )' | node dentaku.js" "968"
assert "echo 4 \* 5 - \( 5 \* \( 8 \- 3 \) \* \( 3 \+ 2 \) \) / 2 | node dentaku.js" "-42"
assert_end dentaku