CODEWITHSUNDEEP
c++binary-tree
Robert Li
Robert Li

Reputation: 1

My Tree based expression solver for C++ has weird issues with digits being overwritten?

so heres my header and cpp file.

template<typename T> struct TreeNode
{
   TreeNode(const T& value, TreeNode<T>* left = NULL, TreeNode<T>* right = NULL)
   {
      Value = value;
      Left = left;
      Right = right;
   }

   T Value;
   TreeNode<T>* Left;
   TreeNode<T>* Right;

   bool IsLeaf() const
   {
      return Left == NULL && Right == NULL;
   }
};

and now my cpp file 

#include "TreeNode.h"
#include <iostream>
#include <string>


using namespace std;

float ValueOf(TreeNode<char>* root);

float ValueOf(TreeNode<char>* root)
{
        if (root->IsLeaf()) 
            return root->Value - '0'; 
        float expressionValueL = ValueOf(root->Left);
        float expressionValueR = ValueOf(root->Right);

        if (root->Value == '+')
            return expressionValueL+expressionValueR;
        else if (root->Value == '-')
            return expressionValueL-expressionValueR;
        else if (root->Value == '*')
            return expressionValueL*expressionValueR;
        else if (root->Value == '/')
            return expressionValueL/expressionValueR;
}

void main ()
{
    TreeNode<char>* treeRoot = nullptr;
    TreeNode<char>* currentNode = treeRoot;
    string expr;

    cout<<"please input expression to be tested:";
    getline (cin, expr);
    cout<<endl;
    int size = expr.size();
    for (int i=0; i<size; i++)
    {
        char test = expr[i];
        if ((test=='1')||(test=='0')||(test=='2')||(test=='3')||(test=='4')||(test=='5')||(test=='6')||(test=='7')||(test=='8')||(test=='9'))
        {
            TreeNode<char> newLeaf = (expr[i]);

            if (currentNode == nullptr)
            {
                treeRoot=&newLeaf;
                currentNode = &newLeaf;
            }
            else
                currentNode->Right = &newLeaf;
        }
        else if ((expr[i]=='+')||(expr[i]=='-'))
        {
            TreeNode<char> newRoot = test;
            newRoot.Left = treeRoot;
            treeRoot = &newRoot;
            currentNode = &newRoot;
        }
        else if (((expr[i]=='*')||(expr[i]=='/'))&&(currentNode->Right==nullptr))
        {
            TreeNode<char> newRoot = test;
            newRoot.Left = treeRoot;
            treeRoot = &newRoot;
            currentNode = &newRoot;
        }
        else if (((expr[i]=='*')||(expr[i]=='/'))&&(currentNode->Right!=nullptr))
        {
            TreeNode<char> newChild = test;
            newChild.Left = currentNode->Right;
            currentNode->Right = &newChild;
            currentNode = &newChild;
        }


    }
    cout<<ValueOf(treeRoot)<<endl;

    system("pause");

}

the problem is that every time i run it, and i input something like 3*4-2, all of the digits in the tree gets overwritten to what the last digit inserted was, so its interpreted as 2*2-2 and gives me 2 as an answer, instead of 10 can anyone tell me what my problem is? thanks =).

btw this program assumes wellformed expressions and single digit numbers.

Upvotes: 0

Views: 196

Answers (2)

iammilind
iammilind

Reputation: 69988

As mentioned by Erik,

TreeNode<char> newLeaf = (expr[i]);

is a local stack variable; instead of do following:

TreeNode<char> *newLeaf = new TreeNode<char>(expr[i]);

And then assign to proper leg. Also, below condition,

if ((test=='1')||(test=='0')||(test=='2')||(test=='3')||(test=='4')||(test=='5')||(test=='6')||(test=='7')||(test=='8')||(test=='9'))

Can be squeezed to,

if(test >= '0' && test <= '9')

In the same way, you can also co-relate the last two else if() statements for better code

Upvotes: 0

Erik
Erik

Reputation: 91270

TreeNode<char> newLeaf = (expr[i]); creates an object on stack - it's invalidated when you leave the enclosing scope. You should not store pointers to such objects.

Use TreeNode<char> * newLeaf = new TreeNode<char>(expr[i]); - and corresponding for any other node that you assign to ->Right and ->Left - aka need to keep alive beyond the scope where you create them.

Upvotes: 3

Related Questions