在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

只是出于好奇，这个递归解决方案会更快吗？public static void main(String[] args){&nbsp; &nbsp; String input = "1 3 + 2 4 5 - + /";&nbsp; &nbsp; List<String> terms = new ArrayList<>(Arrays.asList(input.split(" ")));&nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; String result = build(terms);&nbsp; &nbsp; System.out.println(result);}static String build(List<String> terms){&nbsp; &nbsp; String t = terms.remove(terms.size()-1);&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; if("+-/*".indexOf(t) >= 0)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; String op2 = build(terms);&nbsp; &nbsp; &nbsp; &nbsp; String op1 = build(terms);&nbsp; &nbsp; &nbsp; &nbsp; return "(" + op1 + t + op2 + ")";&nbsp; &nbsp; }&nbsp; &nbsp; else return t;}

Answer 2

由于使用越来越长的表达式，您的问题是二次复杂性。解决办法是建一棵树。而不是"("&nbsp;+&nbsp;k&nbsp;+&nbsp;e&nbsp;+&nbsp;i&nbsp;+&nbsp;")"创建一个包含内容e和子节点的新节点k以及i.&nbsp;然后通过树的简单传递允许您生成任何表示（中缀、前缀或后缀）。