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

你的代码在时间复杂度上是 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());  
}

Answer 2

您的问题是由于使用越来越长的表达式而导致的二次复杂度。解决方案是建造一棵树。而不是

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

创建一个包含内容 e 和子节点 k 和 i 的新节点。然后通过树的简单传递允许您生成任何表示（中缀、前缀或后缀）。

Answer 3

出于好奇，这个递归解决方案是否更快？

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;
}

java 中的反向波兰语到中缀符号优化

Reverse Polish to Infix Notation optimization in java

java

algorithm

optimization

infix-notation