Delete the last two characters in stringstream

[ManlyMartin]

Hey guys, is there any way I could delete the last two characters in a stringstream? I'm working on a tree assignment and was wondering if there was an easy way to delete the last two characters in a stream so it didn't end with ", ".

  string ToStringForwards(BSTNodeT<T>* node) const {
    if (node != NULL) {
      std::ostringstream ss;
      ss << ToStringForwards(node->GetLeft());
      ss << node->GetContents() << ss << ", ";
      ss << ToStringForwards(node->GetRight());
      return ss.str();
    }
    return ""; 
  }

[JLBorges]

// return ss.str();

const std::string str = ss.str() ;
const std::size_t sz = str.size() ;
    
if( sz>1 && str.substr(sz-2) == ", " ) // if the string ends with ", " 
    return str.substr( 0, sz-2 ) ;
else return str ;

[ManlyMartin]

OK so I wrote it like this....

  string ToStringForwards(BSTNodeT<T>* node) const {
    if (node != NULL) {
      std::ostringstream ss;
      ss << ToStringForwards(node->GetLeft());
      ss << node->GetContents() << ss << ", ";
      ss << ToStringForwards(node->GetRight());
      const std::string str = ss.str();
      const std::size_t size = str.size();
      if( size > 1 && str.substr(size - 2) == ", " ) {
        return str.substr(0 , size - 2 );
      } else {
        return str;
      }
    }
    return ""; 
  }

...And it returned this. O.O

500x229b18

[Bdanielz]

I would try and rewrite you function to have only ONE return statement. If you cannot then you might need two functions. Also I would step through that function via your debugger and to verify your logic is landing in the correct scopes.

[ManlyMartin]

I wrote this function to assist.

  BSTNodeT<T>* GetEnd(BSTNodeT<T>* node) const {
    if (node != NULL) {
      if (node->GetRight() != NULL) {
        return GetEnd(node);
      } else if (node->GetLeft() != NULL) {
        return GetEnd(node->GetLeft());
      }
    }
    return node;
  }

The idea is to find the end node in the tree and, if the node isn't the end node in ToStringForwards, add a coma afterwards.

  string ToStringForwards(BSTNodeT<T>* node) const {
    BSTNodeT<T>* end;
    end = GetEnd(node);
    if (node != NULL) {
      std::ostringstream ss;
      ss << ToStringForwards(node->GetLeft());
      ss << node->GetContents();
      if (node != end) {
        ss << ", ";
      }
      ss << ToStringForwards(node->GetRight());
      return ss.str();
    }
    return ""; 
  }

However, I seem to be getting the opposite effect. 20 and 50 show up as "2050, "

[andywestken]

...And it returned this. O.O

500x229b18

That looks like 50 followed by a memory address.

What's happening on line 5? Should you be writing the ostringstream (ss) back into itself?

But wouldn't it be better to just not add the ", " if not needed?

Also, as ToStringForwards() doesn't use any internal state, it looks like it could (and probably should) be a standalone helper function rather than a class member.

Andy

[andywestken]

Your latest version (with the GetEnd assistant function) is getting a bit over-complicated!

And is line 4 of GetEnd() correct?

Andy

[Bdanielz]

I cannot test this because we don't have your code (maybe it helps) your same function with one return type.

string ToStringForwards(BSTNodeT<T>* node) const {
    BSTNodeT<T>* end;
    end = GetEnd(node);
    if (node != NULL) {
        std::ostringstream ss;
        ss << ToStringForwards(node->GetLeft());
        ss << node->GetContents();
        if (node != end) {
            ss << ", ";
        }
        ss << ToStringForwards(node->GetRight());
    }else{
        ss = ""; 
    }
    return ss.str();

}

[andywestken]

@Bdanielz

ss is not in scope at line 13 or 15 so your code is broken.

While one point of return is a good aim, there are cases when this criterium can be relaxed. I don't really see the problem in this case.

But here's one way to do it:

  string ToStringForwards(BSTNodeT<T>* node) const {
    string str;
    if (node != NULL) {
      std::ostringstream ss;
      ss << ToStringForwards(node->GetLeft());
      ss << node->GetContents();
      BSTNodeT<T>* end = GetEnd(node); // moved into as tight a scope as possible
      if (node != end) {
        ss << ", ";
      }
      ss << ToStringForwards(node->GetRight());
      str = ss.str();
    }
    return str;
  }

Andy

PS ostringstream does not have a std::string or (const char*) overload of operator=(). To set the contained string use ostringstream::str()

ss.str(""); // not ss = "";

or

ss.str(string());

[andywestken]

Test Harness

- The class methods have been tweaked to become functions.
- The test node is written to be used on the stack or global.

#include <iostream>
#include <sstream>
using namespace std;

