今更ながら中置記法→逆ポーランド記法→計算をやってみた

前書き

・オレオレアルゴリズムなので、そもそもの理屈が変かも
・説明少な目（ソースとコメント読んで）
・突っ込み大歓迎

目的

今作ってるサービスで、ユーザが計算式を入力する画面があるので、中置記法を逆ポーランド記法に変換して保存、演算する必要があったため。

手順

1.中置記法のホワイトスペースやオペランド（項）、オペレータ（演算子）、ブラケット（括弧）以外の余計な文字をフィルタリングする
2.中置記法を端から舐めて行って、二分木を使ったシンタックスツリーを生成する
3.シンタックスツリーを深いところから順に配列に並べて逆ポーランド記法の数式にする
4.逆ポーランド記法の数式を計算する

ライブラリ及びバージョン

Java 1.8
Spring 4.x

用意するクラス

1.Nodeクラス
2.Formulaクラス
3.Calculatorクラス
4.テストクラス

実装

Nodeクラス

シンタックスツリーと配列で使用するNodeクラスを作成する。

Node.java

public class Node{
    protected Node left;
    protected Node right;
    protected Node parent;
    protected String data;
    protected Integer precedence;
    protected boolean visited;

    public Node(String data, int precedence) {
        this.data = data;
        this.precedence = precedence;
        this.setVisited(false);
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
        left.setParent(this);
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
        right.setParent(this);
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public int getPrecede() {
        return precedence;
    }

    public void setPrecede(int precedence) {
        this.precedence = precedence;
    }

    public Node searchTop() {
        Node current = this;
        while(current.getParent() != null) {
            current = current.getParent();
        }
        return current;
    }

    public Node clone() {
        return new Node(this.data, this.precedence);
    }

    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }
}

二分木のひとつのノードを表すクラス。
左右の枝の先にあるノードと親ノードへの参照を持つ。

Formulaクラス

中置記法の解析及びシンタックスツリーの生成、逆ポーランド記法への変換を実行する。
試行錯誤の末できたコードなので、かなり雑。
グラフとかそういう理屈は知らん。

Formula.java

public class Formula {
    // 正規表現の文字列定数
    // スペース
    public static final String REGEXP_FORMAT = "(%s)";
    public static final String WHITE_SPACE = "\\s";
    // 整数、変数、小数点数（変数についてはまだ考慮してない）
    public static final String OPERANDS = "\\d\\.\\d|\\d|\\w";
    // オペレータを列挙したもの
    public static final String OPERATORS = "\\+|\\-|\\*|\\/|%|\\^";
    // 括弧
    public static final String BRACKETS = "\\(|\\)";
    // 開き括弧
    public static final String OPENING_BRACKET = "\\(";
    // 閉じ括弧
    public static final String CLOSING_BRACKET = "\\)";
    public static final String MINUS = "-";
    // 
    public static final String VALID_FORMULA = "^(\\d\\.\\d|\\d|\\w|-\\d\\.\\d|-\\d|-\\w)(((\\+|\\-|\\*|\\/|%|\\^)(\\d\\.\\d|\\d|\\w|-\\d\\.\\d|-\\d|-\\w))*)$";
    // マイナス値を計算で表すための係数
    public static final String COEFFICIENT = "-1";
    public static final String MULTIPLY = "*";
    // 括弧内のオペレータの優先度を上げるためのゲタ
    public static final int INFLATE_NUMBER = 10;
    // ユーザが入力した数式
    private String formula;
    // シンタックスツリーの根
    private Node tree;
    // 逆ポーランド記法の配列
    private List<Node> rpn;
    // オペレータ、オペランドごとの優先度マップ
    private static final Map<String, ValidCharacter> VALID_CHARACTERS_MAP
        = Arrays.asList(
            new ValidCharacter("\\d\\.\\d", Integer.MAX_VALUE - 1),
            new ValidCharacter("\\w", Integer.MAX_VALUE - 1),
            new ValidCharacter("\\d", Integer.MAX_VALUE - 1),
            new ValidCharacter("%", 2),
            new ValidCharacter("\\+", 2),
            new ValidCharacter("\\-", 2),
            new ValidCharacter("\\*", 3),
            new ValidCharacter("\\/", 3),
            new ValidCharacter("\\^", 4),
            new ValidCharacter("\\(", 10),
            new ValidCharacter("\\)", 10))
        .stream().collect(Collectors.toMap(ValidCharacter::getData, d -> d));
    // 中置記法のままオペレータ、オペランドを格納するキュー
    private Deque<Node> queue = new ArrayDeque<>();

