By

Contents

##将不带左括号的表达式转为中缀表达式

1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) ) –> ( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )

 public static String infixExpressed(String[] strings) {
    String result = new String();
    Stack <String> stack = new Stack();
    for (String s : strings) {
        if (!s.equals(")")) {
            stack.push(s);
        }
        if (s.equals(")")) {
            String temp = new String();
            int i = 0;
            while (i < 3) {
                if (!stack.isEmpty())
                    temp = (String)stack.pop() + temp;
                i++;
            }
            temp = "(" + temp + ")";

            stack.push(temp);
        }
    }
    return stack.pop();
}

1.stack : [1] [+] [2] 读入 “)” 触发条件判断取出字符并拼接成 “(1+2)” 并 push
stack : [(1+2)]

中间省略多步

2.stack : [(1+2)] [*] [3] [-] [4] 读入 “)” 触发条件判断取出字符并拼接成 “(3+4)” 并 push
stack : [(1+2)] [*] [(3-4)]

中间省略多步

3.stack : [(1+2)] [*] [(3-4)] [*] [5] [-] [6] 读入 “)” 触发条件判断取出字符并拼接成 “(5-6)” 并 push
stack : [(1+2)] [*] [(3-4)] [*] [(5-6)]

4.stack : [(1+2)] [*] [(3-4)] [*] [(5-6)] 读入 “)” 触发条件判断取出字符并拼接成 “((3-4)*(5-6))” 并 push
stack : [(1+2)] [*] [((3-4)*(5-6))]

5.stack : [(1+2)] [*] [((3-4)*(5-6))] 读入 “)” 触发条件判断取出字符并拼接成 “((1+2)*((3-4)*(5-6)))” 并 push
stack : [((1+2)*((3-4)*(5-6)))]
6.pop 得到结果

输入：1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )
输出: ( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )

输入：sqrt 1 + 2 ) )
输出: ( sqrt ( 1 + 2 ) )

空格忽略掉。

对比 (aistrate/AlgorithmsSedgewick)[https://github.com/aistrate/AlgorithmsSedgewick/blob/master/1-Fundamentals/1-3-BagsQueuesStacks/Ex_1_3_09.java] 的解法还是要简单易懂，Stack 也少用一个。

实际上后来发现这就是后缀表达式的表达过程嘛。

Stack<String> ops  = new Stack<String>();
    Stack<String> vals = new Stack<String>();

    while (!StdIn.isEmpty())
    {
        String s = StdIn.readString();
        
        if      (s.equals("("))               ;
        else if (s.equals("+") ||
                 s.equals("-") ||
                 s.equals("*") ||
                 s.equals("/") ||
                 s.equals("sqrt")) ops.push(s);
        else if (s.equals(")"))
        {
            String op = ops.pop();
            String v = vals.pop();
            
            if (op.equals("+") ||
                op.equals("-") ||
                op.equals("*") ||
                op.equals("/"))
                v = String.format("( %s %s %s )", vals.pop(), op, v);
            else if (op.equals("sqrt"))
                v = String.format("( %s %s )", op, v);
            
            vals.push(v);
        }
        else vals.push(s);
        //else vals.push(((Double)Double.parseDouble(s)).toString());
    }
Contents