expression_tree.cpp

#include "Expression_Tree.h"
#include <iostream>
#include <stack>
#include <string>
#include <iomanip>
using namespace std;

bool isDigit(char ch) {
    return (ch >='0' && ch <= '9');
}

bool isOperator(char c) {
    return (
        c == '+' || c == '-' ||
        c == '*' || c == '/' ||
        c == '^'
    );
}

void displayNode(ETNode* node){
    cout << "{ 'value': '" << node->value << "' " ;
    if( node->left ){
        cout << ", 'left': ";
        displayNode(node->left);
    }
    if( node->right ){
        cout << ", 'right'";
        displayNode(node->right);
    }
    cout << '}';
}

void displayNodeStack(stack<ETNode *> st) {
    cout << "[ ";
    while(!st.empty()){
        cout << endl;
        cout << "   " ;
        displayNode(st.top());
        st.pop();
        if(!st.empty()){
            cout << ", ";
        }
    }
    cout << " ]";
}

ETNode::ETNode(char value_) : value(value_), left(NULL), right(NULL) {}
ETNode::ETNode(char value_, ETNode* left_, ETNode* right_) : value(value_), left(left_), right(right_) {}

void Expression_Tree::build_expression_tree(char input[], int len) {
    stack<ETNode *> in_stack;
    ETNode *t, *right_operand, *operator_, *left_operand;

    for (int i = 0; i < len; i++) {
        cout << "input[ " << i << " ] = '" << input[i] << "'" << endl;
        cout << "in_stack = " ;
        displayNodeStack(in_stack);
        cout << endl;

        if(input[i] != ')') {
            t = new ETNode(input[i]);
            in_stack.push(t);
        } else {
            right_operand = in_stack.top();
            in_stack.pop();
            operator_ = in_stack.top();
            in_stack.pop();
            left_operand = in_stack.top();
            in_stack.pop();
            in_stack.pop(); // remove the left brace
            t = new ETNode(operator_->value, left_operand, right_operand);
            in_stack.push(t);
        }

        cout << "t = ";
        displayNode(t);
        cout << endl;
        cout << endl;

    }

    // finish off parsing the stack:
    cout << "finishing off stack" << endl ;

    while( in_stack.size() > 1 ) {
        cout << "in_stack = " ;
        displayNodeStack(in_stack);
        cout << endl;

        right_operand = in_stack.top();
        in_stack.pop();
        operator_ = in_stack.top();
        in_stack.pop();
        left_operand = in_stack.top();
        in_stack.pop();
        t = new ETNode(operator_->value, left_operand, right_operand);
        cout << "t = ";
        displayNode(t);
        cout << endl;
        in_stack.push(t);
        cout << endl;
    }

    root = in_stack.top();
}

void Expression_Tree::preorder(ETNode *p)
{
    if (p != 0) {
        visit(p);
        preorder(p->left);
        preorder(p->right);
    }
}

void Expression_Tree::postorder(ETNode *p)
{
    if (p != 0) {
        postorder(p->left);
        postorder(p->right);
        visit(p);
    }
}

void Expression_Tree::inorder(ETNode *p) {
    if (p != 0) {
        inorder(p->left);
        visit(p);
        inorder(p->right);
    }}

// virtual allows re-definition in derived classes
void Expression_Tree::visit(ETNode* p) {
    std::cout << p->value << " ";
}


void Expression_Tree::clear(ETNode *p)
{
    if (p != 0) {
        clear(p->left);
        clear(p->right);
        delete p;
    }
}