Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

概要

数式を逆ポーランド記法に変換するサンプルプログラムです。
アルゴリズム引用元:
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();
    }
}

終わりに

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

ken-maki
githubで公開したプログラムの解説用にQiitaへ記事投稿しています。 github:https://github.com/ken-maki  Twitter:https://twitter.com/kmaki1015 WEBサービス運営も始めました! http://ttagtube.com
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
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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
ユーザーは見つかりませんでした