template<typename T>
class BSTNodeT {
public:
  BSTNodeT* nodeLeft;
  BSTNodeT* nodeRight;
  T         contents;
public:
  BSTNodeT(T c = T())
  : nodeLeft(NULL), nodeRight(NULL), contents(c) {}
  BSTNodeT(BSTNodeT* nL, BSTNodeT* nR, T c)
  : nodeLeft(nL), nodeRight(nR), contents(c) {}
  BSTNodeT* GetLeft() const {
    return nodeLeft;
  }
  BSTNodeT* GetRight() const {
    return nodeRight;
  }
  T GetContents() {
    return contents;
  }
};

template<typename T>
BSTNodeT<T>* GetEnd(BSTNodeT<T>* node) {
  if (node != NULL) {
    if (node->GetRight() != NULL) {
      return GetEnd(node->GetRight()); // added ->GetRight()
    } else if (node->GetLeft() != NULL) {
      return GetEnd(node->GetLeft());
    }
  }
  return node;
}

template<typename T>
string ToStringForwards(BSTNodeT<T>* node) {
  BSTNodeT<T>* end;
  end = GetEnd(node);
  if (node != NULL) {
    std::ostringstream ss;
    ss << ToStringForwards(node->GetLeft());
    ss << node->GetContents();
    if (node != end) {
      ss << ", ";
    }
    ss << ToStringForwards(node->GetRight());
    return ss.str();
  }
  return ""; 
}

const char testTree[] =
  "  [0]   [1]    \n"
  "        / \\    \n"
  "      [2] [3]  \n"
  "      /     \\  \n"
  "    [4]     [5]\n";

namespace TestData {
  BSTNodeT<int> node5(5);
  BSTNodeT<int> node4(4);
  BSTNodeT<int> node3(NULL, &node5, 3);
  BSTNodeT<int> node2(&node4, NULL, 2);
  BSTNodeT<int> node1(&node2, &node3, 1);
  BSTNodeT<int> node0;
}

void test() {
  using namespace TestData;

  cout << "node0 -> " << ToStringForwards(&node0) << "\n"
       << "node1 -> " << ToStringForwards(&node1) << "\n"
       << "node2 -> " << ToStringForwards(&node2) << "\n"
       << "node3 -> " << ToStringForwards(&node3) << "\n"
       << "node4 -> " << ToStringForwards(&node4) << "\n"
       << "node5 -> " << ToStringForwards(&node5) << "\n"
       << "\n";
}

int main() {
  cout << testTree << "\n";
  test();
  return 0;
}

Results

The strings for nodes 1 and 2 don't look quite right?

  [0]   [1]
        / \
      [2] [3]
      /     \
    [4]     [5]

node0 -> 0
node1 -> 42, 1, 3, 5
node2 -> 42,
node3 -> 3, 5
node4 -> 4
node5 -> 5

[ManlyMartin]

Andy was right, line was off! Unfortunately the problem persists...it still shows up at "2050, " instead of "20, 50".

To help clarify, this is the full code (+the nodeT code)

#ifndef BS_TREET_H
#define BS_TREET_H
#include <iostream>
#include <cmath>
#include <string>
#include <cctype>
#include <sstream>
#include "bst_nodet.h"
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::stringstream;

template <typename T>
class BSTreeT {
 public:
  BSTreeT() {
    root_ = NULL;
    size_ = 0;
  }

  ~BSTreeT() {
    Clear();
  }

  int GetSize() const {
    return size_;
  }

  void Clear() {
    Clear(root_);
    size_ = 0;
  }

  int Insert(T i) {
    return Insert(i, root_);
  }

  bool Exists(T i) {
    return Exists(i, root_);
  }

  int Remove(T i) {
    return Remove(i, root_);
  }

  BSTNodeT<T>* Get(T i) {
    return Get(i, root_);
  }

  std::string ToStringForwards() const {
    return ToStringForwards(root_);
  }

  std::string ToStringBackwards() const {
    return ToStringBackwards(root_);
  }

 private:
  BSTNodeT<T>* root_;
  int size_;
  
  void Clear(BSTNodeT<T>*& node) {
    BSTNodeT<T>* left;
    BSTNodeT<T>* right;
    if (node != NULL) {
    left = node->GetLeft();
    right = node->GetRight();
    Clear(left);
    Clear(right);
    delete node;
    node = NULL;
    }
  }
  
  int Insert(T i, BSTNodeT<T>*& node) {
    int count = 0;
    if (node == NULL) {
      node = new BSTNodeT<T>(i);
      size_++;
      count++;
    } else if (node->GetContents() > i) {
      root_ = node;
      return Insert(i, node->GetLeft());
    } else if (node->GetContents() < i) {
      root_ = node;
      return Insert(i, node->GetRight());
    } else {
      node->IncrementCount();
      count++;
      return Insert(i, node);
    }
    return count;
  }

