Form expression to tree printer

[LucasRex]

I want to create a tree viewer from postfix expression and of course I'm stuck.

First the code:

#include <string>
#include <stack>

using namespace std;

struct Node {
    char data;
    Node *left, *right;

    Node(char data) {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

struct Trunk {
    Trunk *prev;
    string str;

    Trunk(Trunk *prev, string str) {
        this->prev = prev;
        this->str = str;
    }
};

void showTrunks(Trunk *p) {
    if (p == nullptr) {
        return;
    }
    showTrunks(p->prev);
    cout << p->str;
}

void printTree(Node *root, Trunk *prev, bool isLeft) {
    if (root == nullptr) {
        return;
    }

    string prev_str = "    ";
    Trunk *trunk = new Trunk(prev, prev_str);

    printTree(root->right, trunk, true);

    if (!prev) {
        trunk->str = "--";
    } else if (isLeft) {
        trunk->str = "---";
        prev_str = "   |";
    } else {
        trunk->str = "---";
        prev->str = prev_str;
    }

    showTrunks(trunk);
    cout << " " << root->data << endl;

    if (prev) {
        prev->str = prev_str;
    }
    trunk->str = "   |";

    printTree(root->left, trunk, false);
}

bool isOperator(char x) {
    switch (x) {
        case '+':
        case '-':
        case '/':
        case '*':
            return true;
    }
    return false;
}


Node parsingExp(string s) {
    Node *root;
    Node *root2;
    stack<Node> rootS;
    stack<char> stack;

    char prev;

    for (int i = 0; i < s.length(); i++) { // browse string
        if (isOperator(s[i])) { // check if is operator
            Node stackValN1 = rootS.top();
            rootS.pop();
            Node stackValN2 = rootS.top();
            rootS.pop();
            if (isOperator(prev)) { // test if previous char is operator
                // get stack of rootS and create sub node with it                root2 = new Node(s[i]);
                root2->left = new Node(stackValN1);
                root2->right = new Node(stackValN2);            }
            char stackVal1 = stack.top();
            stack.pop(); // put in stack
            char stackVal2 = stack.top();
            stack.pop();
            root = new Node(s[i]); // create node with operator
            root->left = new Node(stackVal1); // get value of stack
            root->right = new Node(stackVal2);
            rootS.push(*root); // put node created in stack

        } else {
            stack.push(s[i]); // if != operator put in stack
        }
        prev = s[i]; // actualise previous char of string
    }
    return *root2; //return root for printer
}

int main() {
    string postfixExp = "16*23/+";

    Node *rootFinal;

    // Programmaticaly :
    Node *root = new Node('+');
    root->left = new Node('/');
    root->right = new Node('*');
    root->left->left = new Node('2');
    root->left->right = new Node('3');
    root->right->left = new Node('6');
    root->right->right = new Node('1');

    *rootFinal = parsingExp(postfixExp);

    printTree(rootFinal, nullptr, false);

    return 0;
}

Second, my initial idea:

1) Get the postfix expression
2) Parse the expression
- If it is an operator create the node with the data contained in stack
- If it is an operator and the old character is also an operator then merge the nodes contained in another stack (see in function parsingExp)
- If it's a variable, put it in stack

3) Show tree

I have the hardwired version to create the tree, I would like to build the same from the expression.

I'm in trouble with the creation of the nodes and in particular on the creation of the superior node with the condition "If it is an operator and that the old character is also an operator".

Thanks for help.

[jonnin]

I am not sure I followed what you really wanted, but maybe this will help.
the pre, post, n notation for trees is when you do the recursion based off the current node.

consider a simple tree:

     +
    /   \
   1     2

in order (n fix) means to go left, current, right.
so you would go left, print 1, current, print +, right, print 2:
1 + 2 which is a fairly standard human math expression.
human form requires smarts to inject () around terms, though; its why it isn't used in computers, you always convert in and out of it if you bother to display that type.

preorder, I don't recall that it is useful for expression trees.
that would be current, left, right, + 1 2
that leaves post order, or reverse polish.
left, right, current is post order.
1 2 + which is correct RPN and works with the standard push operands, for operators pop the stack twice, do it, push result back, when only 1 entry on stack and nothing left to push that is final answer.
here that is push 1, push 2, + ... pop 2, pop 1, add, push 3 back. stack size is 1 and nothing left in equation, so you stop.

If you knew all that, then any issues come with building the tree correctly or doing these things correctly. I didn't try to follow and debug what you had yet ..

RPN is non deterministic. That means there are multiple correct answers for an equation. The algorithm used to build it will be deterministic unless you add a randomizer component, but you should evaluate what you generate to see if it is right, not compare it to an 'expected' answer. This is just math ... you can rearrange the input equation too, eg 2+1 and 1+2 ... larger equations can flip flop quite a few terms in RPN and give the same final answer.

[DizzyDon]

It seems easier with prefix notation.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

struct Node {
    char data;
    Node *left, *right;

    Node(char data, Node *left = nullptr, Node *right = nullptr)
       : data(data), left(left), right(right) { }
};

struct Trunk {
    Trunk *prev;
    string str;

    Trunk(Trunk *prev, string str) {
        this->prev = prev;
        this->str = str;
    }
};

void showTrunks(Trunk *p) {
    if (!p) return;
    showTrunks(p->prev);
    cout << p->str;
}

