StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The <code>getNodes</code> and <code>getTree</code> functions would be pretty trivial to write under these constraints, so I just skipped ahead to the interesting part. You would naturally evaluate an expression tree recursively, but that is not an option here because the eval function only takes a string. Sure, you could restringify the remaining tree into a prefix expression and call eval recursively on that, but that would just be stupid.</p> <p>First, I convert the expression tree into a postfix expression, using an explicit stack as the poor man's recursion. Then I evaluate that with the standard operand stack.</p> <pre><code>#include <iostream> #include <vector> #include <string> using namespace std; #include "exptree.h" int evaluate(string d){ Node* tree = getTree(d); //convert tree to postfix for simpler evaluation vector<Node*> node_stack; node_stack.push_back(tree); Node postfix_head; Node* postfix_tail = &postfix_head; while(node_stack.size() > 0){ Node* place = node_stack.back(); if(place->left == 0){ if(place->right == 0){ postfix_tail->right = place; node_stack.pop_back(); } else { node_stack.push_back(place->right); place->right = 0; } } else { node_stack.push_back(place->left); place->left = 0; } } //evaluate postfix Node* place = postfix_head.right; vector<int> stack; while(place != 0){ if(place->op != NUM){ int operand_a, operand_b; operand_b = stack.back(); stack.pop_back(); operand_a = stack.back(); stack.pop_back(); switch(place->op){ case ADD: stack.push_back(operand_a + operand_b); break; case SUB: stack.push_back(operand_a - operand_b); break; case MUL: stack.push_back(operand_a * operand_b); break; case DIV: stack.push_back(operand_a / operand_b); break; } } else { stack.push_back(place->num); } place = place->right; } return stack.back(); } </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