#include #include #include #include struct treenode { char op; // op=='N' if it reps a number int data; treenode * left, * right; treenode(char c, int n, treenode * l = NULL, treenode * r = NULL) { op=c; data=n; left=l; right=r; } }; void print_normally(treenode * T, ostream & fo) { if (T==NULL) { } else if (T->op=='N') fo << T->data << " "; else { fo << "( "; print_normally(T->left, fo); fo << T->op << " "; print_normally(T->right, fo); fo << ") "; } } void print_differently(treenode * T, ostream & fo) { if (T==NULL) fo << "@ "; else if (T->op=='N') fo << T->data << " "; else { fo << "( "; fo << T->op << " "; print_differently(T->left, fo); print_differently(T->right, fo); fo << ") "; } } treenode * read_normally(istream & fi) { char c; fi >> c; if (isdigit(c)) { fi.putback(c); int N; fi >> N; return new treenode('N', N); } else if (c=='(') { treenode * L = read_normally(fi); char op; fi >> op; treenode * R = read_normally(fi); fi >> c; if (c!=')') { cerr << "saw " << c << " when expecting )\n"; return NULL; } return new treenode(op, 0, L, R); } else { cerr << "first char " << c << " not ( or @\n"; return NULL; } } treenode * read_differently(istream & fi) { char c; fi >> c; if (isdigit(c)) { fi.putback(c); int N; fi >> N; return new treenode('N', N); } else if (c=='(') { char op; fi >> op; treenode * L = read_differently(fi); treenode * R = read_differently(fi); fi >> c; if (c!=')') { cerr << "saw " << c << " when expecting )\n"; return NULL; } return new treenode(op, 0, L, R); } else { cerr << "first char " << c << " not ( or @\n"; return NULL; } } void main() { treenode * collection = NULL; collection = read_normally(cin); cout << "differently: "; print_differently(collection, cout); cout << "\n"; cout << "normally: "; print_normally(collection, cout); cout << "\n"; }