Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@pandamaster(パンダ マスター)

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

Posted at

前書き

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

目的

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

手順

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

3
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?