Expression Tree

geeksforgeeks Evaluating the expression represented by expression tree:

Let t be the expression tree
If  t is not null then
      If t.value is operand then  
                Return  t.value
      A = solve(t.left)
      B = solve(t.right)

      // calculate applies operator 't.value' 
      // on A and B, and returns value
      Return calculate(A, B, t.value)

Construction of Expression Tree: Now For constructing expression tree we use a stack. We loop through input expression and do following for every character. 1) If character is operand push that into stack 2) If character is operator pop two values from stack make them its child and push current node again. At the end only element of stack will be root of expression tree.

#include <iostream>
using namespace std;

// An expression tree node
struct Node
{
    bool isOperand;
    int value;
    Node* left, *right;
    string op;
    Node(char x): val(x), isOperand(false), left(NULL), right(NULL) {}
};

bool computeRoot(Node* root) {
    if (!root) return false;
    if (root->isOperand) return root->val;
    bool a = computeRoot(root->left);
    bool b = computeRoot(root->right);
    return calculate(a, b, root->op);
}

int main() {
    return 0;
}