    // コンストラクタ
    public Formula() {
    }

    public Formula(String formula) {
        this.formula = formula;
    }

    public Node parseFormula() throws IllegalArgumentException {
        return parseFormula(formula);
    }

    // 中置記法を逆ポーランド記法へ変換
    public Node parseFormula(String formula) throws IllegalArgumentException {
        // 余計なスペースを除去
        String trim = formula.replaceAll(getRegExp(WHITE_SPACE), "");
        // 余計な文字が含まれるかどうか
        String temp = trim.replaceAll(getRegExp(OPERANDS, OPERATORS, BRACKETS), "");

        Assert.isTrue(temp.length() == 0, "");
        int bracket = 0;
        // 文字列の数式をオペレータ、オペランドに分解
        while(trim.length() > 0) {
            // 先頭のオペレータ or オペランドを取り出す
            String flagment = getFlagment(trim);
            // 取り出した分を消去
            trim = trim.replaceFirst(getRegExp(OPERANDS, OPERATORS, BRACKETS), "");
            // 優先度マップから一致するValidCharacterを取り出す
            ValidCharacter vc = VALID_CHARACTERS_MAP.entrySet().stream().filter(
                entry -> {
                    return flagment.matches(entry.getKey());
                }
            ).findFirst().get().getValue();
            Assert.isTrue(vc != null, "");
            // 開き括弧の場合、優先度を上げる
            if(flagment.matches(OPENING_BRACKET)) {
                bracket++;
                continue;
            }
            // 閉じ括弧の場合、優先度を下げる
            else if(flagment.matches(CLOSING_BRACKET)) {
                bracket--;
                continue;
            }
            String test_flagment = getFlagment(trim);
            // マイナス値が含まれる場合、-1との掛け算に置換
            if((queue.isEmpty() || queue.peekLast().getData().matches(getRegExp(OPERATORS))) && MINUS.equals(flagment) && (test_flagment.matches(getRegExp(OPERANDS)))) {
                queue.add(new Node(COEFFICIENT, Integer.MAX_VALUE - 1));
                queue.add(new Node(MULTIPLY, 3 + INFLATE_NUMBER * (bracket + 1)));
            }
            // プラス値ならそのままキューに格納
            else {
                queue.add(new Node(flagment, flagment.matches(getRegExp(OPERANDS))?vc.getPrecedence():(vc.getPrecedence() + INFLATE_NUMBER * bracket)));
            }
        }
        // 計算式がオペランドで始まって、オペレータを挟んでオペランドで終わるかチェック
        Assert.isTrue(String.join("", queue.stream().map(node -> node.getData()).collect(Collectors.toList())).matches(VALID_FORMULA), "");
        // キューの先頭要素をシンタックスツリーのルートにする
        Node currentNode = queue.pollFirst();
        // シンタックスツリーの生成
        currentNode.setLeft(new Node("", Integer.MAX_VALUE));
        currentNode.setRight(new Node("", Integer.MAX_VALUE));
        do {
            // キューの先頭を取り出す
            Node poll = queue.pollFirst();
            Assert.isTrue(bracket > 0 || !")".equals(poll.getData()), "");
            Node left = currentNode, right = null;
            // 取り出したノードより優先度の高いノードが見つかるまで探索
            do {
                // 優先度の高いノードが見つかった場合
                if(currentNode.getPrecede() >= poll.getPrecede()) {
                    left = currentNode;
                    right = new Node("", Integer.MAX_VALUE);
                    if(currentNode.getParent() != null) {
                        currentNode.getParent().setRight(poll);
                    }
                    currentNode = poll;
                    break;
                }
                // 優先度の低いノードの場合、枝の右を一つ降りる
                else if(currentNode.getPrecede() < poll.getPrecede()) {
                    currentNode = currentNode.getRight();
                }
            }while(true);
            // ノードをツリーに挿入
            currentNode.setLeft(left);
            currentNode.setRight(right);
            currentNode = currentNode.searchTop();
        }while(!queue.isEmpty());
        setTree(currentNode.searchTop());
        return getTree();
    }

    // 文字列の数式から先頭を取り出す
    public String getFlagment(String formula) {
        return formula.substring(0, formula.length() - formula.replaceFirst(getRegExp(OPERANDS, OPERATORS, BRACKETS), "").length());
    }

