1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int uniqid();
struct Variable{
int id;
Variable(int id):id(id){}
bool isOperator() const;
bool isFixed() const;
bool isTemp() const;
bool operator==(Variable v) const;
bool operator!=(Variable v) const;
operator int() const;
};
namespace std {
template <>
struct hash<Variable>{
hash<int> inthasher;
size_t operator()(Variable v) const;
};
}
class Tree{
struct Node;
using Assign = unordered_map<Variable,Node>;
struct Node{
Variable v;
Node *left,*right;
explicit Node(Variable v);
Node(Node *left,Node *right);
Node(const Node &other);
~Node();
Node& operator=(const Node &other);
Assign* match(const Node &pat,Assign *accum=nullptr) const;
Node* apply(const Assign &as) const;
int nleaves() const;
int compare(const Node &other) const;
};
Node *root=nullptr;
static Node* parseTerm(const string &expr,size_t &idx);
static Node* parseNode(const string &expr,size_t &idx);
void replace(Node *subj,const Tree &pat,const Tree &repl,vector<Tree> &accum);
public:
Tree(); // Creates invalid tree
Tree(const string &expr);
Tree(const Tree &other);
~Tree();
Tree& operator=(const Tree &other);
bool matches(const Tree &pat) const;
vector<Tree> replace(const Tree &pat,const Tree &repl);
int nleaves() const;
int compare(const Tree &other) const;
friend ostream& operator<<(ostream &os,const Variable &v);
friend ostream& operator<<(ostream &os,const Node &node);
friend ostream& operator<<(ostream &os,const Tree &tree);
friend bool operator==(const Node &a,const Node &b);
friend bool operator!=(const Node &a,const Node &b);
};
struct TreeCompare{
bool operator()(const Tree &a,const Tree &b) const;
};
ostream& operator<<(ostream &os,const Tree &tree);
|
