Looking for a few examples..

Hello,

I'm looking for easy-to-understand C++ codes with clear logic for :
- Double Linked List
- Queue
- a program that validates expressions. for example :
valid : ([(a+b)+c]) + x
invalid : ([(a+b+c]) + x


I already searched for it, but i wasn't lucky. No i'm not asking for someone to do it for me as i already can do it on my own, but i'm looking for simple and clear ones that are already available preferably with an explanation (like prelude's linked list).


any help is much appreciated :)

Here's an old Doubly-Linked List class I wrote for a class nigh on 3 years back. I haven't really provided it the much needed "old once over" for which it desperately aches, for I leave that chore to act as your method of coherency allocation.

Code:

---

#ifndef _DOUBLYLINKEDLIST_H_
#define _DOUBLYLINKEDLIST_H_

#include <string>
using namespace std;

class ListException {
  string _msg;

public:
  ListException(const char *msg=NULL) {
    _msg = (*msg == NULL) ? "Unknown list error" : msg;
  }

  const string& getMessage() const { return _msg; }
};

template <typename T>
class DoublyLinkedList {
  template <typename T>
  struct DoubleNode {
    T    data;
    DoubleNode  *next;
    DoubleNode  *prev;
    DoubleNode() : next(NULL), prev(NULL), data() { }
  };

  typedef DoubleNode<T> Node;

  Node          *_head;
  Node          *_tail;
  Node          *_cur;
  int          _length;
 
  void*        locateItem(const T &item, int *counter); 
 
public:
  DoublyLinkedList();
  virtual ~DoublyLinkedList();
 
  bool          isFull() const;
  bool          isEmpty() const;
 
  void          clear();

  void          insertItem(const T &item);
  bool          findItem(const T &item);
  void          deleteItem(const T &item);
 
  void          resetList();
  T            getNextItem(); 
};

//////////////////////////////////////////////////////////
// Implementation

template <typename T>
DoublyLinkedList<T>::DoublyLinkedList()
: _head(NULL), _tail(NULL), _cur(NULL), _length(0)
{
}

template <typename T>
DoublyLinkedList<T>::~DoublyLinkedList() {
  clear();
}

///////////////////////////////////////////////////////////////
// name:    locateItem
// params:  item - the item to locate
//
// desc:    searches list for item
// returns: pointer to node where item was located or NULL
//
template <typename T>
void* DoublyLinkedList<T>::locateItem(const T &item) {
  //work our way in from both sides
  Node *left = _head;
  Node *right = _tail;

  int leftIndex = 0;
  int rightIndex = _length - 1;

  while (leftIndex <= rightIndex) {
    if (left->data == item)
      return left;
    if (right->data == item)
      return right;

    ++leftIndex;
    --rightIndex;
    left = left->next;
    right = right->prev;   
  }

  return NULL;
}

/////////////////////////////////////////////
// name:    isFull
// params:  none
//
// desc:    checks if memory is available for
//          dynamic allocation of an item
// returns: true if full. false otherwise.
//
template <typename T>
bool DoublyLinkedList<T>::isFull() const {
  try {//check if room exists for another node
    Node *node = new Node;
    delete node;
    return false;
  }
  catch (bad_alloc exc) {
    return true;
  }
}

///////////////////////////////////////////
// name:    isEmpty
// params:  none
//
// desc:    checks if list is empty
// returns: true if empty. false otherwise.
//
template <typename T>
bool DoublyLinkedList<T>::isEmpty() const {
  return _head == NULL;
}

//////////////////////////////////////////
// name:    clear
// params:  none
//
// desc:    clears all items from the list
// returns: nothing
//
template <typename T>
void DoublyLinkedList<T>::clear() {
  //work our way in from both sides (faster)
  Node *left = _head;
  Node *right = _tail;

  int leftIndex = 0;
  int rightIndex = _length - 1;

  //only while left is < right
  while (leftIndex < rightIndex) {
    _length -= 2;

    Node *next = left->next;
    Node *prev = right->prev;

    delete left;
    delete right;

    ++leftIndex;
    --rightIndex;
    left = next;
    right = prev;   
  }

  //if left and right point at the same node (center)
  //make sure we only delete it once
  if (leftIndex == rightIndex) {
    --_length;
    delete left;
  }

  _head = _tail = _cur = NULL;   
}

//////////////////////////////////////////////////
// name:    insertItem
// params:  item - the item to insert
//
// desc:    inserts an item at the end of the list
// returns: nothing
//
template <typename T>
void DoublyLinkedList<T>::insertItem(const T &item) {
  if (isFull())
    throw ListException("Insert into full list");

  Node *newNode = new Node;
  newNode->data = item;

  if (_tail != NULL) {//if tail is pointing to a valid node
    _tail->next = newNode;//set it's next ptr to the new node
    newNode->prev = _tail;//set it's prev ptr to the previous tail
  }

  _tail = newNode;//now the new node IS the tail

  if (_head == NULL) {//if the list is empty
    _head = _tail;//point the head at the tail
    _cur = _head;
  }

  ++_length;
  ++_insCounter;//update stat counter
}

///////////////////////////////////////////
// name:    findItem
// params:  item - the item to find
//
// desc:    searches list for item
// returns: true if found. false otherwise.
//
template <typename T>
bool DoublyLinkedList<T>::findItem(const T &item) {
  return locateItem(item, &_srcCounter) != NULL;
}

