算法Sedgewick第四版-第1章基础-013一用stack实现自动补全表达式括号

 1 package algorithms.exercise;
 2 
 3 import algorithms.ADT.Stack;
 4 import algorithms.util.StdIn;
 5 import algorithms.util.StdOut;
 6 
 7 
 8 /*************************************************************************
 9  *
10  *  % java Ex_1_3_09
11  *  1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )
12  *  ( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )
13  *
14  *  % java Ex_1_3_09
15  *  sqrt 1 + 2 ) )
16  *  ( sqrt ( 1 + 2 ) )
17  *
18  *************************************************************************/
19 
20 public class Ex_1_3_09
21 {
22     public static void main(String[] args)
23     { 
24         Stack<String> ops  = new Stack<String>();
25         Stack<String> vals = new Stack<String>();
26 
27         while (!StdIn.isEmpty())
28         {
29             String s = StdIn.readString();
30             
31             if      (s.equals("("))               ;
32             else if (s.equals("+") ||
33                      s.equals("-") ||
34                      s.equals("*") ||
35                      s.equals("/") ||
36                      s.equals("sqrt")) ops.push(s);
37             else if (s.equals(")"))
38             {
39                 String op = ops.pop();
40                 String v = vals.pop();
41                 
42                 if (op.equals("+") ||
43                     op.equals("-") ||
44                     op.equals("*") ||
45                     op.equals("/"))
46                     v = String.format("( %s %s %s )", vals.pop(), op, v);
47                 else if (op.equals("sqrt"))
48                     v = String.format("( %s %s )", op, v);
49                 
50                 vals.push(v);
51             }
52             else vals.push(s);
53             //else vals.push(((Double)Double.parseDouble(s)).toString());
54         }
55         
56         StdOut.println(vals.pop());
57     }
58 }