連結:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3371
題意:
可以用表達式樹來表示一個表達式。在本題中,運算符均為二進制的,且運算符和運算數均用1~4個小寫字母表示。
例如,a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f))可以表示為a(b(f(a,4),b(3,f)),f(2,6)),
其中各個結點按照出現順序編号為1,2,3,…,即編号k表示目前為止寫下的第k個結點。
輸入一個長度不超過50000的表達式,輸出一個等價的,結點最少的圖。
分析:
用一個map把子樹映射成編号1, 2,…。這樣一來,子樹就可以用根的名字(字元串)和左右子結點編号表示。
然後構造表達式樹并判斷地輸出即可。
代碼:
1 //HashMap version
2 import java.io.*;
3 import java.util.*;
4 import static java.util.Arrays.*;
5 import static java.lang.Character.*;
6
7 class Node {
8 String s;
9 int lch, rch;
10
11 @Override
12 public int hashCode() {
13 final int prime = 31;
14 int result = 1;
15 result = prime * result + lch;
16 result = prime * result + rch;
17 result = prime * result + ((s == null) ? 0 : s.hashCode());
18 return result;
19 }
20
21 @Override
22 public boolean equals(Object obj) {
23 if (this == obj)
24 return true;
25 if (obj == null)
26 return false;
27 if (getClass() != obj.getClass())
28 return false;
29 Node other = (Node) obj;
30 if (lch != other.lch)
31 return false;
32 if (rch != other.rch)
33 return false;
34 if (s == null) {
35 if (other.s != null)
36 return false;
37 } else if (!s.equals(other.s))
38 return false;
39 return true;
40 }
41 }
42
43 public class Main {
44 Scanner cin = new Scanner(new BufferedInputStream(System.in));
45 final int UP = 50000 + 5;
46 int p, nextNode;
47 char s[];
48 boolean vis[] = new boolean[UP];
49 Node node[] = new Node[UP];
50 HashMap<Node,Integer> map = new HashMap<Node,Integer>();
51
52 { for(int i = 0; i < UP; i++) node[i] = new Node(); }
53
54 int parse() {
55 int id = ++nextNode;
56 node[id].s = "";
57 node[id].lch = node[id].rch = 0;
58 while(isLetter(s[p])) {
59 node[id].s += s[p];
60 p++;
61 }
62 if(s[p] == '(') {
63 p++; node[id].lch = parse(); p++; node[id].rch = parse(); p++;
64 }
65 if(map.containsKey(node[id])) {
66 nextNode--;
67 return map.get(node[id]);
68 }
69 map.put(node[id], id);
70 return id;
71 }
72
73 void output(int id) {
74 if(vis[id]) {
75 System.out.print(id);
76 return;
77 }
78 vis[id] = true;
79 System.out.print(node[id].s);
80 if(node[id].lch != 0) {
81 System.out.print('(');
82 output(node[id].lch);
83 System.out.print(',');
84 output(node[id].rch);
85 System.out.print(')');
86 }
87 }
88
89 void MAIN() {
90 int T = cin.nextInt();
91 while(T --> 0) {
92 s = (cin.next() + "\0").toCharArray();
93 p = nextNode = 0;
94 fill(vis, false);
95 map.clear();
96 output(parse());
97 System.out.println();
98 }
99 }
100
101 public static void main(String args[]) { new Main().MAIN(); }
102 }
1 //TreeMap version
2 import java.io.*;
3 import java.util.*;
4 import static java.util.Arrays.*;
5 import static java.lang.Character.*;
6
7 class Node implements Comparable<Node> {
8 String s;
9 int hash, lch, rch;
10
11 @Override
12 public int compareTo(Node that) {
13 if(hash != that.hash) return hash - that.hash;
14 if(lch != that.lch) return lch - that.lch;
15 return rch - that.rch;
16 }
17 }
18
19 public class Main {
20 Scanner cin = new Scanner(new BufferedInputStream(System.in));
21 final int UP = 50000 + 5;
22 int p, nextNode;
23 char s[];
24 boolean vis[] = new boolean[UP];
25 Node node[] = new Node[UP];
26 TreeMap<Node,Integer> map = new TreeMap<Node,Integer>();
27
28 { for(int i = 0; i < UP; i++) node[i] = new Node(); }
29
30 int parse() {
31 int id = ++nextNode;
32 node[id].s = "";
33 node[id].hash = node[id].lch = node[id].rch = 0;
34 while(isLetter(s[p])) {
35 node[id].hash = node[id].hash * 29 + s[p] - 'a' + 1;
36 node[id].s += s[p];
37 p++;
38 }
39 if(s[p] == '(') {
40 p++; node[id].lch = parse(); p++; node[id].rch = parse(); p++;
41 }
42 if(map.containsKey(node[id])) {
43 nextNode--;
44 return map.get(node[id]);
45 }
46 map.put(node[id], id);
47 return id;
48 }
49
50 void output(int id) {
51 if(vis[id]) {
52 System.out.print(id);
53 return;
54 }
55 vis[id] = true;
56 System.out.print(node[id].s);
57 if(node[id].lch != 0) {
58 System.out.print('(');
59 output(node[id].lch);
60 System.out.print(',');
61 output(node[id].rch);
62 System.out.print(')');
63 }
64 }
65
66 void MAIN() {
67 int T = cin.nextInt();
68 while(T --> 0) {
69 s = (cin.next() + "\0").toCharArray();
70 p = nextNode = 0;
71 fill(vis, false);
72 map.clear();
73 output(parse());
74 System.out.println();
75 }
76 }
77
78 public static void main(String args[]) { new Main().MAIN(); }
79 }
轉載于:https://www.cnblogs.com/hkxy125/p/9074850.html