Convert formulas to reverse Polish notation

Overview

This is a sample program that converts mathematical expressions to Reverse Polish Notation. Algorithm source: http://www.gg.e-mansion.com/~kkatoh/program/novel2/novel208.html Formula source: 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

Thank you

Details

It's just converted to Polish notation based on the formula. I'm just making the algorithm in Java, so I'm grateful to the quoter.

Rpn.java


/**
 *Algorithm quote: http://www.gg.e-mansion.com/~kkatoh/program/novel2/novel208.html
 */
public class Rpn {
    public static void main(String[] args) {
        //Expression quote: 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));
    }

    /**
     *Convert formulas to reverse Polish notation.
     *
     * @param formula Reverse Polish notation Formula to be converted
     * @return Formula converted to reverse Polish notation
     */
    public static String getRpn(String formula) {
        char[] sequenceList  = formula.toCharArray();
        //StringBuilder to store the return value
        StringBuilder resultBuilder = new StringBuilder(sequenceList.length);
        Deque<Character> stack = new ArrayDeque<>();

        //Continue looping until you convert all formulas to Reverse Polish Notation
        for(char token : sequenceList){
            switch (token) {
                case '+':
                case '-':
                    //If the priority of the stacked operator is lower, the stack operator is buffered.
                    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 ')':
                    // 「(From ")Operators up to "to buffer"
                    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:
                    //In the case of numerical value
                    resultBuilder.append(token);
                    break;
            }
        }

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

At the end

Please let me know if there is a bug. If there are no bugs, please use it (laughs) Thanks to the internet for getting the information you want to know with the quoter.

Recommended Posts

Convert formulas to reverse Polish notation
I tried infix notation → reverse Polish notation → calculation
[Brain teaser] Reverse Polish notation enumeration and its calculation
Convert a Java byte array to a string in hexadecimal notation
Convert Java Powerpoint to XPS
I want to convert characters ...
Convert String type to Timestamp type
Convert to Ruby Leet string
Convert Serializable Object to byte []
Convert from ○ months to ○ years ○ months
How to convert Java radix
[Java] Convert ArrayList to array