001package iterator.exprtwo;
002import java.util.Iterator;
003import java.util.NoSuchElementException;
004import java.util.List;
005import java.util.ArrayList;
006import java.util.Stack;
007import java.util.Set;
008import java.util.HashSet;
009import enumeration.Op;
010
011public interface Expr {
012        public int evaluate();
013        public Iterator<Object> preorderIterator();
014        public Iterator<Object> postorderIterator();
015        public Iterator<Object> breadthIterator();
016}
017
018abstract class AbsExpr implements Expr {
019        public abstract int evaluate();
020        public Iterator<Object> preorderIterator() {
021                PreorderIterator i = new PreorderIterator();
022                i.addNode(this);
023                return i;
024        }
025        public Iterator<Object> postorderIterator() {
026                PostorderIterator i = new PostorderIterator();
027                i.addNode(this);
028                return i;
029        }
030        public Iterator<Object> breadthIterator() {
031                BreadthIterator i = new BreadthIterator();
032                i.addNode(this);
033                return i;
034        }
035        abstract Object acceptPreOrder(PreorderIterator i);
036        abstract Object acceptPostOrder(PostorderIterator i);
037        abstract Object acceptBreadth(BreadthIterator i);
038}
039
040class Const extends AbsExpr {
041        private final int v;
042        public Const(int v) {
043                this.v = v;
044        }
045        public int evaluate() {
046                return v;
047        }
048        Object acceptPreOrder(PreorderIterator i) {
049                return v;
050        }
051        Object acceptPostOrder(PostorderIterator i) {
052                i.markVisited(this);
053                return v;
054        }
055        Object acceptBreadth(BreadthIterator i) {
056                i.markVisited(this);
057                return v;
058        }
059}
060
061class BinOp extends AbsExpr {
062        private final AbsExpr l;
063        private final AbsExpr r;
064        private final Op op;
065        public BinOp(AbsExpr l, Op op, AbsExpr r) {
066                if ((l == null) || (op == null) || (r == null)) {
067                        throw new IllegalArgumentException();
068                }
069                this.op = op;
070                this.l = l;
071                this.r = r;
072        }
073        public int evaluate() {
074                return op.eval(l.evaluate(), r.evaluate());
075        }
076        Object acceptPreOrder(PreorderIterator i) {
077                i.addNode(r);
078                i.addNode(l);
079                return op;
080        }
081        Object acceptPostOrder(PostorderIterator i) {
082                i.markVisited(this);
083                if (i.visited(r)) {
084                        return op;
085                } else {
086                        i.addNode(this);
087                        if (i.visited(l))
088                                return r.acceptPostOrder(i);
089                        else
090                                return l.acceptPostOrder(i);
091                }
092        }
093        Object acceptBreadth(BreadthIterator i) {
094                if (i.visited(this)) {
095                        i.addNode(l);
096                        i.addNode(r);
097                        return i.next();
098                } else {
099                        i.markVisited(this);
100                        i.addNode(this);
101                        return op;
102                }
103        }
104}
105
106class PreorderIterator implements Iterator<Object> {
107        private Stack<AbsExpr> s = new Stack<AbsExpr>();
108        public boolean hasNext() {
109                return ! s.empty();
110        }
111        void addNode(AbsExpr e) {
112                s.push(e);
113        }
114        public Object next() {
115                if (hasNext())
116                        return (s.pop()).acceptPreOrder(this);
117                throw new NoSuchElementException();
118        }
119        public void remove() {
120                throw new UnsupportedOperationException();
121        }
122}
123
124class PostorderIterator implements Iterator<Object> {
125        private Set<AbsExpr> v = new HashSet<AbsExpr>();
126        private Stack<AbsExpr> s = new Stack<AbsExpr>();
127        public boolean hasNext() {
128                return ! s.empty();
129        }
130        boolean visited(AbsExpr e) {
131                return v.contains(e);
132        }
133        void markVisited(AbsExpr e) {
134                v.add(e);
135        }
136        void addNode(AbsExpr e) {
137                s.push(e);
138        }
139        public Object next() {
140                if (hasNext())
141                        return (s.pop()).acceptPostOrder(this);
142                throw new NoSuchElementException();
143        }
144        public void remove() {
145                throw new UnsupportedOperationException();
146        }
147}
148
149class BreadthIterator implements Iterator<Object> {
150        private Set<AbsExpr> v = new HashSet<AbsExpr>();
151        private List<AbsExpr> l = new ArrayList<AbsExpr>();
152        public boolean hasNext() {
153                return ! l.isEmpty();
154        }
155        boolean visited(AbsExpr e) {
156                return v.contains(e);
157        }
158        void markVisited(AbsExpr e) {
159                v.add(e);
160        }
161        void addNode(AbsExpr e) {
162                l.add(e);
163        }
164        public Object next() {
165                if (hasNext()) {
166                        AbsExpr e = l.get(0);
167                        l.remove(0);
168                        return e.acceptBreadth(this);
169                }
170                throw new NoSuchElementException();
171        }
172        public void remove() {
173                throw new UnsupportedOperationException();
174        }
175}
176