//////////////////////////////////////
// name:    deleteItem
// params:  item - item to delete
//
// desc:    deletes item from the list
// returns: nothing
//
template <typename T>
void DoublyLinkedList<T>::deleteItem(const T &item) {
  if (isEmpty())
    return;

  //work our way in from both sides 
  Node *left = _head;
  Node *right = _tail;

  int leftIndex = 0;
  int rightIndex = _length - 1;

  while (leftIndex <= rightIndex) {
    ++_delCounter;//update stat counter

    //update our pointer indices
    ++leftIndex;
    --rightIndex;
   
    if (left->data == item) {
      --_length;
     
      if (left == _head) {//if at head, repoint it to our next node
        _head = left->next;
        _head->prev = NULL;
      }

      if (left == _cur)//don't let _cur point at invalid memory
        _cur = _cur->next;

      if (left->prev != NULL)//point prev node's next to our node's next
        left->prev->next = left->next;
     
      if (left->next != NULL)//point next node's prev to our node's prev
        left->next->prev = left->prev;

      Node *next = left->next;//get next node before deleting
      delete left;//now dealloc
      left = next;//continue
    }
    else
      left = left->next;

    if (right->data == item) {
      --_length;

      if (right == _tail) {//if at tail, repoint at our prev node
        _tail = right->prev;
        _tail->next = NULL;
      }

      if (right == _cur)//don't let _cur point at invalid memory
        _cur = _cur->prev;

      if (right->next != NULL)//point next node's prev to our node's prev
        right->next->prev = right->prev;

      if (right->prev != NULL)//point prev node's next to our node's next
        right->prev->next = right->next;

      Node *prev = right->prev;//get prev node before deleting
      delete right;//now dealloc
      right = prev;//continue
    }
    else
      right = right->prev;
  }
}

/////////////////////////////////////////////
// name:    resetList
// params:  none
//
// desc:    resets internal pointer to head
// returns: nothing
//
template <typename T>
void DoublyLinkedList<T>::resetList() {
  _cur = _head;
}

/////////////////////////////////////////////
// name:    getNextItem
// params:  none
//
// desc:    gets item internal pointer refers
//          to then increments to the next
// returns: item internal pointer refers to
//
template <typename T>
T DoublyLinkedList<T>::getNextItem() {
  if (_cur == NULL)//either empty list or resetList wasn't called
    throw ListException("Retrieve next without reset");

  T item = _cur->data;//get the data
  _cur = _cur->next;//move to the next node
  return item;
}
 
#endif //_DOUBLYLINKEDLIST_H_

---

(If any of the implementation seems odd or generally unusual, recall that it was written as defined by the instructor's direction.)

Thanks Lucky, but i'm afraid that this is a bit complicated than what i was looking for :). I need those programs in their simplest form so i can read and understand them on the fly.

I have a data structure exam coming very soon, and i'm already modifying and redoing more than a dozen programs that my teacher wrote. His logic, variable naming and style is incredibley hard to the point that he'd let a "hello world" program look extremley complicated.

So i'm simplifying his program, but so far i couldn't do well with the three programs i've mentioned. :)

Question, do you understand templates?

This is a good one for queues...
http://www.cprogramming.com/tutorial...ory/queue.html

Code:

---

//valid : ([(a+b)+c]) + x
//invalid : ([(a+b+c]) + x

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

using namespace std;

//function declarations
bool Is_Bracket_Open(char);
bool Is_Bracket_Closed(char);
bool Check_Match(char,char);
bool Is_Valid(string);

int main()
{
    string A ="([(a+b)+c])+x";
    string B ="([(a+b+c)+x";
   
    if(Is_Valid(A)==true)
    {
        cout<<"Valid";
    }
    else
    cout<<"***ERR";
   
   
    cin.get();
    cin.get();
}
/*=============================================
  Given: my_string  a string
  Task:  To determine if the brackets are valid
  return: Nada
  ============================================*/
bool Is_Valid(string my_string)
{
    stack<char> my_stack;//create a stack of chars
    for(int i=0; i<my_string.length(); i++)//iterate through string
    {
     
        char Symbol;
        Symbol = my_string[i];
       
        if(Is_Bracket_Open(Symbol)==true)
        {
            //push open bracket onto stack
            my_stack.push(Symbol);
        }
        if(Is_Bracket_Closed(Symbol)==true)
        {
            char top;
            if (!my_stack.empty())
            {
              top = my_stack.top();
               
              if(Check_Match(top,Symbol)==true)
              {
                //discard opening bracket
             
                  my_stack.pop();
               
              }
              else
              {
               
         
                return false;
                break;
              }
            } 
            else
            {
                return false;
                break;
            }     
        }
       
    }
    if(!my_stack.empty())
    {
      return false;
    }
    else
    {
      return true;
    }     
   
}     
 

bool Is_Bracket_Open(char ch)
{
    if ((ch == '(')||
        (ch == '[')||
        (ch == '{'))
        return true;
    else
        return false;
}

bool Is_Bracket_Closed(char ch)
{
    if ((ch == ')')||
        (ch == ']')||
        (ch == '}'))
        return true;
    else
        return false;
}

bool Check_Match(char A,char B)
{
    if ((A=='(')&&(B==')') )
    {
        return true;
    }
    else if ((A=='{')&&(B=='}') )
    {
        return true;
    }
      else if ((A=='[')&&(B==']') )
    {
        return true;
    }
}

---

That's an example using the stack... it may or maynot be helpful

Thanks alot guys, i really appreciate it.

I still need the most important program though, the doubly linked list. I couldn't find an example anywhere.

any ideas?