Professor Futrelle. Posted 1/11/99
Full projects on the Amabassador Mac server, in CodeWarrior.
/* * gcd 1201 w99 class * 1/6/99 RPF * File: gcd2.cp */ #include <iostream> int gcd(int, int); int gcd(int u, int v) { int t; while (u > 0) { if (u < v) { t = u; u = v; v = t; } u = u - v; } return v; } main() { int x, y; while (cin >> x && cin >> y) if (x>0 && y>0) cout << x << ' ' << y << ' ' << gcd(x,y) << '\n'; }
/* * gcd 1201 w99 class * 1/10/99 RPF * File: int-arr-stack.cp */ /* Simple non-template stack of integers using an array. Changed itemType in Sedg. to int. */ #include <iostream> class Stack { private: int *stack; int p; public: Stack(int max=100) { stack = new int[max]; p = 0; } ~Stack() { delete[] stack; } // added [] to delete every array el. inline void push(int v) { stack[p++] = v; } inline int pop() { return stack[--p]; } inline int empty() { return !p; } }; // Using the stack to evaluate postfix (reverse Polish) express. // such as 2 4 + (= 6) or 3 4 5 + * (= 23), etc. main () { char c; Stack acc(50); int x; while (cin.get(c) & (c != '\n')) // added: newline finishes it { x = 0; while (c == ' ') cin.get(c); if (c == '+') x = acc.pop() + acc.pop(); if (c == '*') x = acc.pop() * acc.pop(); while (c>='0' && c<='9') { x = 10*x + (c-'0'); cin.get(c); } acc.push(x); } cout << acc.pop() << endl; }
/* * gcd 1201 w99 class * 1/10/99 RPF * File: josephus.cp */ /* This is a useful file to run under the debugger, since it allows you to see the entire linked structure, with all the keys and pointer values. It can also trace the operation of the algorithm, of course. The book suggests using N=9 and M=5 as an example. */ // struct in Sedgewick has been changed to class // and public: added (struct is a class defaulting to public:) class node { public: int key; struct node *next; }; main() { int i, N, M; struct node *t, *x; cin >> N >> M; t = new node; t->key = 1; x = t; for (i = 2; i <= N; i++) { t->next = new node; t = t->next; t->key = i; } t->next = x; while (t != t->next) { for (i = 1; i < M; i++) t = t->next; cout << t->next->key << ' '; x = t->next; t->next = x->next; delete x; } cout << t->key << '\n'; }
/* * gcd 1201 w99 class * 1/10/99 RPF * File: parse-and-visit.cp * Based heavily on templated-arr-stack.cp */ /* Templated stack used for parse tree example, Sedg. pg. 41, basically the machinery in templated-arr-stack. This is followed by traversals of the tree in various orders. */ #include <iostream> struct node { char info; struct node *l, *r; }; node* z; // The "null" node, terminating all leaves. // Templated stack class, with one type "Type" template <class Type> class Stack { private: Type *stack; int p; public: Stack(int max=100) { stack = new Type[max]; p = 0; } // an array of Type ~Stack() { delete[] stack; } // added [] to delete every array el. inline void push(Type v) // must push object of Type { stack[p++] = v; } inline Type pop() // pop must return the Type { return stack[--p]; } inline int empty() { return !p; } }; // Visit will print out the node info followed by a space void visit(node*); void visit(node* nd) { cout << nd->info << ' '; } // Postorder traversal will reproduce the postorder expression. // The rule is visit the left, right, and root, in that order. // A recursive formulation is the simplest to write (pg. 60). void traverse_postorder(node*); void traverse_postorder(node* nd) { if (nd != z) // z is a global { traverse_postorder(nd->l); traverse_postorder(nd->r); visit(nd); } } // From the parse tree, pg. 41, it is clear that the bracketed form below it // can be printed out by the following rule: // If the node is + or *, print a ( then visit the left tree, then the operator, // then the right tree, then a paren. If not an operator, just visit the node. // This describes inorder-expression: void inorder_expression(node*); void inorder_expression(node* nd) { if (nd != z) { if ((nd->info == '*') || (nd->info == '+')) cout << "("; inorder_expression(nd->l); visit(nd); inorder_expression(nd->r); if ((nd->info == '*') || (nd->info == '+')) cout << ")"; } } // HERE IS MAIN() ********************************* main () { node *x; char c; Stack<node*> stack(50); // template Type is pointer to node z = new node; z->l = z; z->r = z; // the global value set here. cout << "After a postorder expression such as A B C + D E * * F + *" << '\n'; cout << "is typed in below, a parse tree is built from it.\n"; while (cin.get(c) && (c != '\n')) { while (c == ' ') cin.get(c); x = new node; x->info = c; x->l = z; x->r = z; if (c=='+' || c=='*') { x->r = stack.pop(); x->l = stack.pop(); } stack.push(x); } // x is now the top of the parse tree, so traverse it. cout << "\n\nHere is the tree after postorder traversal:\n\n"; traverse_postorder(x); cout << "\n\n\nHere is the expression by inorder traversal:\n\n"; inorder_expression(x); cout << '\n'; } /* If the following expression is entered interactively, A B C + D E * * F + * followed by a carriage return, then the parse tree can be examined in the debugger, stepped to the last char input, c = '*'. At that point the tree structure is exactly what is shown in Fig. 4.4 in the text. We can also follow the building of the tree by using the debugger, with the build sequence shown in Fig. 4.5. Use Show types in the Data menu of the debugger. To view the stack array, select the stack: node** field of the Stack class of the Variable window of the debugger and then select Open Array Window from the Data menu, and so forth. */ /* Here is a sample run: After a postorder expression such as A B C + D E * * F + * is typed in below, a parse tree is built from it. A B C + D E * * F + * Here is the tree after postorder traversal: A B C + D E * * F + * Here is the expression by inorder traversal: (A * (((B + C )* (D * E ))+ F )) */
/* * gcd 1201 w99 class * 1/10/99 RPF * File: templated-arr-stack.cp */ /* Templated stack used for parse tree example, Sedg. pg. 41 */ #include <iostream> struct node { char info; struct node *l, *r; }; // Templated stack class, with one type "Type" template <class Type> class Stack { private: Type *stack; int p; public: Stack(int max=100) { stack = new Type[max]; p = 0; } // an array of Type ~Stack() { delete[] stack; } // added [] to delete every array el. inline void push(Type v) // must push object of Type { stack[p++] = v; } inline Type pop() // pop must return the Type { return stack[--p]; } inline int empty() { return !p; } }; main () { node *x, *z; char c; Stack<node*> stack(50); // template Type is pointer to node z = new node; z->l = z; z->r = z; while (cin.get(c) && (c != '\n')) { while (c == ' ') cin.get(c); x = new node; x->info = c; x->l = z; x->r = z; if (c=='+' || c=='*') { x->r = stack.pop(); x->l = stack.pop(); } stack.push(x); } } /* If the following expression is entered interactively, A B C + D E * * F + * followed by a carriage return, then the parse tree can be examined in the debugger, stepped to the last char input, c = '*'. At that point the tree structure is exactly what is shown in Fig. 4.4 in the text. We can also follow the building of the tree by using the debugger, with the build sequence shown in Fig. 4.5. Use Show types in the Data menu of the debugger. To view the stack array, select the stack: node** field of the Stack class of the Variable window of the debugger and then select Open Array Window from the Data menu, and so forth. */