StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>For what its worth, here is the solution I coded up just before I posted the question</p> <pre><code>#include <iostream> #include <vector> #include "exptree.h" using namespace std; Node *getNodes(string s) { const int MAXINT =(int)(((unsigned int)-1) >> 1), MININT = -MAXINT -1; Node *list; int sign, num; s += " "; // this simplifies a lot of logic, allows trailing white space to always close off an integer list = (Node *) (num = sign = 0); for (int i=0; i<s.size(); ++i) { char c = s[i]; // more efficient and cleaner reference to the current character under scrutiny if (isdigit(c)) { if (sign == 0) sign = 1; // if sign not set, then set it. A blank with a sign==0 now signifies a blank that can be skipped num = 10*num + c - '0'; } else if (((c=='+') || (c=='-')) && isdigit(s[i+1])) { // another advantage of adding blank to string above so don't need a special case sign = (c=='+') ? 1 : -1; } else if ( !isspace(c) && (c != '+') && (c != '-') && (c != '*') && (c != '/')) { cout << "unexpected character " << c << endl; exit(1); } else if (!isspace(c) || (sign != 0)) { // have enough info to create next Node list->left = (list == 0) ? (list = new Node) : (list->left->right = new Node); // make sure left pointer of first Node points to last Node list->left->right = 0; // make sure list is still null terminated list->left->op = (c=='+' ? ADD : (c=='-' ? SUB : (c=='*' ? MUL : (c=='/' ? DIV : NUM)))); // choose right enumerated type list->left->num = (list->left->op==NUM) ? sign*num : MININT; // if interior node mark number for evaluate function num = sign = 0; // prepare for next Node } } return list; } Node *getTree(string s) { Node *nodes = getNodes(s), *tree=0, *root, *node; vector<Node *> stack; if (nodes == 0) return tree; root = tree = nodes; nodes = nodes->right; for (node=nodes; node != 0; node=nodes) { nodes = nodes->right; if (root->op != NUM) { // push interior operator Node on stack til time to point to its right tree stack.push_back(root); root = (root->left = node); // set interior operator Node's left tree and prepare to process that left tree } else { root->left = root->right = 0; // got a leaf number Node so finish it off if (stack.size() == 0) break; root = stack.back(); // now pop operator Node off the stack stack.pop_back(); root = (root->right = node); // set its left tree and prepare to process that left tree } } if ((stack.size() != 0) || (nodes != 0)) { cout << "prefix expression has missing or extra terms" << endl; exit(1); } return tree; } int evaluate(string s) { // MININT is reserved value signifying operator waiting for a left side value, low inpact since at edge of representable integers const int MAXINT =(int)(((unsigned int)-1) >> 1), MININT = -MAXINT -1; Node *tree = getTree(s); vector<Node *> stack; int v = 0; // this is value of a leaf node (a number) or the result of evaluating an interior node if (tree == 0) return v; do { v = tree->num; if (tree->op != NUM) { stack.push_back(tree); tree = tree->left; // prepare to process the left subtree } else while (stack.size() != 0) { // this while loop zooms us up the right side as far as we can go (till we come up left side or are done) delete tree; // done with leaf node or an interior node we just finished evaluating tree = stack.back(); // get last interior node from stack if (tree->num == MININT) { // means returning up left side of node, so save result for later tree->num = v; tree = tree->right; // prepare to evaluate the right subtree break; // leave the "else while" for the outer "do while" which handles evaluating an expression tree } else { // coming up right side of an interior node (time to calculate) stack.pop_back(); // all done with interior node v = tree->op==ADD ? tree->num+v : (tree->op==SUB ? tree->num-v : (tree->op==MUL ? tree->num*v : tree->num/v)) ; } } } while (stack.size() != 0); return v; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload