Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 756
  • Last Modified:

Help on Algorith for parsing an in put string in a binary tree

1. I am trying to insert for example    (-, (/, (*, 4, (+, 15, 10)), 7), 9)  which is in prefix form into a binary tree and display it in binary tree like this:
            | - |
            /---\
         | /|     | 9 |
       /---\    
    | * |   | 7 |    
    /  \
 | 4 |  |+|
        /  \
     |15|  |10|

2. Then from there i perform the Transversals( Preorder,inorder,postorder,etc)
Can someone with an algorithms on how to do it. If there is a sample caode will be fine. My problem is how to parse the input
The ideas is like this:
that on the first call of parseBinaryOperations,
the inputString is your entire string, and the return values would be:
operation = "-"
leftOperand = "(/, (*, 4, (+, 15, 10)), 7)"
rightOperand = "9"

Since leftOperand[0] = '(', then you know that you have to keep calling parseBinaryOperations (recursively - TBD). If the operand is not a '(', then you can insert a node.

I need help on this
thanks'
0
Atouray
Asked:
Atouray
  • 59
  • 55
  • 5
  • +1
1 Solution
 
cupCommented:
Are you intending to use C or C++ with or without STL or home-brew templates?  You many not be aware but there are several ways of doing this.

In C, you could split the line using strtok

In C++ with simple STL, you could use the find in string

A more complex template solution (which some people brand as 'elegant' but you need to know STL and templates quite well to understand it).  If you want to play with templates, you could specify a delimiter

template <char delimiter>
class Delim
{
   ...
   bool isdel(char c)
   {
      return eq(c, delimiter);
   }
};

Then tokenize using any character as a delimiter:

   basic_istringstream<char, my_char_traits<','> > tokenizer(' (-, (/, (*, 4, (+, 15, 10)), 7), 9)');

If you play around with iterators, copy and back_inserter and vectors, you could then get a vector of all the tokens in one statement (which some people call elegant).

Personally, if any C++ coder can't understand it in two seconds, the code isn't very maintainable but some people like the complexity; everyone is different.
0
 
cupCommented:
Sorry, it should have been

basic_istringstream<char, Delim<','> > tokenizer(' (-, (/, (*, 4, (+, 15, 10)), 7), 9)');

Problems of cutting and pasting from my test programs with totally random naming conventions.
0
 
AtourayAuthor Commented:
I want to use C to implement it. How can io do it with C please?
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
phoffricCommented:
I looked up prefix form definition. Prefix form has no parenthesis. Do you want the input to be prefix form or your form?
0
 
phoffricCommented:
from http://www.codeproject.com/KB/recipes/binary_tree_expressions.aspx?msg=1104406 :

* + 1 2 - 3 4
Expressions in prefix are solved by scanning the equation for an operator with two immediate values to the right of it. This is continued and repeated until there are no more operators left.

So a parsePrefixForm function would have a prefix form input "* + 1 2 - 3 4" and return the operator and the left and right operands:
op = "*"
left = "+ 1 2"
right = "- 3 4"

Since left starts with an operator, then use parsePrefixForm on left to yield:
op = "+"
left = 1
right = 2

Since right starts with an operator, then use parsePrefixForm on right to yield:
op = "-"
left = 3
right = 4


0
 
AtourayAuthor Commented:
I need it to be in my form(With parentise).
0
 
phoffricCommented:
In that case, input to parseExpr() is "(-, (/, (*, 4, (+, 15, 10)), 7), 9)"
op = "-"
left = "/, (*, 4, (+, 15, 10)), 7"
right = "9"     <==  Since this is a number string, we are done parsing this string.

Since left = "/, (*, 4, (+, 15, 10)), 7" starts with an operator, then use parseExpr() on it to yield:
op = "/"
left = "*, 4, (+, 15, 10)"
right = "7"   <==  Since this is a number string, we are done parsing this string.

Since left = "*, 4, (+, 15, 10)" starts with an operator, then use parseExpr() on it to yield:
op = "*"
left = "4"   <==  Since this is a number string, we are done parsing this string.
right = "+, 15, 10"

Since right = "+, 15, 10" starts with an operator, then use parseExpr() on it to yield:
op = "+"
left = "15"    <==  Since this is a number string, we are done parsing this string.
right = "10"  <==  Since this is a number string, we are done parsing this string.
0
 
AtourayAuthor Commented:
So we should  use stack to implement parseExpr()  perser, right?
0
 
phoffricCommented:
Why? If parseExpr() is a fairly basic parser doing just what the above says, then I'm not sure why you want a stack. Maybe a higher level function would need a stack?
0
 
AtourayAuthor Commented:
I am seeking for both C++ and C solution. if it is going to confuse the experts, then i seek for only C++ solution then.
Thanks
0
 
AtourayAuthor Commented:
Sorry about that. Either of them is fine for me. Both C/C++ is fine.
0
 
AtourayAuthor Commented:
Thanks
0
 
js-profiCommented:
More confusing than the tags is the syntax of the input string. Why |4| and |+| are on same level?
0
 
AtourayAuthor Commented:
we are trying to follow this break down here: html#26115977. That is how the perse should work. I don't know if i answer your question.
0
 
AtourayAuthor Commented:
i want to give up on this thread. I am not getting the help i need here. I though i was going to get help, but this topic has been dragging for long now. I have to post the same question three time and still no one is able to get me a solution.
0
 
phoffricCommented:
js-profi: re: "Why |4| and |+| are on same level?"

What is shown is a Binary Expression Tree. The subtree:
    | * |
    /  \
 | 4 |  |+|
        /  \
     |15|  |10|
means in prefix notation: "* 4 + 15 10"
~  * 4 (+ 15 10)
~ 4 * (15+10) = 4*(25) = 100

0
 
js-profiCommented:
You could use a C++ tree like the one in code window. If it is homework we would develop the Formula::parse function step by step.
enum Operator 
{ NONE = '\0', 
  PLUS = '+', 
  MINUS = '-', 
  DIVIDE = '/', 
  MULTIPLY = '*' 
};

class Operation
{
   Operator op;
   Operation * left;
   Operation * right;
   Operation() : op(NONE), left(NULL), right(NULL) {}
   friend class Formula;
};

class Formula
{
   Operation root;
public:
   Formula() {}
   Formula(const std::string & f) { parse(f); }
   void parse(const std::string & f);
  
};

Open in new window

0
 
js-profiCommented:
Forgot to handle the case where Operation is a constant. could be done by adding a double member to Operation. Or like  
class Operation 
{  
protected:  
   Operator op;
   Operator() op(NONE){}
   friend class Formula; 
};

class Expression : public Operation
{
   Operation * left; 
   Operation * right; 
   Expression() : left(NULL), right(NULL) {} 
   friend class Formula; 
}; 
 
class ConstantTerm : public Operation
{
   double val;
   ConstantTerm() : val(0.0) {} 
   friend class Formula; 
};

Open in new window

0
 
AtourayAuthor Commented:
Is this the perser to perse the input string "(-, (/, (*, 4, (+, 15, 10)), 7), 9)"?
which of the two codes does it and how do you run it?
0
 
js-profiCommented:
The parse function would take the root (which must be turned to an Expression in case of taking the virtual concept) and pass it together with the string argument to a function parseExpression.

bool Formula::parseExpression(Operation * ptrOper, const std::string f);

void Formula::parse(const std::string f)
{
    parseExpression(&root, f);
}

The parseExpression would check if the formula properly was enclosed in parantheses. Then would parse the operator and the operands. When a operand with parantheses was detected a new Expression was created and the parseExpression was called recursively using the substring. In case of a constant the ConstantTerm operation was created. If no syntax error occurs the final return would be true.
0
 
js-profiCommented:
Probably you should use the

class Operation
{
   Operator op;
   Operation * left;
   Operation * right;
   double val;
   Operation() : op(NONE), left(NULL), right(NULL), val(0.0) {}
   friend class Formula;
};

for first approach to make it simpler.

0
 
AtourayAuthor Commented:
I think i got my perser working, now i just want to be able to display the tree like this:
             | - |
            /---\
         | /|     | 9 |
       /---\    
    | * |   | 7 |    
    /  \
 | 4 |  |+|
        /  \
     |15|  |10|
I need some to help me on how to display it in graphic as above in Dos.
thanks
0
 
js-profiCommented:
how did you store the tree? Without knowing the structures we can't help transverse.
0
 
AtourayAuthor Commented:
Here is my perser:
Can you please check it out for me and help me on Printing the binary tree like i suggested, like this:
    | - |
            /---\
         | /|     | 9 |
       /---\    
    | * |   | 7 |    
    /  \
 | 4 |  |+|
        /  \
     |15|  |10|
on Dos.
Thanks

perser.txt
0
 
AtourayAuthor Commented:
I just need to be able to print the binary Tree in DOS as i suggested and not the preorder, inorder etc.
I want to see how my individual string a placed.
thanks
0
 
js-profiCommented:
The con, ImS, Tn, nouvelN, nowN, .... are not defined. I get 43 errors when compiling your code. it is not good code even if it works for your sample. why using so much global variables? why not using recursive calls? what is ImS? a stack or a queue? don't think it is right container for a binary tree.
0
 
AtourayAuthor Commented:
the imS is defined as :vector<string> imS;
Tn is define and initialises as :node* Tn=NULL;
nowN is defined as:node* nowN=NULL;
struct node* nouvelN(string); -definition
the structure is
struct node {
    string val;
    struct node* right;
    struct node* left;
struct node* parent;
};
ImS is a stack.
here is
struct node* nouvelN(string val){
      node* node = new (struct node);
      node->val = val;
      node->left = NULL;
      node->right = NULL;
      node->parent = NULL;
      return node;
}
I hope i have given you enough information to complile now.
thanks
0
 
AtourayAuthor Commented:
Can someone help me on this please. I need to know how to print a binary tree in graphic form in C++ on the console or any how as shown in the structure above.
Thanks
0
 
js-profiCommented:
A vector<string> isn't a binary tree. the information which node has left or right child node is not stored.
you need a binary tree class like the one I posted or a template bintree class.

normally it is better to print a tree horizontally in dos box cause depth of a tree normally is much less than width. if depth is 4 width is 2^4 == 16 what makes up to 31 (16 operands + 15 for slashes) lines for display.

in your case the tree is degenerated as only rarely a node has two branches. So you also could think of a vertical display as suggested. but you can't rely on the degeneration. if 6 nested paranthesis and each operation has left and right suboperation your last line would need 127 chars (64 operands + 63 spaces) for last line if any operand is one single char. If you want to print constants as well you would need to replace the constants found by a, b, c ...
0
 
js-profiCommented:
is imS and ImS different??? what is the binary tree?
0
 
AtourayAuthor Commented:
yes, imS and ImS are the same. sorry about that. The binary tree is Tn.
So you mean my fucntion is not greating a binary tree? if so how could i have done it, resubmit your modification that can correct it please.
thanks
0
 
js-profiCommented:
ok, if the binary tree is Tn we have a root node which could be looked on as a tree.

to print tree vertically we need some helpers. first is the depth of tree.

int depth(struct node* n)
{
    int ld = 1;
    int rd = 1;
    if (n->left != NULL) ld = depth(n->left)+1;
    if (n->right != NULL) rd = depth(n->right)+1;
    return ld < rd? rd : ld;
}

If you would like to consider degeneration you also would need to calculate most left node and its difference in levels to the root. Same for right side. first approach is to not optimize the tree regarding degeneration. we should omit the || and use placeholders a, b, c for constants.  


0
 
AtourayAuthor Commented:
So how does this function help in  printing the binary tree and what is its connection wityh the code i sent you. Can you please include it in the code i submitted with the link, so that i can better understand. you can resunmit the code.lease
0
 
js-profiCommented:
I only have a browser in the moment. Maybe i find time later when i am at home. the depth we need to calculate the indent of the root -node value. So if we have depth 5 like in your sample we need to display up to 16 leafs at bottom line. So the root val needs an indent of 31 chars and the tree looks

 
-
                       /--------------\
               /                              9
           /------\
       *              7
     /---\
   4       + 
          /-\
         A   B

A = 10
B = 15

Open in new window

0
 
js-profiCommented:
the - in first line had 31 spaces at the left.
0
 
js-profiCommented:
Probably the below is better
R              - 
       /---------------\ 
       /               9 
   /-------\ 
   *       7
 /---\ 
 4   +  
    /-\ 
    A B 

A = 10
B = 15

Open in new window

0
 
AtourayAuthor Commented:
This will be good. Can you tell me how i can achieve this. Please show mw a sample code or better place it on my code and resubmit it. this will solve my problem. Please i am waiting.
thanks
0
 
js-profiCommented:
i have only a browser for now as told. but the function to print is not so difficult. you also should answer the q. whether it is  some kind of academical assignment. we would need to elaborate the code together in that case.

look at the code which is some kind of prototype.
void displayTree(struct node * n, size_t indent, size_t nlin, 
                 std::vector<std::string> lines)
{   
   int d = depth(n);
   if (depth == 1)
   {
       std::string val = n->val;
       if (val.size() > 1)
           val = nextConstant(val);  // manages constants  
       while (nlin >= lines.size())
           lines.push_back(std:.string(""));
       std::string & curline = lines[nlin];
       curline.resize(indent, ' ');
       curline += n->val;
       return; 
   }
   if (n->left != NULL)
   {
       // calculate indent to left subnode
       ...
       // add the /----\ to next line using the left indent
       ...
       // call displayTree recursively passing left node, 
       // new indent, nlin + 2
       ...
       // do similar for right node       
   }
}

Open in new window

0
 
js-profiCommented:
it is std::vector<std::string> & lines
0
 
AtourayAuthor Commented:
Hi js-profi;
i don't  seem to understand but check what i am trying to do. I would like you to complete the code for calculation indent to left subnode for me to see, i will do the right node. I don't understand this comments you made:
// calculate indent to left subnode
       ...
       // add the /----\ to next line using the left indent
       ...
       // call displayTree recursively passing left node,  
       // new indent, nlin + 2
Please help me on that
Thanks

void displayTree(struct node * n, size_t indent, size_t nlin,  
                 std::vector<std::string> & lines) 
{    
   int d = depth(n); 
   if (depth == 1) 
   { 
       std::string val = n->val; 
       if (val.size() > 1) 
           val = nextConstant(val);  // manages constants   
       while (nlin >= lines.size()) 
           lines.push_back(std:.string("")); 
       std::string & curline = lines[nlin]; 
       curline.resize(indent, ' '); 
       curline += n->val; 
       return;  
   } 
   if (n->left != NULL) 
   { 
    int ld = 1;
    int rd = 1;
    ld = depth(n->left)+1;// calculate indent to left subnode 
       ... 
       // add the /----\ to next line using the left indent 
       ... 
       // call displayTree recursively passing left node,  
       // new indent, nlin + 2 
       ... 
       // do similar for right node        
   } 
}