  bool Exists(T i, BSTNodeT<T>* node) {
    if (node != NULL) {
      Exists(i, node->GetLeft());
      if (node->GetContents() == i) {
        return true;
      }
      Exists(i, node->GetRight());
    }
    return false; 
  }

  int Remove(T i, BSTNodeT<T>* node) {
    T min;
    if (node != NULL) {
      if (node->GetContents() == i) {
        if ((node->GetLeft() == NULL) && node->GetRight() == NULL) {
          if (i == 1) {
            delete node;
            node = NULL;
            size_--; 
            return 0;
          } else {
            node->DecrementCount();
            return node->GetContents();
          }
        } else if ((node->GetLeft() != NULL) && (node->GetRight()) == NULL) {
          if (i == 1) {
            delete node;
            node = NULL;
            size_--; 
            return 0;
          } else {
            node->DecrementCount();
            return node->GetContents();
          }
        } else if ((node->GetLeft() == NULL) && (node->GetRight()) != NULL) {
          if (i == 1) {
            delete node;
            node = NULL;
            size_--; 
            return 0;
          } else {
            node->DecrementCount();
            return node->GetContents();
          }
        } else {
          if (i == 1) {
            delete node;
            node = NULL;
            size_--; 
            return 0;
          } else {
            node->DecrementCount();
            return node->GetContents();
          }
        }
      } else if (node->GetContents() > i) {
      return Remove(i, node->GetLeft());
      } else if (node->GetContents() < i) {
      return Remove(i, node->GetRight());
      }
    }
    return -1;
  }

  BSTNodeT<T>* Get(T i, BSTNodeT<T>* node) {
    if (node != NULL) {
      Get(i, node->GetLeft());
      if (node->GetContents() == i) {
        return node;
      }
      Get(i, node->GetRight());
    }
    return NULL; 
  }

  string ToStringForwards(BSTNodeT<T>* node) const {
    string str;
    if (node != NULL) {
      std::ostringstream ss;
      ss << ToStringForwards(node->GetLeft());
      ss << node->GetContents();
      BSTNodeT<T>* end = GetEnd(node);
      if (node != end) {
        ss << ", ";
      }
      ss << ToStringForwards(node->GetRight());
      str = ss.str();
    }
    return str;
  }

  string ToStringBackwards(BSTNodeT<T>* node) const {
    if (node != NULL) {
      std::ostringstream ss;
      ss << ToStringBackwards(node->GetRight());
      ss << node->GetContents();
      if ((node->GetLeft() != NULL) || (node->GetRight() != NULL)) {
        ss << ", ";
      }
      ss << ToStringBackwards(node->GetLeft());
      return ss.str();
    }
    return ""; 
  }

  T FindMin(BSTNodeT<T>* node) const {
    if (node != NULL) {
      if (node->GetLeft() == NULL) {
        return node->GetContents();
      } else {
        return FindMin(node->GetLeft());
      }
    }
    return T();
  }
  
  BSTNodeT<T>* GetEnd(BSTNodeT<T>* node) const {
    if (node != NULL) {
      if (node->GetRight() != NULL) {
        return GetEnd(node->GetRight());
      } else if (node->GetLeft() != NULL) {
        return GetEnd(node->GetLeft());
      }
    }
    return node;
  }
};

#endif /* BS_TREET_H */ 

ToStringBackwards isn't finished, so you can ignore that for now.

#ifndef BST_NODET_H
#define BST_NODET_H
#include <iostream>
#include <cmath>
#include <string>
#include <cctype>
#include <sstream>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::stringstream;

template <typename T>
class BSTNodeT {
 public:
  BSTNodeT() {
    left_ = NULL;
    right_ = NULL;
    contents_ = T();
    count_ = 0;
  }

  BSTNodeT(T contents) {
    left_ = NULL;
    right_ = NULL;
    contents_ = contents;
    count_ = 0;
  }

  ~BSTNodeT() {
    left_ = NULL;
    right_ = NULL;
  }

  void SetContents(T contents) {
    contents_ = contents;
  }

  void SetLeft(BSTNodeT<T>* node) {
    left_ = node;
  }

  void SetRight(BSTNodeT<T>* node) {
    right_ = node;
  }

  void IncrementCount() {
    count_++;
  }

  void DecrementCount() {
    count_--;
  }

  T GetContents() const {
    return contents_;
  }
  
  T& GetContents() {
    return contents_;
  }

  BSTNodeT<T>* GetLeft() const {
    return left_;
  }
  
  BSTNodeT<T>*& GetLeft() {
    return left_;
  }