    public List<Node> toTreeToRpn() {
        return parseTreeToRpn(this.tree);
    }

    // シンタックスツリーを逆ポーランド記法の配列へ変換
    public List<Node> parseTreeToRpn(Node tree) {
        // 最後に反転
        rpn = new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        stack.push(tree);
        while(!stack.isEmpty() ) {
            // スタックに積まれたノードを配列に格納
            Node node = stack.pop();
            rpn.add(node);
            // 葉ノードはInteger.MAX_VALUEなので、それより優先度の小さいノードの左右の枝をスタックに格納する
            if(node.getRight().getPrecede() < Integer.MAX_VALUE) {
                stack.push(node.getRight());
            }
            if(node.getLeft().getPrecede() < Integer.MAX_VALUE) {
                stack.push(node.getLeft());
            }
        }
        Collections.reverse(rpn);
        return rpn;
    }

    public int calculateRpnInteger() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
        return calculateRpnInteger(this.rpn);
    }

    // 逆ポーランド記法の計算式を計算
    public int calculateRpnInteger(List<Node> rpn) throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
        Stack<Node> stack = new Stack<>();
        Calculator calc = new Calculator();
        // 配列のすべての要素についてループ
        for(Node token : rpn) {
            // オペランドの場合はスタックに積む
            if(token.getPrecede() == Integer.MAX_VALUE - 1) {
                stack.push(token);
            }
            // オペレータの場合はスタックから2値を取り出して計算
            else {
                Assert.notEmpty(stack, "");
                Node left = stack.pop();
                Assert.notEmpty(stack, "");
                Node right = stack.pop();
                stack.push(new Node(calc.calculate(token.getData(), left.getData(), right.getData()).toString(), Integer.MAX_VALUE - 1));
            }
        }
        // 計算結果を返す
        return Integer.valueOf(stack.pop().getData());
    }

    public String getFormula() {
        return formula;
    }

    public void setFormula(String formula) {
        this.formula = formula;
    }

    public Node getTree() {
        return tree;
    }

    public void setTree(Node tree) {
        this.tree = tree;
    }

    public String getRegExp(String... regexp) {
        return String.format(REGEXP_FORMAT, String.join("|", regexp));
    }

    public List<Node> getRpn() {
        return rpn;
    }

    public void setRpn(List<Node> rpn) {
        this.rpn = rpn;
    }
}

// オペレータ、オペランドの優先度を表す内部クラス
class ValidCharacter {
    String data;
    Integer precedence;
    public ValidCharacter(String data, int precedence) {
        this.data = data;
        this.precedence = precedence;
    }

    public String getData() {
        return data;
    }

    public int getPrecedence() {
        return precedence;
    }
}

Calculatorクラス

逆ポーランド記法の配列を先頭から取り出して順次計算する。

Calculator.java

public class Calculator {
    private String key;
    private Map<String, Method> calculators = new HashMap<>();

    // 各オペレータごとに計算用のメソッドをハッシュマップに格納する。
    public Calculator() throws NoSuchMethodException, SecurityException {
        calculators.put("+", this.getClass().getMethod("addInteger", new Class[] {String.class, String.class}));
        calculators.put("-", this.getClass().getMethod("subtractInteger", new Class[] {String.class, String.class}));
        calculators.put("*", this.getClass().getMethod("multiplyInteger", new Class[] {String.class, String.class}));
        calculators.put("/", this.getClass().getMethod("divideInteger", new Class[] {String.class, String.class}));
        calculators.put("%", this.getClass().getMethod("surplusInteger", new Class[] {String.class, String.class}));
        calculators.put("^", this.getClass().getMethod("powerFloat", new Class[] {String.class, String.class}));
    }

    // オペレータと2つのオペランドを渡して計算を実行する。
    public Object calculate(String operator, String left, String right) throws IllegalAccessException, IllegalArgumentException, InvocationTargetException {
        Method method = calculators.get(operator);
        Assert.isNotNull(method, "");
        return method.invoke(this, left, right);
    }

    // 足し算
    public Object addInteger(String left, String right) {
        return Integer.parseInt(left) + Integer.parseInt(right);
    }

    // 引き算
    public Object subtractInteger(String left, String right) {
        return Integer.parseInt(left) - Integer.parseInt(right);
    }

    // 掛け算
    public Object multiplyInteger(String left, String right) {
        return Integer.parseInt(left) * Integer.parseInt(right);
    }

