circular link list in c++

[saraSS]

I'm trying to built and array of circular link list but when I read the input file Ijust get a long link list instead of different list and after trying to use Linked_list_Stack *obj[arraysize]; I'm getting this errors
newcir.cpp:107: request for member `push' in `obj[i]', which is of
non-aggregate type `Linked_list_Stack*'
newcir.cpp:110: request for member `print_list' in `obj[i]', which is of
non-aggregate type `Linked_list_Stack*'

[arne]

I'm trying to built and array of circular link list but when I read the input file Ijust get a long link list instead of different list and after trying to use Linked_list_Stack *obj[arraysize]; I'm getting this errors
newcir.cpp:107: request for member `push' in `obj[i]', which is of
non-aggregate type `Linked_list_Stack*'
newcir.cpp:110: request for member `print_list' in `obj[i]', which is of
non-aggregate type `Linked_list_Stack*'

May it be that you try to access the push member with code like

  obj[i].push();
 

?

If so: the array contains only pointers to objects, not the objects themselves. So, you have to use

  (*obj[i]).push();
 

or

  obj[i]->push();
 

[saraSS]

fix that problem thatnks but still getting only one list I need different list my main is
int main( )
{
int i;
cin>>arraysize;
Linked_list_Stack *obj[arraysize];

for(i=0;i<arraysize;i++)
{
obj[i] = new Linked_list_Stack;
while(!cin.eof())
{
cin>>num;
if(num!=-1)
{
obj[i]->push( );
}
}
obj[i]->print_list( );
cout<<endl;
}
return 0;

[arne]

Could you please explain a little bit more in detail what you're trying to do?
As far as I understand from your code, you're

- building an array of pointers to elements of type Linked_list_Stack

- allocating objects for each of the pointers in the array

- invoking the member function push() of these objects (what is pushed here btw?)

- and finally you invoke the member function print_list (what will/should be printed here?)

Could you explain what should happen if you're program worked correctly?

[saraSS]

I im trying to implement a stack-based postfix calculator for sets of nonnegative
integers. The input consists of the following items:
a. n, the number of input sets, on a line by itself.
b. n ordered sets of non-negative integers, each starting on a new line and each terminated by -1. Each set is to be stored as an ordered, singly-linked,circular list with a header.
c. A string containing a postfix expression, on a line by itself, without any spaces. The following
may appear:
U set union (destructive, i.e. the result set will be created using some elements of the operand
sets. Extra elements must be recycled.)
I set intersection (destructive)
- set difference (destructive)
\ symmetric difference (destructive)
= equality test (destructive)
< tests whether the first operand set is properly contained in the second operand set (destructive)
& Boolean and (implementation of TRUE/FALSE is your decision)
| Boolean or
! Boolean not
x where x is a lower-case symbol in the range ‘a’ . . . ‘z’ to indicate that a copy should be made
of an input set. This copy will be an ordered singly-linked circular list with a header. A
pointer to the header of the cloned list is to be pushed to the stack. ‘a’ indicates that the first
input set should be copied, ‘b’ indicates that the second input set should be copied, and so on.
The input will be provided to your program through standard input using a shell redirect.
2. The output is the one item that remains on the stack after processing the entire postfix expression. It
may be a set (e.g. a linked list) or a Boolean value. If it is a set, then print the values separated by
spaces. If it is a Boolean value, then print TRUE or FALSE.

one example input file is
6
1 3 5 7 9 11 13 15 17 19 -1
2 4 6 8 10 12 14 16 18 20 -1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 -1
0 3 6 9 12 15 18 -1
1 4 7 10 13 16 19 -1
2 5 8 11 14 17 20 -1
abcdefUUUUIabIacIadIaeIafIUUUU=

what I have done is just the link list my program

 
#include <iostream>
#include <fstream>
#include <cstdio>
 
using namespace std;
int arraysize,num;
 
class Linked_list_Stack
{
private:
struct node
{
int data;
node *next;
};
 
node *top;
node *entry;
node *print;
node *bottom;
node *last_entry;
node *second_last_entry;
 
public:
Linked_list_Stack( );
void pop( );
void push( );
void print_list( );
void show_working( );
};
 
Linked_list_Stack::Linked_list_Stack ( )
{
top=NULL;
bottom=NULL;
}
 
void Linked_list_Stack::push( )
{
 
entry=new node;
if(bottom==NULL)
{ 
entry->data=num;
entry->next=NULL;
bottom=entry;
top=entry;
}
else
{
entry->data=num;
entry->next=NULL;
top->next=entry;
top=entry;
}
cout<<"\n\n\t *** "<<num<<" is pushed onto the Stack."<<endl;
}
 
void Linked_list_Stack::pop( )
{
if(bottom==NULL)
cout<<"\n\n\n\t *** Error : Stack is empty. \n"<<endl;
else
{
for(last_entry=bottom;last_entry->next!=NULL;
last_entry=last_entry->next)
second_last_entry=last_entry;
if(top==bottom)
bottom=NULL;
 
int poped_element=top->data;
delete top;
top=second_last_entry;
top->next=NULL;
cout<<"\n\n\n\t *** "<<poped_element<<" is poped from the Stack."<<endl;
}
}
 
void Linked_list_Stack::print_list( )
{
print=bottom;
 
if(print!=NULL)
cout<<"\n\n\n\n\n\t Values pushed onto Stack are : \n"<<endl;
 
while(print!=NULL)
{
cout<<print->data;
print=print->next;
}
}
 
int main( )
{
int i;
cin>>arraysize;
Linked_list_Stack *obj[arraysize];
 
for(i=0;i<arraysize;i++)
{
obj[i] = new Linked_list_Stack;
while(!cin.eof()) 
{ 
cin>>num;
if(num!=-1)
{
obj[i]->push( );
}
}
obj[i]->print_list( );
cout<<endl;
} 
return 0;
}
 

thanks for helping me

[saraSS]

did I scare you off I hope not I need some help mostly with the lists I have some code ready for the operations between the list mean the union and all that
thanks again

[arne]

did I scare you off I hope not I need some help mostly with the lists I have some code ready for the operations between the list mean the union and all that
thanks again

No, you didn't. It was just night time where I live, so I had to get some sleep :-)

Do you need to build the lists/stacks on your own (for instance, since it is part of the assignment)? If not, you may consider to use the "list" and "stack" containers from the C++ standard template library. This would save you a lot of trouble, I guess.

[saraSS]

ok that sound good but how do I do that ?

[arne]

ok that sound good but how do I do that ?

:)
Start off with getting a good introductory book / tutorial on C++: the template containers are explained in each of these. It's really worth the effort!

For a quick start, you can also have a look at
http://www.cppreference.com
They explain the usage of containers with easy examples and list all member functions to manipulate them.

[saraSS]

in the site you gave me talk a lot about vector can I use the same functions for my list and I'll need to change all my program for some of those functions I dont know I'm confuse

[saraSS]

for example I have the class

 
class list
{
public:
node* begin() const;
node* end() const;
int size() const;
bool empty() const;
void insert(node* p, const data_type& d);
void erase(node*& p);
list();
list (const list& l);
~list();
list& operator= (const list& l);
private:
void free_list();
node* head;
#define tail NULL
};
 
 

then I need to implement some code from the site you gave me for every function I have in this class? and what about the ones that dont have an implementation they dont need implementation because I'm adding #include <list> ?
see I'm really confuse
lol

[arne]

in the site you gave me talk a lot about vector can I use the same functions for my list and I'll need to change all my program for some of those functions I dont know I'm confuse

The question was if you _have_ to implement the containers (i.e. data structures such as list or stack) on your own or if you may want to use the built-in classes.

It is nothing wrong with implementing and using one's own data structures, as long as you have a good reason to do so.

Using the STL containers was just a proposal that may save you some time now (since you don't need to worry about how to implement and debug your data structures) and later (as you know about STL containers next time you have to do some coding).

I am sorry if I confused you :)

[saraSS]

I want to save some time and learn to use the stl but getting confuse here

[arne]

I want to save some time and learn to use the stl but getting confuse here

Upps, sorry didn't see your last post ... that's why I replied to an old posting by you ...

You don't have to implement the member functions of the STL list, it's already done. The STL list contains all functions you typically need for a list, such as inserting elements, finding elements, removing elements and the like. The same holds true for the stack container.
Look at the "Constructors" to see how objects of these classes can be created.

In addition, there are some (generic) algorithms, such as copy, sort, rotate and many more that support operations on STL containers. See the "Algorithms" section on the site I mentioned.

[saraSS]

then if the fuction are in the stl I dont need to include then in my class? if I include then means I need to implement them?

do I need just to work in main and call for all those functions when I need them?

[arne]

then if the fuction are in the stl I dont need to include then in my class? if I include then means I need to implement them?

do I need just to work in main and call for all those functions when I need them?

Yes, you just include the header. I attach a simple example that uses the STL list container and an STL algorithm:

#include <iostream>
#include <list>
 
using namespace std;
 
int main( void )
{
    // define a list that holds ints
    list<int> i_list;
 
    // add new elements at the end of the list (list member function)
    i_list.push_back( 1 );
    i_list.push_back( 2 );
    i_list.push_back( 3 );
    i_list.push_back( 4 );
 
    // traverse the list and print out the elements
    list<int>::iterator iter;
    for( iter=i_list.begin(); iter!=i_list.end(); iter++ ) {
 
        cout << *iter << endl;
    }
 
    // reverse the list (generic STL algorithm)
    reverse( i_list.begin(), i_list.end() );
 
    // traverse the list and print out the elements (again)
    for( iter=i_list.begin(); iter!=i_list.end(); iter++ ) {
 
        cout << *iter << endl;
    }
 
    return 0;
}
 
 

[saraSS]

then yes this way save a lot time .
I trying to make various containers using an array like

list<int> i_list[arraysize];

and use a for loop like this

 
for(i=0;i<arraysize;i++)
{
while(!cin.eof())
{
cin>>num;
if(num!=-1)
{
i_list[i].push_back( num );
}
else
return 0;
} 
}
 
and printing out like this
 
for(i=0;i<arraysize;i++)
{
// traverse the list and print out the elements
list<int>::iterator iter;
for( iter=i_list[i].begin(); iter!=i_list[i].end(); iter++ )
{
cout << *iter << endl;
}
} 
 

I'm not getting errors just blank

[saraSS]

opps was not readding the size of the array now I got
-bash-2.05b$ a.out < hw2file1.txt
279-1-bash-2.05b$
how can I rewrite the while loop so it stops every -1 and keep going with the array of containers ?

[saraSS]

I got it working the list
I guess you when home? ok thanks

do you think this is gonna work as circular list or I need an extra funtion just to make every list a circular lis you know making the end point to the head ?

[arne]

I got it working the list
I guess you when home? ok thanks

do you think this is gonna work as circular list or I need an extra funtion just to make every list a circular lis you know making the end point to the head ?

Good!
Do you really need a circular list?

[saraSS]

the assignment say yes and I need to name every list with and alphabet letter so I can do the operatinons later

[saraSS]

Each set is to be stored as an ordered, singly-linked,
circular list with a header.

[arne]

Each set is to be stored as an ordered, singly-linked,
circular list with a header.

Is that a hint or a demand? Sounds a little like a demand ...

STL lists are neither singly-linked nor circular. And AFAIK the STL does not provide such lists, since they are not that common, I would guess.

That's why I said in the beginning that here is nothing wrong with implementing own containers, if you have a good reason for it. Non-existence is a good reason :-)

One could certainly mimic a circular list using the features of the STL list container ...

[saraSS]

so how can I mimic the circular list I work good with exemples lol

[saraSS]

remember my initial code I rewrite the whiel loop and is working so i'm gonna try to keep working with that one and using a few of the <list> funtions see if help me a lit

[arne]

so how can I mimic the circular list I work good with exemples lol

Hmm, ok. So what distinguishes a serial from circular list?

The successor of the last element is the first element.
Since you want a singly linked list, you don't have to care about the predecessor of the first element, there is only one direction.

In principal, you can either write a wrapper class which simply contains a std::list or you could derive a class from std::and "extend" its functionality.
A wrapper class may have the advantage that you could also "provide" (reduce) the functionality of single-linkedness ... :-)

[saraSS]

I but with the initial program I cant mix and match looks like I mean the funtion that I have and the functions from the library ;(

[arne]

I but with the initial program I cant mix and match looks like I mean the funtion that I have and the functions from the library ;(

It's a tradeoff. You have the choice between
- rewriting your program and writing a wrapper/derived class, and
- making your own circular list container work.

However:
Looking through your former posts, I would recommend that you clarify for yourself the requirements and decide _how_ you want to organize your data. (In the very beginning you talked about a stack, but currently we're at an array of singly-linked circular lists.)
This is the very first (design!) decision you have to take. After that you should think about which data structures are appropriate to implement your design. Otherwise we'll go in circles ...

[saraSS]

is not my decision actually is what the assigment says it says to implement a stack based postfix calculator for sets of integers and those sets need to be store as an ordered, singly-linked,circular list with a header, and I need to use some recycling list for the calculator.
but I though the array was gonna make it easy I guess i need to change the array for a stack of circular list? I dont know lol

[arne]

is not my decision actually is what the assigment says it says to implement a stack based postfix calculator for sets of integers and those sets need to be store as an ordered, singly-linked,circular list with a header, and I need to use some recycling list for the calculator.
but I though the array was gonna make it easy I guess i need to change the array for a stack of circular list? I dont know lol

No, you need both, an array and a stack:

I took the time to read through your assignment. I think what you need are the following "ingredients"

- a node_struct (list element with value and successor pointer)
- a header_struct which points to a first node
- an array/vector of header structs, where you will store and keep the input
- a stack (maybe std::stack<header_struct *>?), where you store the links to the cloned lists
- stack operations (push, pop)
- list operations (clone and all the set mathematics stuff as required by the assignment)

The array/vector is used as a reference when you have to put the same set onto the stack again. The stack itself is what you use for the math. That's why you need both, I would say.

[saraSS]

sound like a plan I'm gonna work on that and let you know thanks

[arne]

sound like a plan I'm gonna work on that and let you know thanks

Yes, please do so. Sounds like quite an interesting assignment :)

[saraSS]

ok so I need to work the postfix evaluation with a stack and I'm ok I guess
how can I set a string to nul in c++?
I've seen something like this but does not work with c++

strset(postfix_expression[count_2] = NULL);

[arne]

ok so I need to work the postfix evaluation with a stack and I'm ok I guess
how can I set a string to nul in c++?
I've seen something like this but does not work with c++

strset(postfix_expression[count_2] = NULL);

Has postfix_expression[count_2] type std::string? Then use member functions
clear() to remove all elements from the string, or
erase() to remove only specific elements.

[saraSS]

I want to initialize Postfix_expression[100] to null but nothing work not even the clear() function

[saraSS]

and my get line function is not working either lol
give me like and infinite look just stuck there is
cin.getline(Postfix_expression,80); why why? lol

[arne]

I want to initialize Postfix_expression[100] to null but nothing work not even the clear() function

Clear() only applies to std::strings, of course, such as in

std::string a_string;
a_string.clear();
 

That's why I asked of which type Postfix_expression is ...

[saraSS]

I'm using array of char for the postfix exprexion thinking that is gonna be easy to pop and pust every letter and do the operations but is getting complicated I got a lot confuse with the strings and that how can I do it with the char Postfix_expression[100] and the get line

[arne]

and my get line function is not working either lol
give me like and infinite look just stuck there is
cin.getline(Postfix_expression,80); why why? lol

Try something like

int main( void )
{
        std::cout << "Please enter a phrase: ";
 
        string txt;
 
        getline( cin, txt );
 
        std::cout << txt << std::endl;
 
        return 0;
}
 

and copy the relevant parts into your code (if this works) ...

[arne]

I'm using array of char for the postfix exprexion thinking that is gonna be easy to pop and pust every letter and do the operations but is getting complicated I got a lot confuse with the strings and that how can I do it with the char Postfix_expression[100] and the get line

You mean for the UUUUUIab... stuff? You can do most (all?) things with std::string that you can do with char[]. You can even convert the read-in string to an char[] by calling std::string::c_str().

But char[] works, too:

int main( void )
{
    char txt[100];
 
        std::cout << "Please enter a phrase: ";
    cin.getline( txt, 100 );
 
    cout << txt << endl;
 
    return 0;
}
 

[saraSS]

still not geting anything the cursor just stay there this is what I'm doing in main
int main( )
{
int m;

Initialize ( ) ;
//cout<<"ok";
cin.getline (postfix,80) ;
cout<<"ok";
SetExpression (postfix) ;
puts(postfix);
strcpy(eval,postfix);
m=Evaluate( );
printf("answer: %d", m );
return 0;
}

[arne]

still not geting anything the cursor just stay there this is what I'm doing in main
int main( )
{
int m;

Initialize ( ) ;
//cout<<"ok";
cin.getline (postfix,80) ;
cout<<"ok";
SetExpression (postfix) ;
puts(postfix);
strcpy(eval,postfix);
m=Evaluate( );
printf("answer: %d", m );
return 0;
}

But that you see nothing is no related to getline: comment out all other function call (except for the getline, puts and printf functions) and you will see that you read in the data. I guess you have an infinite loop somewhere else :)

You may also add an "endl" io manipulator like

cout << "ok" << endl;
 

to see where the problem is. Without "endl" the ouput buffer is not flushed. and you cannot see where the program currently is.

[saraSS]

done that and i print out the ok before that line but not the one after so i think is the get line the mess up

[arne]

done that and i print out the ok before that line but not the one after so i think is the get line the mess up

Try this code (it's _your_ code reduced to the essential parts with only the postfix declaration added):

#include <iostream>
using namespace::std;
 
int main( )
{
    int m;
    char postfix[80];     // added this line 
 
//    Initialize ( ) ;
    cout<<"ok" << endl;
    cin.getline (postfix,80) ;
    cout<<"ok" << endl;
//    SetExpression (postfix) ;
    puts(postfix);
//    strcpy(eval,postfix);
//    m=Evaluate( );
    printf("answer: %d", m );
    return 0;
}
 

This runs fine on my machine: It prints "ok" 2 times, the input string and the value of m. No endless loop here.

[saraSS]

I had char postfix[80]; as a gloval variable but even like the way you told me
still cant get my line ?

 #include <iostream> 
using namespace std;
#define MAX 80
 
char stack[MAX] ;
char eval[MAX] ;
char *s, *t ; /*pointers to input and output strings*/
int top; /*Stack top*/
 
/*Function Prototypes*/
void Initialize (void);
void SetExpression (char *);
char Pop (void );
void Push (char);
int Evaluate(void);
 
int main( )
{
int m;
char postfix[80]; 
 
Initialize ( ) ;
cout<<"ok";
cin.getline (postfix,80) ;
cout<<"ok";
SetExpression (postfix) ;
puts(postfix);
strcpy(eval,postfix);
m=Evaluate( );
printf("answer: %d", m );
return 0;
}
 
void Initialize (void)
{
top = -1 ;/*Make stack empty*/
}
 
void SetExpression ( char *str )
{
s = str ;
}
 
/* adds operator to the stack */
void Push ( char c )
{
if ( top == MAX - 1 )
printf ( "\nStack is full.\n" ) ;
else
{
top++ ;
stack[top] = c ;
}
}
 
/* pops an operator from the stack */
char Pop ( void )
{
if ( top == -1 ) /* Stack is empty*/
return -1 ;
else
{
char item = stack[top] ;
top-- ;
return item ;
}
}
 
int Evaluate(void)
{
int i,l,a,b,q,z;
l=strlen(eval);
for(i=0;i<l;i++)
{
if ( isdigit ( eval[i] ) )
{
Push(eval[i]);
}
else if ( eval[i] == 'U' || eval[i] == 'I' || eval[i] == '-' || eval[i] == '\' || eval[i] == '=' 
|| eval[i] == '<' || eval[i] == '&' || eval[i] == '|' || eval[i] == '&' )
{
a = Pop ( );
b = Pop ( );
 
switch( eval[i] )
{
case 'U' : break;
case 'I' : break;
case '-' : break;
case '\' : break;
case '<' : break;
case '&' : break;
case '|' : break;
case '!' : break;
}
Push ( q );
}
}
z = Pop ( );
return z;
}
 

what I'm doing wrong?

[arne]

See, I just commented out all insignificant function calls. This _definitively_ works and reads in a line from stdin. Please copy and try this code (without all the other functions you have written) in a new program, so that we have a basis on which we can proceed. BTW, the code you posted does not compile. May it be that you change your code, compile, ignore the errors and execute an old executable?

#include <iostream>
using namespace std;
#define MAX 80
 
char stack[MAX] ;
char eval[MAX] ;
char *s, *t ; /*pointers to input and output strings*/
int top; /*Stack top*/
 
/*Function Prototypes*/
void Initialize (void);
void SetExpression (char *);
char Pop (void );
void Push (char);
int Evaluate(void);
 
int main( )
{
    int m;
    char postfix[80];
 
//    Initialize ( ) ;
    cout<<"ok";
    cin.getline (postfix,80) ;
    cout<<"ok";
//    SetExpression (postfix) ;
    puts(postfix);
    strcpy(eval,postfix);
//    m=Evaluate( );
    printf("answer: %d", m );
    return 0;
}
 

[saraSS]

yes it does not compile Im trying to get the line from this file so i'm doing the compilation and getting this
-bash-2.05b$ g++ hi.cpp
-bash-2.05b$ a.out hw2file2.txt
ok
only one ok the imput file is abcdefUUUUIabIacIadIaeIafIUUUU=
and still nothing I dont know I am running the new version of the program

[arne]

yes it does not compile Im trying to get the line from this file so i'm doing the compilation and getting this
-bash-2.05b$ g++ hi.cpp
-bash-2.05b$ a.out hw2file2.txt
ok
only one ok the imput file is abcdefUUUUIabIacIadIaeIafIUUUU=
and still nothing I dont know I am running the new version of the program

Ah, you tried to get the data from a file, not typing it in by hand? Then it's clear why you get no line :)

Try

-bash-2.05b$ a.out < hw2file2.txt

Note the '<' ...

[saraSS]

why is it different for this file with all my file I usually use only a.out hw2file2.txt?

[arne]

why is it different for this file with all my file I usually use only a.out hw2file2.txt?

Because you try to get the data via cin! The file content is redirected to your program by '<'. If you use
a.out hw2file2.txt
you pass only the file name as a parameter. You still have to open the file then. Different approach.

BTW, you can also use '>' to redirect the output of your program to another file.

Did you get the data now from the file?