java - 反向抛光到 java 中的 Infix Notation 优化

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

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

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

创建一个包含内容 e 和子节点 k 和 i 的新节点。然后简单地遍历树就可以生成任何表示(中缀、前缀或后缀)。