Open in new window

0
 
AtourayAuthor Commented:
Hi js-profi;
i would be glad if you can complete your code. It seems when you complete the code, my problem will be solved. I need to see how you will do this, because i have been trying to do this  but can't. Please remember, i am a complete newbies in C++, so i need to learn from experts like you.
So please come your code for me to see how you will achieve this:
R              -  
       /---------------\  
       /               9  
   /-------\  
   *       7
 /---\  
 4   +  
    /-\  
    A B  
 
A = 10
B = 15
Thanks
0
 
AtourayAuthor Commented:
Please this is not academic, so please don't think you are doing an assignment. You are merely help out a newbie in C++ who is trying to learn from experts.
0
 
js-profiCommented:
ok. i'll think i'll find some time today.

you could add the functions and try to compile

std::string nextConstant(const std::string& val)
{
     static char constant = 'A';
     static std::string  constants;
     // return all vals if empty input
     if (val.empty) return constants;
     // add val to all constants
     constants += constant;
     constants += " = ";
     constants += val;
     constants += "\n";
     std::string ret(1, constant);
     // increment for next constant
     constant++;
     return ret;

}

void display()
{
      if (Tn == NULL  || Tn->val.empty()) return;
      size_t d = depth(Tn);
      size_t i   = (1<<(d-1))-1;  // calculate indent for root
      std::vector<std::string> all;
      displayTree(Tn, i, 1, all);

      std::string::iterator lin;
      for (lin=all.begin(); lin != all.end(); ++lin)
            std::cout << (*lin) << std::endl;
      std::cout << nextConstant("");  // get all constants if any
}

0
 
AtourayAuthor Commented:
Thanks for this, but the i am unable to complete the function displayTree. So i don't think i can run it, because you are calling it in void display(). So can you please just complete the displayTree function, and i will check to see if it works the magic.
Thanks
0
 
js-profiCommented:
what you got should compile. we must do it together or you wouldn't learn from. also the functions already given you must understand. add comments so that i could verify.
0
 
AtourayAuthor Commented:
In the displayTree function, you indicated these comments:
ld = depth(n->left)+1;// calculate indent to left subnode  
       ...  
       // add the /----\ to next line using the left indent  
       ...  
       // call displayTree recursively passing left node,  
       // new indent, nlin + 2  

I tried to calculate indent to left subnode  using this:ld = depth(n->left)+1;. Is that correct?
I don't know how to do this one:  // add the /----\ to next line using the left indent and
// call displayTree recursively passing left node,  
       // new indent, nlin + 2  
I really need your help on this:
If i see your code i learn from it and try applying it on other ways. That is what i am doing and that is why i ask yoy to complete your code for me and i will apply it on other ways that i am pracising.
Thanks
 
0
 
AtourayAuthor Commented:
I also tried to compile your code, but i ran into bunch of errors. Below are the errors:
Error      1      error C3867: 'std::basic_string<_Elem,_Traits,_Ax>::empty': function call missing argument list; use '&std::basic_string<_Elem,_Traits,_Ax>::empty' to create a pointer to member      

Error      2      error C2446: '==' : no conversion from 'int' to 'int (__cdecl *)(node *)'      

Error      3      error C2040: '==' : 'int (__cdecl *)(node *)' differs in levels of indirection from 'int'      

Error      4      error C2882: 'std' : illegal use of namespace identifier in expression      

Error      5      error C2143: syntax error : missing ')' before ':'      

Error      6      error C2059: syntax error : ')'      

Error      7      error C2143: syntax error : missing ')' before ';'      

Error      8      error C2679: binary '=' : no operator found which takes a right-hand operand of type 'std::_Vector_iterator<_Ty,_Alloc>' (or there is no acceptable conversion)      

Error      9      error C2679: binary '!=' : no operator found which takes a right-hand operand of type 'std::_Vector_iterator<_Ty,_Alloc>' (or there is no acceptable conversion)      

What is coursing such errors? I am using visual studio 2008, express  edition.
thanks
0
 
js-profiCommented:
The errors are cause i have no compiler but only browser probably most are typos. would need the wrong statement added to the errors (or your code with line numbers and line numbers with the errors)-
0
 
js-profiCommented:
ld = depth(n->left) -1  is not correct. it would give 3 for second level what is the number of levels below.

The indent from left margin to most left node is 15 for root level and 7 for second level and 3 for  third level and 1 for fourth level and 0 for fifth level. that calculates by

    (2^(depth-1)) - 1

2^x   can be calculated in c/c++ by  1<<x.

look at my display function to see the calculation for the top level.