void printTree(Node *root, Trunk *prev = nullptr, bool isLeft = false) {
    if (!root) return;
    string prev_str = "    ";
    Trunk *trunk = new Trunk(prev, prev_str);
    printTree(root->right, trunk, true);
    if (!prev)
        trunk->str = "--";
    else if (isLeft) {
        trunk->str = "---";
        prev_str = "   |";
    } else {
        trunk->str = "---";
        prev->str = prev_str;
    }
    showTrunks(trunk);
    cout << " " << root->data << endl;
    if (prev) prev->str = prev_str;
    trunk->str = "   |";
    printTree(root->left, trunk, false);
}

bool isOperator(char x) {
    switch (x) {
        case '+': case '-': case '/': case '*': return true;
    }
    return false;
}

Node *tree_from_expr_r(const string& exp, size_t &ind) {
    if (ind == exp.size())
        return nullptr;

    char ch = exp[ind++];

    if (isOperator(ch)) {
        auto n_left  = tree_from_expr_r(exp, ind);
        auto n_right = tree_from_expr_r(exp, ind);
        return new Node(ch, n_left, n_right);
    }
    
    return new Node(ch);
}

Node *tree_from_expr(const string& exp) {
    size_t ind = 0;
    return tree_from_expr_r(exp, ind);
}

int main() {
#if 1
    string postfixExp = "16*23/+";
    string prefixExp = postfixExp;
    reverse(prefixExp.begin(), prefixExp.end());
    Node *root = tree_from_expr(prefixExp); //("+/32*61");
#else
#define _ new Node
    auto root =
        _('+',
            _('/',
                _('3'),
                _('2')
             ),
            _('*',
                _('6'),
                _('1')
             )
          );
#undef _
#endif

    printTree(root);

    return 0;
}

[LucasRex]

I understand the general idea, but I may have misstated my problem.

To start, I can generate this output with the code below:

Output :

        --- 1
    --- *
   |    --- 6
-- +
   |    --- 3
    --- /
        --- 2

Code :

    Node *root2 = new Node('/');
    root2->left = new Node('2');
    root2->right = new Node('3');

    Node *root3 = new Node('*');
    root3->left = new Node('6');
    root3->right = new Node('1');
    
    Node *root = new Node('+');
    root->left = new Node(*root2);
    root->right = new Node(*root3);

My problem is that I want to take my string expression :

16*23/+

and convert it to print the same tree after evaluation.

For that I use this function:

Node parsingExp(string s) {
    Node *root;
    Node *root2;
    stack<Node> rootS;
    stack<char> stack;

    char prev;

    for (char & i : s) { // browse string
        if (isOperator(i)) { // check if is operator
            Node stackValN1 = rootS.top();
            rootS.pop();
            Node stackValN2 = rootS.top();
            rootS.pop();
            if (isOperator(prev)) { // test if previous char is operator
                root2 = new Node(i);
                root2->left = new Node(stackValN1);
                root2->right = new Node(stackValN2);
            }
            char stackVal1 = stack.top();
            stack.pop(); // put in stack
            char stackVal2 = stack.top();
            stack.pop();
            root = new Node(i); // create node with operator
            root->left = new Node(stackVal1); // get value of stack
            root->right = new Node(stackVal2);
            rootS.push(*root); // put node created in stack

        } else {
            stack.push(i); // if != operator put in stack
        }
        prev = i; // actualise previous char of string
    }
    return *root2; //return root for printer
}

But with the return I can't display the tree. I can't find my error in the function and that's why I'm blocking.

[LucasRex]

Yes that's it.

I thought it would be easier to use the postFix expression.

I will study the solution.

Thank you for the help !

[DizzyDon]

I guess it's just as easy to do it from the postfix form.

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>

using namespace std;

struct Node {
    char data;
    Node *left, *right;

    Node(char data, Node *left = nullptr, Node *right = nullptr)
       : data(data), left(left), right(right) { }
};

struct Trunk {
    Trunk *prev;
    string str;

    Trunk(Trunk *prev, string str) {
        this->prev = prev;
        this->str = str;
    }
};

void showTrunks(Trunk *p) {
    if (!p) return;
    showTrunks(p->prev);
    cout << p->str;
}

void printTree(Node *root, Trunk *prev = nullptr, bool isLeft = false) {
    if (!root) return;
    string prev_str = "    ";
    Trunk *trunk = new Trunk(prev, prev_str);
    printTree(root->right, trunk, true);
    if (!prev)
        trunk->str = "--";
    else if (isLeft) {
        trunk->str = "---";
        prev_str = "   |";
    } else {
        trunk->str = "---";
        prev->str = prev_str;
    }
    showTrunks(trunk);
    cout << " " << root->data << endl;
    if (prev) prev->str = prev_str;
    trunk->str = "   |";
    printTree(root->left, trunk, false);
}

bool isOperator(char x) {
    switch (x) {
        case '+': case '-': case '/': case '*': return true;
    }
    return false;
}

Node *tree_from_rpn(const string& exp) {
    stack<Node*> st;
    for (char ch: exp) {
        if (isOperator(ch)) {
            auto n_left  = st.top();
            st.pop();
            auto n_right  = st.top();
            st.pop();
            st.push(new Node(ch, n_left, n_right));
        }
        else
            st.push(new Node(ch));
    }
    return st.top();
}

int main() {
    string postfixExp = "16*23/+";
    Node *root = tree_from_rpn(postfixExp);
    printTree(root);
}