Databases
StackOverflow2013
Postsdbo
PONightmare Expression Tree with over-constrained class
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PONightmare Expression Tree with over-constrained class
    text
    copied!<p>I inadvertently let my students overconstrain a shared class used to solve the following problem. I realized it might be a problem denizens of this site might enjoy.</p> <p>The first team/function, getNodes, takes a string representing a prefix expression using signed integers and the four operations +, -, *, and / and produces the corresponding null terminated linked list of tokens, using the class Node, with tokens linked through the "right" pointer.</p> <p>The second team/function, getTree, takes a similar string, passes it to getNodes, and relinks the resultant nodes to be an expression tree.</p> <p>The third team/function, evaluate, takes a similar string, passes it to getTree, and evaluates the resultant expression tree to form an answer.</p> <p>The over-constrained exptree.h follows. The problem has to be solved by writing just the three functions defined above, no additional functions.</p> <pre><code>#ifndef EXPTREE_H_ #define EXPTREE_H_ using namespace std; enum Ops{ADD, SUB, MUL, DIV, NUM}; class Node { private: int num; Ops op; Node *left, *right; public: friend Node *getNodes(string d); friend Node *getTree(string d); friend int evaluate (string); }; int evaluate(string d); Node *getNodes(string d); Node *getTree(string d); #endif </code></pre> <p>The only libraries that can be used are these</p> <pre><code>#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;string&gt; #include "exptree.h" </code></pre> <p>For those of you worried about my students, I will be pointing out today how just a couple of more well placed functions would allow this problem to be easily solved. I know the expression tree can code rational numbers and not just integers. I'll be pointing that out today as well.</p> <p>Here is the driver program I gave them based on their specs.</p> <pre><code>#include &lt;iostream&gt; #include &lt;string&gt; #include "exptree.h" using namespace std; void test(string s, int target) { int result = evaluate(s); if (result == target) cout &lt;&lt; s &lt;&lt; " correctly evaluates to " &lt;&lt; target &lt;&lt; endl; else cout &lt;&lt; s &lt;&lt; "(" &lt;&lt; result &lt;&lt; ") incorrectly evaluates to " &lt;&lt; target &lt;&lt; endl; } int main() { test("42", 42); test("* - / 4 2 1 42", 42); test("* - / -4 +2 -1 2", -2); test("* - / -4 +2 -1 2 ", -2); test("* 9 6", 54); return 0; } </code></pre> <p>Can you write the three functions in as elegant a fashion as possible to solve this nightmarish problem?</p>
 

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