  BSTNodeT<T>* GetRight() const {
    return right_;
  }
  
  BSTNodeT<T>*& GetRight() {
    return right_;
  }

  int GetCount() {
    return count_;
  }
private:
  T contents_;
  BSTNodeT<T>* left_;
  BSTNodeT<T>* right_;
  int count_;
};

#endif /* BST_NODET_H */ 

[andywestken]

I have a solution if you want it...

But as this a forum about learning how to code I didn't post it; just the test harness I used to fix the code.

(I can say that your code doesn't look that different to mine. A slight rework is all you need to give you the right result!!)

Andy :-)

[JLBorges]

    string ToStringForwards( BSTNodeT<T>* node ) const
    {
        string str;
        if( node != NULL )
        {
            std::ostringstream ss;

            //////////////////////////////////////////////////////
            string left_str = ToStringForwards( node->GetLeft() );
            if( !left_str.empty() ) ss << left_str << ", " ;
            //////////////////////////////////////////////////////

            ss << node->GetContents() ;
            
            BSTNodeT<T>* end = GetEnd( node );
            if( node != end )
            {
                ss << ", ";
            }
            
            ss << ToStringForwards( node->GetRight() );
            str = ss.str();
        }
        return str;
    }

Note: Though I have left it as it is, this

            BSTNodeT<T>* end = GetEnd( node );
            if( node != end )
            {
                ss << ", ";
            }

is inane. How many times do you want to traverse the tree?
(With this GetEnd() idea, the in-order traversal has quadratic complexity.)
http://coliru.stacked-crooked.com/a/a7960f471f4fb2a3

[ManlyMartin]

I think I've gotten a step closer to solving the problem but...not quite.

  BSTNodeT<T>* GetEnd(BSTNodeT<T>* node) const {
    if (node != NULL) {
      if (node->GetRight() != NULL) {
        return GetEnd(node->GetRight());
        if (node != root_) {
          return GetEnd(node->GetLeft());
        }
      }
    }
    return node;
  }

  string ToStringForwards(BSTNodeT<T>* node) const {
    BSTNodeT<T>* end;
    end = GetEnd(node);
    if (node != NULL) {
      std::ostringstream ss;
      ss << ToStringForwards(node->GetLeft());
      ss << node->GetContents();
      if (node != end) {
        ss << ", ";
      }
      ss << ToStringForwards(node->GetRight());
      return ss.str();
    }
    return ""; 
  }

There's still a problem but this one I really don't get. It's returning "2050" instead of "20, 50". I don't see how it failed to add the coma twice. There's only one end value and both 20 and 50 can't be it.

[JLBorges]

See the code between comments:

            //////////////////////////////////////////////////////
            string left_str = ToStringForwards( node->GetLeft() );
            if( !left_str.empty() ) ss << left_str << ", " ;
            ////////////////////////////////////////////////////// 

After ToStringForwards() on the left sub-tree, we need to add a comma separator if the string is not empty.

The GetEnd() function is not the culprit for this issue (missing comma separator: it still shows up at "2050, " instead of "20, 50".). You can leave the GetEnd() as it is, if there is no requirement of linear complexity.

[ManlyMartin]

Oh! Sorry about that, I missed your post! It worked, but for the sake of knowledge, can you tell me how it fixed the problem? You say it's for empty strings, but my empty stringstreams seemed to function fine. The issue always seemed to be with the second element in the string.

[JLBorges]

The left sub-tree of tree is also a tree, GetEnd() of the sub-tree returns the last node in an in-order traversal of the sub-tree. So there won't be a comma separator at the end of ToStringForwards( node->GetLeft() );

Our code was:

1. the string for the left sub-tree; there is no comma separator at the end after the value in the last node because GetEnd() for the left sub-tree would be that last node.

2. the string for the current node; comma separator (if current node is not end)

3. the string for the right sub-tree

We need to add a comma separator between steps 1 and 2 (if step 1 returned a non-empty string).

[andywestken]

I'm working on a tree assignment ...

A rather belated question, but what are ToStringForwards() and ToStringBackwards() intended to do?

Is the order of nodes correct, and it's just the missing commas that is the problem?

Andy

From above

  [0]   [1]
        / \
      [2] [3]
      /     \
    [4]     [5]

node0 -> 0
node1 -> 42, 1, 3, 5
node2 -> 42,
node3 -> 3, 5
node4 -> 4
node5 -> 5

And adding two more nodes

  [0]     [1]
         /   \
      [2]     [3]
      / \     / \
    [4] [5] [6] [7]

node0 -> 0
node1 -> 42, 51, 63, 7
node2 -> 42, 5
node3 -> 63, 7
node4 -> 4
node5 -> 5
node6 -> 6
node7 -> 7