5
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

posted at

updated at

数式を逆ポーランド記法に変換

概要

数式を逆ポーランド記法に変換するサンプルプログラムです。
アルゴリズム引用元:
http://www.gg.e-mansion.com/~kkatoh/program/novel2/novel208.html
数式引用元:
http://www.wdic.org/w/SCI/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95

ありがたや

詳細

数式をもとにポーランド記法に変換しているだけです。
アルゴリズムをJavaで作っているだけなので、感謝すべきは引用元様でしょう。

Rpn.java
/**
 * アルゴリズム引用:http://www.gg.e-mansion.com/~kkatoh/program/novel2/novel208.html
 */
public class Rpn {
    public static void main(String[] args) {
        // 式の引用:http://www.wdic.org/w/SCI/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95
        String formula = "a+b"; // ab+
//        String formula = "a+(b*c)"; // abc*+
//        String formula = "(a+b)*c"; // ab+c*
//        String formula = "a*b+c*d+e*f"; // ab*cd*ef*++
//        String formula = "((a+b)*(c+d)+e)*f"; // ab+cd+*e+f*

        System.out.println(getRpn(formula));
    }

    /**
     * 数式を逆ポーランド記法に変換.
     *
     * @param formula 逆ポーランド記法変換対象の数式
     * @return 逆ポーランド記法に変換した数式
     */
    public static String getRpn(String formula) {
        char[] sequenceList  = formula.toCharArray();
        // 戻り値を格納するStringBuilder
        StringBuilder resultBuilder = new StringBuilder(sequenceList.length);
        Deque<Character> stack = new ArrayDeque<>();

        // 数式をすべて逆ポーランド記法に変換するまでループを続ける
        for(char token : sequenceList){
            switch (token) {
                case '+':
                case '-':
                    // スタックされた演算子の優先順位より低い場合は、スタックの演算子をバッファへ
                    while (!stack.isEmpty()) {
                        char c = stack.getFirst();
                        if (c == '*' || c == '/') {
                            resultBuilder.append(stack.removeFirst());
                        } else {
                            break;
                        }
                    }
                    stack.addFirst(token);
                    break;
                case '*':
                case '/':
                case '(':
                    stack.addFirst(token);
                    break;
                case ')':
                    // 「(」から「)」までの演算子をバッファへ
                    List<Object> list = Arrays.asList(stack.toArray());
                    int index = list.indexOf('(');

                    Deque<Character> workStack = new ArrayDeque<>();
                    for (int i = 0; i <= index; i++) {
                        char c = stack.removeFirst();
                        if (c != '(') {
                            workStack.addFirst(c);
                        }
                    }

                    while (!workStack.isEmpty()) {
                        resultBuilder.append(workStack.removeFirst());
                    }
                    break;
                default:
                    // 数値の場合
                    resultBuilder.append(token);
                    break;
            }
        }

        while (!stack.isEmpty()) {
            resultBuilder.append(stack.removeFirst());
        }
        return resultBuilder.toString();
    }
}

終わりに

バグっていたら教えてください。バグっていなかったら使ってください(笑)
引用元様と知りたい情報をすぐ手に入れられるインターネットに感謝。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
5
Help us understand the problem. What are the problem?