Оптимизация обратной записи с польского на инфиксную в Java

Question

Я пытаюсь решить проблему программирования, которая заключается в преобразовании обратной польской записи в инфиксную запись. Например: 1 3 + 2 4 5 - + / будет: ((1 + 3) / (2+ (4-5))) Мое решение пока работает, но оно недостаточно быстрое. Поэтому я ищу любые советы по оптимизации.

public class betteralgo {
    public static void main(String[] args) throws IOException {
        BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
        String line = bi.readLine();
        String[] input = line.split(" ");
        StringBuilder builder = new StringBuilder();
        Stack<String> stack = new Stack<String>();

        for(String e:input) {
            switch(e){
                case("+"):
                case("-"):
                case("*"):
                case("/"):
                    String i = stack.pop();
                String k = stack.pop();
                stack.push("(" + k + e + i + ")");
                break;
                default:
                    stack.push(e);
                }
            }
        System.out.println(stack.pop());        
        }       
    }

Answer 1

Ваша проблема в квадратичной сложности из-за работы с более длинными и длинными выражениями. Решение состоит в том, чтобы построить дерево. Вместо

"(" + k + e + i + ")"

создайте новый узел с содержимым e и потомками k и i. Затем простой проход по дереву позволяет генерировать любое представление (инфикс, префикс или постфикс).

Answer 2

Просто из любопытства, быстрее ли это рекурсивное решение?

public static void main(String[] args)
{
    String input = "1 3 + 2 4 5 - + /";
    List<String> terms = new ArrayList<>(Arrays.asList(input.split(" ")));      
    String result = build(terms);
    System.out.println(result);
}

static String build(List<String> terms)
{
    String t = terms.remove(terms.size()-1);        
    if("+-/*".indexOf(t) >= 0)
    {
        String op2 = build(terms);
        String op1 = build(terms);
        return "(" + op1 + t + op2 + ")";
    }
    else return t;
}

Answer 3

Ваш код O(n) во временной сложности, которая, я думаю, является самой быстрой из возможных для этой проблемы. Но вы не пользуетесь StringBuilder, но используете трудоемкую конкатенацию строк.

Вот оптимизированная версия:

public static void main(String[] args) throws IOException {
    BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
    String line = bi.readLine();
    String[] input = line.split(" ");
    StringBuilder builder = new StringBuilder();
    Stack<String> stack = new Stack<String>();

    for(String e:input) {
        switch(e) {
            case("+"):
            case("-"):
            case("*"):
            case("/"):
                String i = stack.pop();
                String k = stack.pop();
                builder.setLength(0);
                builder.append("(");
                builder.append(k).append(e).append(i);
                builder.append(")");
                stack.push(builder.toString());
                break;
            default:
                stack.push(e);
        }
    }
    System.out.println(stack.pop());  
}