    // 割り算
    public Object divideInteger(String left, String right) {
        return Integer.parseInt(left) / Integer.parseInt(right);
    }

    // 剰余
    public Object surplusInteger(String left, String right) {
        return Integer.parseInt(left) % Integer.parseInt(right);
    }

    // べき乗
    public Object powerFloat(String left, String right) {
        return (int)Math.pow(Double.parseDouble(left), Double.parseDouble(right));
    }
}

これは単純に計算するだけのクラスなので説明不要。

テスト

いくつか計算式を適用してみて思った通りになるかどうかテスト。
うまく行かないテストケースがあったら教えてちょ。

FormulaTest.java

public class FormulaTest {

    @Test
    public void testGetFlagment() {
        assertEquals("1", new Formula("1+1").getFlagment("1+1"));
    }

    @Test
    public void testParseFormula1() {
        Node node = new Formula().parseFormula("1+2");
        assertEquals("1", node.getLeft().getData());
        assertEquals("+", node.getData());
        assertEquals("2", node.getRight().getData());
    }

    @Test
    public void testParseFormula2() {
        Node node = new Formula().parseFormula("(1+2)*3");
        assertEquals("1", node.getLeft().getLeft().getData());
        assertEquals("2", node.getLeft().getRight().getData());
        assertEquals("+", node.getLeft().getData());
        assertEquals("3", node.getRight().getData());
        assertEquals("*", node.getData());
    }

    @Test
    public void testParseFormula3() {
        Node node = new Formula().parseFormula("3*(1+2)");
        assertEquals("1", node.getRight().getLeft().getData());
        assertEquals("2", node.getRight().getRight().getData());
        assertEquals("+", node.getRight().getData());
        assertEquals("3", node.getLeft().getData());
        assertEquals("*", node.getData());
    }

    @Test
    public void testParseFormula4() {
        Node node = new Formula().parseFormula("(1+2)*(3+4)");
        assertEquals("1", node.getLeft().getLeft().getData());
        assertEquals("2", node.getLeft().getRight().getData());
        assertEquals("+", node.getLeft().getData());
        assertEquals("*", node.getData());
        assertEquals("3", node.getRight().getLeft().getData());
        assertEquals("4", node.getRight().getRight().getData());
        assertEquals("+", node.getRight().getData());
    }

    @Test
    public void testParseTreeToRPN1() {
        Node node = new Formula().parseFormula("(1+2)*(3+4)");
        List<Node> rpn = new Formula().parseTreeToRpn(node);
        assertEquals("4", rpn.get(0).getData());
        assertEquals("3", rpn.get(1).getData());
        assertEquals("+", rpn.get(2).getData());
        assertEquals("2", rpn.get(3).getData());
        assertEquals("1", rpn.get(4).getData());
        assertEquals("+", rpn.get(5).getData());
        assertEquals("*", rpn.get(6).getData());
    }

    @Test
    public void testParseTreeToRPN2() {
        Node node = new Formula().parseFormula("(1+2)^2*(3+4)");
        List<Node> rpn = new Formula().parseTreeToRpn(node);
        assertEquals("4", rpn.get(0).getData());
        assertEquals("3", rpn.get(1).getData());
        assertEquals("+", rpn.get(2).getData());
        assertEquals("2", rpn.get(3).getData());
        assertEquals("2", rpn.get(4).getData());
        assertEquals("1", rpn.get(5).getData());
        assertEquals("+", rpn.get(6).getData());
        assertEquals("^", rpn.get(7).getData());
        assertEquals("*", rpn.get(8).getData());
    }

    @Test
    public void testParseTreeToRPN3() {
        Node node = new Formula().parseFormula("(1.1+2)^3*(4+5)");
        List<Node> rpn = new Formula().parseTreeToRpn(node);
        assertEquals("5", rpn.get(0).getData());
        assertEquals("4", rpn.get(1).getData());
        assertEquals("+", rpn.get(2).getData());
        assertEquals("3", rpn.get(3).getData());
        assertEquals("2", rpn.get(4).getData());
        assertEquals("1.1", rpn.get(5).getData());
        assertEquals("+", rpn.get(6).getData());
        assertEquals("^", rpn.get(7).getData());
        assertEquals("*", rpn.get(8).getData());
    }