but, we don't need indent from left margin to most left node of level but indent relative to current intend for left node of current node. if you count the chars of sample tree you'll see that current indent of top level is 15 and you have to go -8 for next indent. 8 is 2^3 where 3 is depth(n->left)-1. so next left indent is

   cur_indent - ((2^(cur_depth-2))

and right indent by using +.

for lower levels you don't need to call depth function for left and right node as it is simply +1 to the current depth.  
0
 
AtourayAuthor Commented:
Hum..., any code to show what you are explaining to me?
It will be easier for me to follow.
0
 
js-profiCommented:
   size_t nextindent = indent - (1<<(d-2));
0
 
js-profiCommented:
easier? look, i could give you all code but wouldn't help you for next program. better try to understand code and explanations and ask for help on a specific statement.
0
 
AtourayAuthor Commented:
I did not get you, Sorry, i must say it again, i am a complete newbie in C++. Please just be patient with me, i am learning. It is better you give me the code of what you explaining, or better still complete it in the incmplete code you post here, then i will read it and understand what you were saying. I really don't understand and i don't even know how to do it. I think i will really learn if you give me that code. You think if you do that i will not learn , but i will surely learn. Maybe people's learning style are different.
0
 
js-profiCommented:
if you are a complete newbie, i. e. it is your first program?, the task seems to heavy. we can't make a tutorial here in a thread where any simple c statement was explained. i am patient but you must go my way or look for other. next steps are
- try to compile
- post errors if any
- implement next statement where i made ...
- ask for that statement if it is not clear

look i can't give you full code as it would offend ee rules.
0
 
AtourayAuthor Commented:
Ok. then lets go by your way.
Check this out. I hope i understand what you said. Am i correct? If not how should i have done it?

std::string nextConstant(const std::string& val)
{
     static char constant = 'A';
     static std::string  constants;
     // return all vals if empty input
     if (data.empty()) return constants;
     // add val to all constants
     constants += constant;
     constants += " = ";
     constants += val;
     constants += "\n";
     std::string ret(1, constant);
     // increment for next constant
     constant++;
     return ret;

}
int depth(struct node* n) 
{
    int ld = 1;
    int rd = 1;
    if (n->left != NULL) ld = depth(n->left)+1;
    if (n->right != NULL) rd = depth(n->right)+1;
    return ld < rd? rd : ld;
}

void displayTree(struct node * n, size_t indent, size_t nlin,  
                 std::vector<std::string> & lines) 
{    
   int d = depth(n); 
   if (depth == 1) 
   { 
	   std::string data = n->data; 
       if (data.size() > 1) 
           data = nextConstant(data);  // manages constants   
       while (nlin >= lines.size()) 
           lines.push_back(std:.string("")); 
       std::string & curline = lines[nlin]; 
       curline.resize(indent, ' '); 
	   curline += n->val; 
       return;  
   } 
   if (n->left!= NULL) 
   { 
       // calculate indent to left subnode 
      size_t nextindent = indent - (1<<(d-2));
       // add the /----\ to next line using the left indent 
       cout << "/----\" << endl;
       // call displayTree recursively passing left node, 
       displayTree((Tn);
       // new indent, nlin + 2 
      size_t nextindent = indent + (1<<(d-2));
      cout << "/----\" << endl;
//       // do similar for right node        
   } 
} 

void display()
{
	if (Node_tree == NULL  || Node_tree->data.empty()) return;
      size_t d = depth((Tn);
      size_t i   = (1<<(d-1))-1;  // calculate indent for root
      std::vector<std::string> all;
      displayTree(Tn, i, 1, all);

      std::string::iterator lin;
      for (lin=all.begin(); lin != all.end(); ++lin)
            std::cout << (*lin) << std::endl;
      std::cout << nextConstant("");  // get all constants if any
}

Open in new window

0
 
AtourayAuthor Commented:
I still have the above errors i mentioned in post number: ID: 26179367. IT is complaining of:
error C2446: '==' : no conversion from 'int' to 'int (__cdecl *)(node *)' due to the expression:
  if (depth == 1)
   { ..
error C2679: binary '=' : no operator found which takes a right-hand operand of type 'std::_Vector_iterator<_Ty,_Alloc>' (or there is no acceptable conversion)      due to the expression:
for (lin=all.begin(); lin != all.end(); ++lin)
I can't seems to know the reason why this errors? Do you know why?
Thanks


0
 
AtourayAuthor Commented:
I don't get it still with the current method. I am giving up on this method. I am trying this other method of printing a binary tree:
<->
 +--</>
 |   +--<*>
 |   |   +--<4>
 |   |   +--<+>
 |   |       +--<15>
 |   |       +--<7>
 |   +--<9>
 +--<10>

Can anyone help me on this method please.
Thanks
0
 
js-profiCommented:
i corrected the errors from your code. try to get it compiled at your system and post the errors.

std::string nextConstant(const std::string& val) 
{ 
     static char constant = 'A'; 
     static std::string  constants; 
     // return all vals if empty input 
     if (val.empty()) return constants; 
     // add val to all constants 
     constants += constant; 
     constants += " = "; 
     constants += val; 
     constants += "\n"; 
     std::string ret(1, constant); 
     // increment for next constant 
     constant++; 
     return ret; 
 
} 
int depth(struct node* n)  
{ 
    int ld = 1; 
    int rd = 1; 
    if (n->left != NULL) ld = depth(n->left)+1; 
    if (n->right != NULL) rd = depth(n->right)+1; 
    return ld < rd? rd : ld; 
} 
 
void displayTree(struct node * n, size_t indent, size_t nlin,   
                 std::vector<std::string> & lines)  
{     
   int d = depth(n);  
   if (d == 1)  
   {  
        std::string data = n->data;  
       if (data.size() > 1)  
           data = nextConstant(data);  // manages constants    
       while (nlin >= lines.size())  
           lines.push_back(std::string(""));  
       std::string & curline = lines[nlin];  
       curline.resize(indent, ' ');  
           curline += n->data;  
       return;   
   }  
   if (n->left!= NULL)  
   {  
       // calculate indent to left subnode  
      size_t nextindent = indent - (1<<(d-2)); 
       // add the /----\ to next line using the left indent  
      cout << "/----\\" << endl; 
       // call displayTree recursively passing left node,  
      displayTree(n->left, nextindent, nlin+2, lines); 
       // new indent, nlin + 2  
      cout << "/----\\" << endl; 
//       // do similar for right node         
   }  
}  


void display() 
{ 
      if (Node_tree == NULL  || Node_tree->data.empty()) return; 
      size_t d = depth(Node_tree); 
      size_t i   = (1<<(d-1))-1;  // calculate indent for root 
      std::vector<std::string> all; 
      displayTree(Node_tree, i, 1, all); 
 
      vector<string>::iterator lin; 
      for (lin=all.begin(); lin != all.end(); ++lin) 
            std::cout << (*lin) << std::endl; 
      std::cout << nextConstant("");  // get all constants if any 
}

Open in new window

0
 
AtourayAuthor Commented:
I have compiled and there is no error. But when i called display in my main to print the tree, it gives me the following error:
error C2660: 'display' : function does not take 1 arguments

my tree is stored in Node_tree and when is called display like display(Node_tree) in my main so that it can disply the tree, i give me the above error.
any idea ihow i can called the function that prints my tree in your code?
      
0
 
js-profiCommented:
error C2660 is a compile error. the display function currently has no argument but assumed a global variable to exist called Node_tree. it is better to change that cause global variables are not so good.

use

 void display(node * n)
 {
     if (n == NULL || n->data.empty())
     ...
 }

and replace all Node_tree in display function with n.

then you can call display(Node_tree) in main.

the output won't be correct til now cause we didn't implement right branch in displayTree.
0
 
AtourayAuthor Commented:
Yea, the output is not correct. It looks like the what i attached.
for the implementation of the right branch, is it not going to be like this

/size_t nextindentr = indent + (1<<(d-2));
 // add the /----\ to next line using the left indent  
      cout << "/----\\" << endl;
   //call displayTree recursively passing left node,  
  displayTree(n->right, nextindentr, nlin+2, lines);
       // new indent, nlin + 2  
      cout << "/----\\" << endl;
. Or how should it be written?

output.doc
0
 
js-profiCommented:
have only browser cannot download doc. please copy output from console to clipboard and post as code snippet.

regarding code: the "/------\\" is already written. don't need again (and never twice). rest looks ok but should compile.



 
0
 
AtourayAuthor Commented:
The code is compiling, but the output is not correct. i decided to simply the input to (1,2,3),
but i have the below is output.
I don't think it is correct.

Doc1.doc
0
 
AtourayAuthor Commented:
The output, please check.
sorry here is what you ask for:
the output, after inputing (1,2,3),
          1
       2     3/----\
/----\
the output after inputting this:("(1,(2,3,),(5,,7))")
          1
       2       3     5     7/----\
/----\
/----\
The out put after inputting this:("(-, (/, (*, 4, (+, 15, 10)), 7), 9)")
          -
               /               *        4           +        15      10      7
    9/----\
/----\
/----\
/----\
/----\
/----\
/----\
I don't think this is tree structure.




2 3

Open in new window

0
 
js-profiCommented:
ok. first error is
        2     3/----\
the /----\ should be in line before.

the displayTree must not use cout statements but fill the lines vector. see my code for displaying the botton leafs (d == 1). the problem with cout is that you can't go back. but in a real tree we would go down and up.

0
 
js-profiCommented:
that means the output is made in display by showing all lines of the vector.

in displayTree we need to fill the string lines nlin and nlin+1 using the calculated or given indents.

   // first check if vector already has a line
   if (nlin == 0 || nlin >= lines.size())
       lines.resize(nlin+2);
   // then get a reference of line string at nlin.
   std::string & line = lines[nlin];  
   if (line.size() < indent)
       line.resize(indent, ' ');   // offset with blanks
    std::string data = n->data;  
    if (data.size() > 1)  
    data = nextConstant(data);  // manages constants    
    line = line.substr(0, indent) + data;
    std::string & nline = lines[nlin+1];
    if (nline.size() < nextindentl)
         nline.resize(nextindentl, ' ');   // add spaces up to left indent
    nline = nline.substr(0, nextindentl);
    nline += "/";
    nline.resize(nextindentr, '-');
    nline += "\\";
0
 
AtourayAuthor Commented:
Now i have removed all the cout statement in the displayTree function amd the run, i still have the output like below. This are still not a tree.
 for (1,2,3),
         1
       2     3


2 3

for ("(1,(2,3,),(5,,7))")
          1
       2       3     5     7

for

for ("(-, (/, (*, 4, (+, 15, 10)), 7), 9)")
          -
               /               *        4           +        15      10      7
    9

so what is the problem again?

Open in new window

0
 
js-profiCommented:
first do all outputs to code snippet box or formatting is wrong.

next, can you put your latest code to the code snippet box.
0
 
AtourayAuthor Commented:
now i am geting something i am getting something like this:

-
       /       *        4     +       15     10     7     9
               -
       /---------------\
       /               9
   /-------\
   *       7
 /---\
  4  +
    /-\
    1510
A =  4
B = 15
C = 10

This is good, but only one issue and that is the figures that print on top such as:-
       /       *        4     +       15     10     7     9
i don't need them there, just the tree:
 -
       /---------------\
       /               9
   /-------\
   *       7
 /---\
  4  +
    /-\
    1510
A =  4
B = 15
C = 10
i don't know why they are printed on top

Open in new window

0
 
js-profiCommented:
the figures must be some other output. can you post all your code?

the 1510 is wrong should be A B.  The ' 4' is because the data contains a leading space. could you get rid of it when parsing?
 
0
 
js-profiCommented:
in display you could

    cout << endl << "-----------------------------------------------------" << endl;

what sould separate the tree from parsing output.
0
 
AtourayAuthor Commented:
Here is the entire code for the tree printing:

std::string nextConstant(const std::string& val) 
{ 
     static char constant = 'A'; 
     static std::string  constants; 
     // return all vals if empty input 
     if (val.empty()) return constants; 
     // add val to all constants 
     constants += constant; 
     constants += " = "; 
     constants += val; 
     constants += "\n"; 
     std::string ret(1, constant); 
     // increment for next constant 
     constant++; 
     return ret; 
 
} 
int depth(struct node* n)  
{ 
    int ld = 1; 
    int rd = 1; 
    if (n->left != NULL) ld = depth(n->left)+1; 
    if (n->right != NULL) rd = depth(n->right)+1; 
    return ld < rd? rd : ld; 
} 
 
void displayTree(struct node * n, size_t indent, size_t nlin,   
                 std::vector<std::string> & lines)  
{     
   int d = depth(n);  
   if (d == 1)  
   {  
        std::string val = n->val;  
       if (val.size() > 1)  
           val = nextConstant(val);  // manages constants    
       while (nlin >= lines.size())  
           lines.push_back(std::string(""));  
       std::string & curline = lines[nlin];  
       curline.resize(indent, ' ');  
           curline += n->val;  
       return;   
   }  
   if (n->left!= NULL)  
   {  
       // calculate indent to left subnode  
      size_t nextindentl = indent - (1<<(d-2)); 
       // add the /----\ to next line using the left indent  
      //cout << "/----\\" << endl; 
       // call displayTree recursively passing left node,  
      displayTree(n->left, nextindentl, nlin+2, lines); 
       // new indent, nlin + 2  
    //  cout << "/----\\" << endl; 
//       // do similar for right node
	  size_t nextindentr = indent + (1<<(d-2));
	 // add the /----\ to next line using the left indent  
      //cout << "/----\\" << endl; 
       // call displayTree recursively passing left node,  
	  displayTree(n->right, nextindentr, nlin+2, lines); 
       // new indent, nlin + 2  
      //cout << "/----\\" << endl; 
	  // first check if vector already has a line
   if (nlin == 0 || nlin >= lines.size())
       lines.resize(nlin+2);
   // then get a reference of line string at nlin.
   std::string & line = lines[nlin];  
   if (line.size() < indent)
       line.resize(indent, ' ');   // offset with blanks
    std::string val = n->val;  
    if (val.size() > 1)  
    val = nextConstant(val);  // manages constants    
    line = line.substr(0, indent) + val;
    std::string & nline = lines[nlin+1]; 
    if (nline.size() < nextindentl)
         nline.resize(nextindentl, ' ');   // add spaces up to left indent
    nline = nline.substr(0, nextindentl);
    nline += "/";
    nline.resize(nextindentr, '-');
    nline += "\\";
   }  
}  
 
void display(node * n) 
{ 
      if (n == NULL  || n->val.empty()) return; 
      size_t d = depth(n); 
      size_t i   = (1<<(d-1))-1;  // calculate indent for root 
      std::vector<std::string> all; 
      displayTree(n, i, 1, all); 
 
      vector<string>::iterator lin; 
      for (lin=all.begin(); lin != all.end(); ++lin) 
            std::cout << (*lin) << std::endl; 
      std::cout << nextConstant("");  // get all constants if any 
}

"The  1510 is wrong should be A B." It it not ok to print 15 10, instead of A B?

Open in new window

0
 
AtourayAuthor Commented:
check the entire code and tell me where i should place "cout << endl << "-----------------------------------------------------" << endl;"
ou can modify it and and resubmit again.
thanks
0
 
js-profiCommented:
place the cout after check on n at begin of display(node * n).
std::string nextConstant(const std::string& val) 
{ 
    static char constant = 'A'; 
    static std::string  constants; 
    // return all vals if empty input 
    if (val.empty()) return constants; 
    // add val to all constants 
    constants += constant; 
    constants += " = "; 
    constants += val; 
    constants += "\n"; 
    std::string ret(1, constant); 
    // increment for next constant 
    constant++; 
    return ret; 

} 
int depth(struct node* n)  
{ 
    int ld = 1; 
    int rd = 1; 
    if (n->left != NULL) ld = depth(n->left)+1; 
    if (n->right != NULL) rd = depth(n->right)+1; 
    return ld < rd? rd : ld; 
} 

void displayTree(struct node * n, size_t indent, size_t nlin,   
                 std::vector<std::string> & lines)  
{     
    int d = depth(n);  
    if (d == 1)  
    {  
        std::string val = n->val;  
        if (val.size() > 1)  
            val = nextConstant(val);  // manages constants    
        while (nlin >= lines.size())  
            lines.push_back(std::string(""));  
        std::string & curline = lines[nlin];  
        curline.resize(indent, ' ');  
        curline += val;  
        return;   
    }  
    if (n->left!= NULL)  
    {  
        if (nlin == 0 || nlin >= lines.size())
            lines.resize(nlin+2);
        // calculate indent to left subnode  
        size_t nextindentl = indent - (1<<(d-2)); 
        // add the /----\ to next line using the left indent  
        // call displayTree recursively passing left node,  
        displayTree(n->left, nextindentl, nlin+2, lines); 
        // new indent, nlin + 2  
        //       // do similar for right node
        size_t nextindentr = indent + (1<<(d-2));
        // add the /----\ to next line using the left indent  
        //cout << "/----\\" << endl; 
        // call displayTree recursively passing left node,  
        displayTree(n->right, nextindentr, nlin+2, lines); 
        // new indent, nlin + 2  
        //cout << "/----\\" << endl; 
        // first check if vector already has a line
        // then get a reference of line string at nlin.
        std::string & line = lines[nlin];  
        if (line.size() < indent)
            line.resize(indent, ' ');   // offset with blanks
        std::string val = n->val;  
        if (val.size() > 1)  
            val = nextConstant(val);  // manages constants    
        line = line.substr(0, indent) + val;
        std::string & nline = lines[nlin+1]; 
        if (nline.size() < nextindentl)
            nline.resize(nextindentl, ' ');   // add spaces up to left indent
        nline = nline.substr(0, nextindentl);
        nline += "/";
        nline.resize(nextindentr, '-');
        nline += "\\";
    }  
}  

void display(node * n) 
{ 
    if (n == NULL  || n->val.empty()) return; 
    size_t d = depth(n); 
    size_t i   = (1<<(d-1))-1;  // calculate indent for root 
    std::vector<std::string> all; 
    displayTree(n, i, 1, all); 

    vector<string>::iterator lin; 
    for (lin=all.begin(); lin != all.end(); ++lin) 
        std::cout << (*lin) << std::endl; 
    std::cout << nextConstant("");  // get all constants if any 
}

Open in new window

0
 
AtourayAuthor Commented:
i place the cout code just after the display function, but it only draw the line between
-
       /       *        4     +       15     10     7     9
and the tree. I don't want the console to show this
-
       /       *        4     +       15     10     7     9
on top of the tree. Only the tree. Any idea how i can get rid of it. It does not look nice like that to me.

-
       /       *        4     +       15     10     7     9
              
-------------------------------------------------------------------
               -
       /---------------\
       /               9
   /-------\
   *       7
 /---\
  4  +
    /-\
    1510
A =  4
B = 15
C = 10

Open in new window

0
 
js-profiCommented:
if you print 10 15 instead of A B all your indents must be calculated differently cause the bottom line needs 2 digits for each possible data. the calculation is (2^(depth-1)) * 3 for maximum on bottom line. for depth 6 that is 32*3 == 96 what would exceed normal console window width. For indents we now have 31, 15, 7, 3, 1, 0 what would turn to 47, 23, 11, 2, 0. The relative offsets for nextindents  would be 24, 12, 3, 1 and the statement is

    size_t nextindentl = indent - ((1<<(d-2) + (1<<(d-3)));

do you want to change it?

 
0
 
js-profiCommented:
to get rid of the first outputs search for printf statements in your parser and comment them.
0
 
AtourayAuthor Commented:
Yea, you are right. I have realised that with three digit numbers, say 150, will show only 15 at the bottom. so i can i print the letter instead of the number in the case of three digits numbers like 150. But i still want the digits to show if it is  1 or 2 digits( i.e if it does not exceed the  normal console window width).
Can you show me that in the code by resubmiting the entire cde i post and comment where that is added for me to know.

Also, is there anyway, we can get rid of the numbers printing above the tree?

 
0
 
AtourayAuthor Commented:
The numbers above the tree are gone now. I just need you to help me with the problem of the numbers exceeding the  normal console window width. e.g three digits numbers say 140.
0
 
js-profiCommented:
did you check for printf statements in your code?

the code changes for outputting up to 2 digits is easy to locate. search for 1<< and change those statements according to the statement i showed for nextindentl. then change  if (val.size() > 1) to if (val.size() > 2).
0
 
AtourayAuthor Commented:
if i do the changes you ask me to do, i get errors. I did the following changes
size_t nextindentl = indent - (1<<(d-2) + (1<<(d-3)));
size_t nextindentr = indent + (1<<(d-2) + (1<<(d-3)));

and got the below error:

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.
It does ot print, the console closes.

Yea, commented my printfs and they are gone.
0
 
js-profiCommented:
no other changes? try

size_t nextindentl = indent - ((1<<(d-2)) + (1<<(d-3)));
size_t nextindentr = indent + ((1<<(d-2)) + (1<<(d-3)));

print the values if you still get runtime error.

0
 
AtourayAuthor Commented:
Yea, no other changes. I just did the follow changes:
size_t nextindentl = indent - (1<<(d-2) + (1<<(d-3)));
size_t nextindentr = indent + (1<<(d-2) + (1<<(d-3)));
and changed all statements with if (val.size() > 1) to if (val.size() > 2). All the changes are done in the displayTree fun.
 
Now i just tried what you said,  but still have errors. Here is the runtime error:
 Debug Error!
Invalid allocation size:4294967291 bytes
any idea how to solve this?

0
 
js-profiCommented:
4294967291 is actually -5. the crash is because of resizing a string with that huge value. did you change the calculation in display function for initial intend of root node?
0
 
AtourayAuthor Commented:
No i did not chabge anything in the display function.
0
 
js-profiCommented:
size_t i   = (1<<(d-1)) + (1<<(d-2))-1;

that is the indent of the root. if you didn't modify it you get negative indents for lower levels but as size_t type is unsigned, it turns to 4294967291
0
 
js-profiCommented:
i told you to make changes to any calculation with 1<< .
0
 
js-profiCommented:
i leave now. don't forget to give points.
0
 
AtourayAuthor Commented:
I have changed all the have 1<<, but still the same error.
0
 
AtourayAuthor Commented:
Hey, wait. It is still not working. Can you please be patient with me. Thsi is the only problem left.
0
 
js-profiCommented:
is it still 294967291?

print out all calculated intend, nextindentl, nextindendr. post your latest code.
0
 
js-profiCommented:
eeh, i was busy since 13 hours now. and had one sandwich only. could you proceed a little bit ...
0
 
js-profiCommented:
ok, i think i found out what goes wrong. the (d-3) turns negative for d == 2.



in display do

size_t i;
if (d > 1) 
   i   = (1<<(d-1)) + (1<<(d-2))-1;
else
   i = 0;

in displayTree do

    if (n->left!= NULL)  
    {  
        if (nlin == 0 || nlin >= lines.size())
            lines.resize(nlin+2);
        // calculate indent to left subnode  
        size_t nextindentl;
        if (d > 2)
            nextindentl = indent - ((1<<(d-2)) + (1<<(d-3))); 
        else
            nextindentl = indent - 2;

        // add the /----\ to next line using the left indent  
        // call displayTree recursively passing left node,  
        displayTree(n->left, nextindentl, nlin+2, lines); 
        // new indent, nlin + 2  
        //       // do similar for right node
        size_t nextindentr;
        if (d > 2)
            nextindentr = indent + ((1<<(d-2)) + (1<<(d-3))); 
        else
            nextindentr = indent + 2;

        displayTree(n->right, nextindentr, nlin+2, lines); 
        // new indent, nlin + 2  
        //cout << "/----\\" << endl; 
        // first check if vector already has a line
        // then get a reference of line string at nlin.
        std::string & line = lines[nlin];  
        if (line.size() < indent)
            line.resize(indent, ' ');   // offset with blanks
        std::string val = n->val;  
        if (val.size() > 1)  
            val = nextConstant(val);  // manages constants    
        line = line.substr(0, indent) + val;
        std::string & nline = lines[nlin+1]; 
        if (nline.size() < nextindentl)
            nline.resize(nextindentl, ' ');// add spaces up to left indent
        nline = nline.substr(0, nextindentl);
        nline += "/";
        nline.resize(nextindentr + 1, '-');
        nline += "\\";
    }

Open in new window

0
 
js-profiCommented:
will return in about 1 hour.
0
 
AtourayAuthor Commented:
Here is my latest code. Can you just correct the error then and re-submit it here.
Thanks

// Functions to print the tree 
std::string nextConstant(const std::string& val) 
{ 
     static char constant = 'A'; 
     static std::string  constants; 
     // return all val if empty input 
     if (val.empty()) return constants; 
     // add val to all constants 
     constants += constant; 
     constants += " = "; 
     constants += val; 
     constants += "\n"; 
     std::string ret(1, constant); 
     // increment for next constant 
     constant++; 
     return ret; 
 
} 

// Calculate the depth of the tree
int depth(struct node* n)  
{ 
    int ld = 1; 
    int rd = 1; 
    if (n->left != NULL) ld = depth(n->left)+1; 
    if (n->right != NULL) rd = depth(n->right)+1; 
    return ld < rd? rd : ld; 
} 
 
//Display of tree
void displayTree(struct node * n, size_t indent, size_t nlin,   
                 std::vector<std::string> & lines)  
{     
   int d = depth(n);  
   if (d == 1)  
   {  
        std::string val = n->val;  
       if (val.size() > 2)  
           val = nextConstant(val);  // manages constants    
       while (nlin >= lines.size())  
           lines.push_back(std::string(""));  
       std::string & curline = lines[nlin];  
       curline.resize(indent, ' ');  
           curline += n->val;  
       return;   
   }  
   if (n->left!= NULL)  
   {  
       // calculate indent to left subnode  
      size_t nextindentl = indent - ((1<<(d-2)) + (1<<(d-3)));
       // call displayTree recursively passing left node,  
      displayTree(n->left, nextindentl, nlin+2, lines); 
	  size_t nextindentr = indent + ((1<<(d-2)) + (1<<(d-3)));
	  displayTree(n->right, nextindentr, nlin+2, lines); 
   if (nlin == 0 || nlin >= lines.size())
       lines.resize(nlin+2);
    //reference of line string at nlin.
   std::string & line = lines[nlin];  
   if (line.size() < indent)
       line.resize(indent, ' ');   // offset with blanks
    std::string val = n->val;  
    if (val.size() > 2)  
    val = nextConstant(val);  // manages constants    
    line = line.substr(0, indent) + val;
    std::string & nline = lines[nlin+1]; 
    if (nline.size() < nextindentl)
         nline.resize(nextindentl, ' ');   // add spaces up to left indent
    nline = nline.substr(0, nextindentl);
    nline += "/";
    nline.resize(nextindentr, '-');
    nline += "\\";
   }  
}  
 
// Output the tree
void display(node * n) 
{ 
 
      if (n == NULL  || n->val.empty()) return; 
      size_t d = depth(n); 
      size_t i   = (1<<(d-1)) + (1<<(d-2))-1;  // calculate indent for root 
      std::vector<std::string> all; 
      displayTree(n, i, 1, all); 
 
      vector<string>::iterator lin; 
      for (lin=all.begin(); lin != all.end(); ++lin) 
            std::cout << (*lin) << std::endl; 
      std::cout << nextConstant("");  // get all constants if any
	  }

Open in new window

0
 
js-profiCommented:
ok.
// Functions to print the tree 
std::string nextConstant(const std::string& val) 
{ 
     static char constant = 'A'; 
     static std::string  constants; 
     // return all val if empty input 
     if (val.empty()) return constants; 
     // add val to all constants 
     constants += constant; 
     constants += " = "; 
     constants += val; 
     constants += "\n"; 
     std::string ret(1, constant); 
     // increment for next constant 
     constant++; 
     return ret; 
 
} 

// Calculate the depth of the tree
int depth(struct node* n)  
{ 
    int ld = 1; 
    int rd = 1; 
    if (n->left != NULL) ld = depth(n->left)+1; 
    if (n->right != NULL) rd = depth(n->right)+1; 
    return ld < rd? rd : ld; 
} 
 
//Display of tree
void displayTree(struct node * n, size_t indent, size_t nlin,   
                 std::vector<std::string> & lines)  
{     
   int d = depth(n);  
   if (d == 1)  
   {  
        std::string val = n->val;  
       if (val.size() > 2)  
           val = nextConstant(val);  // manages constants    
       while (nlin >= lines.size())  
           lines.push_back(std::string(""));  
       std::string & curline = lines[nlin];  
       curline.resize(indent, ' ');  
           curline += n->val;  
       return;   
   }  
    if (n->left!= NULL)  
    {  
        if (nlin == 0 || nlin >= lines.size())
            lines.resize(nlin+2);
        // calculate indent to left subnode  
        size_t nextindentl;
        if (d > 2)
            nextindentl = indent - ((1<<(d-2)) + (1<<(d-3))); 
        else
            nextindentl = indent - 2;

        // add the /----\ to next line using the left indent  
        // call displayTree recursively passing left node,  
        displayTree(n->left, nextindentl, nlin+2, lines); 
        // new indent, nlin + 2  
        //       // do similar for right node
        size_t nextindentr;
        if (d > 2)
            nextindentr = indent + ((1<<(d-2)) + (1<<(d-3))); 
        else
            nextindentr = indent + 2;

        displayTree(n->right, nextindentr, nlin+2, lines); 
        // new indent, nlin + 2  
        //cout << "/----\\" << endl; 
        // first check if vector already has a line
        // then get a reference of line string at nlin.
        std::string & line = lines[nlin];  
        if (line.size() < indent)
            line.resize(indent, ' ');   // offset with blanks
        std::string val = n->val;  
        if (val.size() > 1)  
            val = nextConstant(val);  // manages constants    
        line = line.substr(0, indent) + val;
        std::string & nline = lines[nlin+1]; 
        if (nline.size() < nextindentl)
            nline.resize(nextindentl, ' ');// add spaces up to left indent
        nline = nline.substr(0, nextindentl);
        nline += "/";
        nline.resize(nextindentr + 1, '-');
        nline += "\\";
    }
}  
 
// Output the tree
void display(node * n) 
{ 
 
      if (n == NULL  || n->val.empty()) return; 
      size_t d = depth(n); 
      size_t i;
      if (d > 1) 
         i = (1<<(d-1)) + (1<<(d-2))-1;
      else
         i = 0;

      std::vector<std::string> all; 
      displayTree(n, i, 1, all); 
 
      vector<string>::iterator lin; 
      for (lin=all.begin(); lin != all.end(); ++lin) 
            std::cout << (*lin) << std::endl; 
      std::cout << nextConstant("");  // get all constants if any
	  }

Open in new window

0
 
js-profiCommented:
ok.
std::string nextConstant(const std::string& val) 
{ 
    static char constant = 'A'; 
    static std::string  constants; 
    // return all vals if empty input 
    if (val.empty()) return constants; 
    // add val to all constants 
    constants += constant; 
    constants += " = "; 
    constants += val; 
    constants += "\n"; 
    std::string ret(1, constant); 
    // increment for next constant 
    constant++; 
    return ret; 

} 
int depth(struct node* n)  
{ 
    int ld = 1; 
    int rd = 1; 
    if (n->left != NULL) ld = depth(n->left)+1; 
    if (n->right != NULL) rd = depth(n->right)+1; 
    return ld < rd? rd : ld; 
} 

void displayTree(struct node * n, size_t indent, size_t nlin,   
                 std::vector<std::string> & lines)  
{     
    int d = depth(n);  
    if (d == 1)  
    {  
        std::string val = n->val;  
        if (val.size() > 1)  
            val = nextConstant(val);  // manages constants    
        while (nlin >= lines.size())  
            lines.push_back(std::string(""));  
        std::string & curline = lines[nlin];  
        curline.resize(indent, ' ');  
        curline += val;  
        return;   
    }  
    if (n->left!= NULL)  
    {  
        if (nlin == 0 || nlin >= lines.size())
            lines.resize(nlin+2);
        // calculate indent to left subnode  
        size_t nextindentl;
        if (d > 2)
            nextindentl = indent - ((1<<(d-2)) + (1<<(d-3))); 
        else
            nextindentl = indent - 2;

        // add the /----\ to next line using the left indent  
        // call displayTree recursively passing left node,  
        displayTree(n->left, nextindentl, nlin+2, lines); 
        // new indent, nlin + 2  
        //       // do similar for right node
        size_t nextindentr;
        if (d > 2)
            nextindentr = indent + ((1<<(d-2)) + (1<<(d-3))); 
        else
            nextindentr = indent + 2;

        displayTree(n->right, nextindentr, nlin+2, lines); 
        // new indent, nlin + 2  
        //cout << "/----\\" << endl; 
        // first check if vector already has a line
        // then get a reference of line string at nlin.
        std::string & line = lines[nlin];  
        if (line.size() < indent)
            line.resize(indent, ' ');   // offset with blanks
        std::string val = n->val;  
        if (val.size() > 1)  
            val = nextConstant(val);  // manages constants    
        line = line.substr(0, indent) + val;
        std::string & nline = lines[nlin+1]; 
        if (nline.size() < nextindentl)
            nline.resize(nextindentl, ' ');// add spaces up to left indent
        nline = nline.substr(0, nextindentl);
        nline += "/";
        nline.resize(nextindentr + 1, '-');
        nline += "\\";
    }
}  

void display(node * n) 
{ 
    if (n == NULL  || n->val.empty()) return; 
    size_t d = depth(n); 
    size_t i;
    if (d > 1)
        i = (1<<(d-1))-1;  // calculate indent for root 
    else
        i = 0;
    std::vector<std::string> all; 
    displayTree(n, i, 1, all); 

    vector<string>::iterator lin; 
    for (lin=all.begin(); lin != all.end(); ++lin) 
        std::cout << (*lin) << std::endl; 
    std::cout << nextConstant("");  // get all constants if any 
}

Open in new window

0
 
AtourayAuthor Commented:
it still gives me the same error.
0
 
AtourayAuthor Commented:
Did you correct the above codes. Which of them is working. I tried both, but they all give the same errors.
Did you actually run the code on your visual studio c++, to check your corrections? Because non of your corrections are working.
0
 
AtourayAuthor Commented:
It is not even working with the ones that were working.
I hope we are not messing up what we have achieved so far.
\
0
 
js-profiCommented:
i can't run the code as i don't have parser and main. what are the values for indent, nextindentl, nextindentr
0
 
AtourayAuthor Commented:
how can i know the values of indent, nextindentl, nextindentr. I am not very familier with VS.
because the program is not runing and cannot compile due to runtime error. I cannot determine. So tell me how to get the value.
0
 
js-profiCommented:
set a breakpoint at each line.resize(..) and nline.resize(...). then at break examine the argument passed to resize. if it is 4 billion you got the pulprit. if not do f5 to continue. if it crashes you could choose 'retry' to step into the statement that crashes. examine all variables around by hoovering the mouse above the variable.
0
 
js-profiCommented:
alternatively, post the rest of the sources here. i'll will debug for you.
0
 
AtourayAuthor Commented:
It actually do compile but when i input and run, it give a runtime error as follows:
Debug Error!

The application has requested the Runtime to terminate it in an unsual way. Please contact the application's support team for for information.

0
 
js-profiCommented:
run the program with F5 from IDE. set breakpoints by clicking left of the statement into gray margin,
0
 
AtourayAuthor Commented:
i also show the following in debug:
in the xstring windowm shows:

      size_type _Num;
            if (0 < _Count && _Grow(_Num = _Mysize + _Count))
                  {      // make room and append new stuff using assign
                  _Chassign(_Mysize, _Count, _Ch);
                  _Eos(_Num);
                  }
            return (*this);
            }


in the memset.asm it shows this below:

        rep     stosd
main_loop_tail:
        test    edx,edx         ; if there is no tail bytes,
        jz      finish          ; we finish, and it's time to leave
; Set remaining bytes

i hope this infomation can help you to debug for me
0
 
js-profiCommented:
no. open the call stack window and navigate up to displayTree. call stack is one of helper windows available thru debug menu - windows ...
0
 
AtourayAuthor Commented:
Do you have faacebook, i add you in my friends list? I hope i have given you good information to debug
0
 
AtourayAuthor Commented:
the value of nextindentl      is   4294967295      unsigned int
0
 
js-profiCommented:
no facebook. love my privacy.  :)
0
 
AtourayAuthor Commented:
That is ok. so do you see the value of nextindentl ?
0
 
js-profiCommented:
i debugged and found that in display there is still the wrong indent of 15 calculated.

use
void display(node * n) 
{ 
    if (n == NULL  || n->val.empty()) return; 
    size_t d = depth(n); 
    size_t i;
    if (d > 1)
        i = (1<<(d-1)) + (1<<(d-2))-1;  // calculate indent for root 
    else
        i = 0;
    std::vector<std::string> all; 
    displayTree(n, i, 1, all); 

    vector<string>::iterator lin; 
    for (lin=all.begin(); lin != all.end(); ++lin) 
        std::cout << (*lin) << std::endl; 
    std::cout << nextConstant("");  // get all constants if any 
}

Open in new window

0
 
js-profiCommented:
that's my output after changing  (val.size() > 1) to  (val.size() > 2)
-
           /------------------------\
           /                       9
     /------------\
     *           7
  /------\
  4     +
      /----\
      10  15

Open in new window

0
 
AtourayAuthor Commented:
Yea, it is correct now. Thanks, but just one more thing i want you to help me on how to make colours at different level in the tree. I want to put colours at different level of the Tree. How can i do that. I just want to differentiate the levels by colours.
Thanks
0
 
js-profiCommented:
unfortunately i never made console programming. not so easy.
0
 
AtourayAuthor Commented:
ok. i give you this point. But do you know anyone who can help on that. Wanna see how that is done.
thanks
0
 
AtourayAuthor Commented:
Can anyone help me out on how to print colours for the different levels of a binary tree please.
thanks
0
 
AtourayAuthor Commented:
I got this code which sets all the text to one colour. I want to use it to set different colours at different levels of the tree.
Can anyone help me out on how to do that.
Thanks

#include <iostream>
#include <windows.h>

using namespace std;
HANDLE hCon;

enum Color { DARKBLUE = 1, DARKGREEN, DARKTEAL, DARKRED, DARKPINK, DARKYELLOW, GRAY, DARKGRAY, BLUE, GREEN, TEAL, RED, PINK, YELLOW, WHITE };

void SetColor(Color c){
        if(hCon == NULL)
                hCon = GetStdHandle(STD_OUTPUT_HANDLE);
        SetConsoleTextAttribute(hCon, c);
}

Open in new window

0
 
js-profiCommented:
better use a new question as only participating experts would take attention.
0
 
AtourayAuthor Commented:
ok, i created a new question for it and awarded you your point. Thanks for the help
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 59
  • 55
  • 5
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now