CODEWITHSUNDEEP
c++treeexpression
stef0526
stef0526

Reputation: 25

Printing an expression tree

I am able to print my expression tree in inorder. But I need to be able to print it in inorder with parenthesis. for example postorder 53+ should output (5+3)

I currently have:

void printTree(struct TreeNode *tree)
{
   if (tree != NULL)
    {
      if (isalpha(tree->info) || isdigit(tree->info))
        cout << "(";
      printTree( tree->left);
      cout<< tree->info;
      printTree(tree->right);
      if (isalpha(tree->info) || isdigit(tree->info))
        cout << ")";
    }
}

But this gives me incorrect output. If i enter postfix expression 62/5+ it gives me (6)/(2)+(5)

:(

Upvotes: 1

Views: 4077

Answers (2)

Jiri Kriz
Jiri Kriz

Reputation: 9292

You need to distinguish between leaf nodes and non-leaf nodes. Only non-leaf nodes are enclosed in parantheses.

bool isLeaf(struct TreeNode* tree) {
    return tree->left == 0 && tree->right == 0;
}

void printTree(struct TreeNode* tree) {
    if (tree != NULL) { // this test could be omitted if the printed tree is not empty
        if (isLeaf(tree)) {
            cout << tree->info;
        }
        else {
            cout << "(";
            printTree(tree->left);
            cout << tree->info;
            printTree(tree->right);
            cout << ")";            
        }
    }
}

Upvotes: 2

Sander De Dycker
Sander De Dycker

Reputation: 16243

Try reversing the if conditions that decide whether the parentheses should be printed :

void printTree(struct TreeNode *tree)
{
    if (tree != NULL)
    {
        if (!(isalpha(tree->info) || isdigit(tree->info)))
            cout << "(";
        printTree( tree->left);
        cout<< tree->info;
        printTree(tree->right);
        if (!(isalpha(tree->info) || isdigit(tree->info)))
            cout << ")";
    }
}

Or probably even better :

void printTree(struct TreeNode *tree)
{
    if (tree != NULL)
    {
        if (isoperator(tree->info))
            cout << "(";
        printTree( tree->left);
        cout<< tree->info;
        printTree(tree->right);
        if (isoperator(tree->info))
            cout << ")";
    }
}

where isoperator is appropriately defined to distinguish operators from operands.

Upvotes: 1

Related Questions