    @Test
    public void testParseTreeToRPN4() {
        Node node = new Formula().parseFormula("(1 + -2) ^ 3 * (4 + 5)");
        List<Node> rpn = new Formula().parseTreeToRpn(node);
        assertEquals("5", rpn.get(0).getData());
        assertEquals("4", rpn.get(1).getData());
        assertEquals("+", rpn.get(2).getData());
        assertEquals("3", rpn.get(3).getData());
        assertEquals("2", rpn.get(4).getData());
        assertEquals("-1", rpn.get(5).getData());
        assertEquals("*", rpn.get(6).getData());
        assertEquals("1", rpn.get(7).getData());
        assertEquals("+", rpn.get(8).getData());
        assertEquals("^", rpn.get(9).getData());
        assertEquals("*", rpn.get(10).getData());
    }

    @Test
    public void testCalculate1() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
        Node node = new Formula().parseFormula("(1+-2)*(3+4)");
        List<Node> rpn = new Formula().parseTreeToRpn(node);
        rpn.stream().forEach(entry -> System.out.print(entry.getData() + ","));
        System.out.println("");
        assertEquals(-7, new Formula().calculateRpnInteger(rpn));
    }

    @Test
    public void testCalculate2() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
        Node node = new Formula().parseFormula("((1+2)*3)+4");
        List<Node> rpn = new Formula().parseTreeToRpn(node);
        assertEquals(13, new Formula().calculateRpnInteger(rpn));
    }

    @Test
    public void testCalculate3() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
        Node node = new Formula().parseFormula("(1+-2)-(3+4)");
        List<Node> rpn = new Formula().parseTreeToRpn(node);
        rpn.stream().forEach(entry -> System.out.print(entry.getData() + ","));
        System.out.println("");
        assertEquals(-8, new Formula().calculateRpnInteger(rpn));
    }

    @Test
    public void testCalculate4() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
        Node node = new Formula().parseFormula("1*-2-(3*-4)");
        List<Node> rpn = new Formula().parseTreeToRpn(node);
        rpn.stream().forEach(entry -> System.out.print(entry.getData() + ","));
        System.out.println("");
        assertEquals(10, new Formula().calculateRpnInteger(rpn));
    }
}

FormulaTestTestError.java

package net.pandamaster.trpg.utils.formula;

import static org.junit.Assert.*;

import java.lang.reflect.InvocationTargetException;
import java.util.List;

import org.junit.Test;

import net.pandamaster.trpg.utils.Node;

public class FormulaTestTestError {

    @Test(expected = IllegalArgumentException.class)
    public void testParseFormula1() {
        Node node = new Formula().parseFormula("1++2");
        assertEquals("1", node.getLeft().getData());
        assertEquals("+", node.getData());
        assertEquals("2", node.getRight().getData());
    }

    @Test(expected = IllegalArgumentException.class)
    public void testParseTreeToRPN1() {
        Node node = new Formula().parseFormula("1++2");
        List<Node> rpn = new Formula().parseTreeToRpn(node);
        System.out.println(rpn.toString());
        assertEquals("4", rpn.get(0));
        assertEquals("3", rpn.get(1));
        assertEquals("+", rpn.get(2));
        assertEquals("2", rpn.get(3));
        assertEquals("1", rpn.get(4));
        assertEquals("+", rpn.get(5));
        assertEquals("*", rpn.get(6));
    }

    @Test(expected = IllegalArgumentException.class)
    public void testCalculate1() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
        Node node = new Formula().parseFormula("(1++2)*(3+4)");
        List<Node> rpn = new Formula().parseTreeToRpn(node);
        assertEquals(21, new Formula().calculateRpnInteger(rpn));
    }

    @Test(expected = IllegalArgumentException.class)
    public void testCalculate2() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
        Node node = new Formula().parseFormula("1*-2--(3*-4)");
        List<Node> rpn = new Formula().parseTreeToRpn(node);
        rpn.stream().forEach(entry -> System.out.print(entry.getData() + ","));
        System.out.println("");
        assertEquals(10, new Formula().calculateRpnInteger(rpn));
    }

    @Test(expected = IllegalArgumentException.class)
    public void testCalculate3() throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
        Node node = new Formula().parseFormula("-(1+2)*(3+4)");
        List<Node> rpn = new Formula().parseTreeToRpn(node);
        assertEquals(21, new Formula().calculateRpnInteger(rpn));
    }
}

参考サイト

https://artofproblemsolving.com/community/c163h141553_how_to_convert_infix_to_postfixreverse_polish_notation
https://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95