C++ on Stack,Queue,Plalindrome,tolowercase(),touppercase( ) help....!!

jason07 · 10-12-2005, 12:14 AM

Write a program that read a line of text, changes each uppercase letter to lowercase and places each letter both in a queue and onto a stack.
The program should then verify whether the line of text is a palindrome

Output:

Please enter a line of text
I am A.I

i AM a.i

This is a palindrome

--------------------------------------------------------------------------this what i have done...
still hv some problems...

1. Program Output:-
Please enter a line of text:
i am not a.i
i am not a.i
This is a palindrome <-----it must be this is not a palindrome
(uncorrect answers)
Press any key to continue

2. How to use the touppercase() n tolowercase()combine as below???
how to loop word by word?

I am A.I

i AM a.i

Code:

Code:

#include<iostream> 
#include <cstdlib> // For EXIT_FAILURE and EXIT_SUCCESS 
#include <fstream> 
#include<string> 

#include <algorithm> 
#include <iomanip> 
#include <cctype> 

using namespace std; 

const int MAX=50;    // initialize max string size of 50 characters 
typedef char StackElement;  // define StackElement 
typedef char QueueElement;  // define QueueElement 
class Stack 
{ 
public: 
   Stack(){top=-1;arr[MAX]=0;}   // default stack constructor 
      void push(StackElement & ch);  // push function 
      StackElement topNpop();         // top and pop functions combined 
      bool empty() const;            // empty function 
private: 
      StackElement arr[MAX];    // define char array 
      int   top;                  // define int top 
    
}; 
/******************************************* 
FUNCTION: push() 
DESCRIPTION: Pushes an element onto the stack 
PRECONDITION: Waiting for function call 
POSTCONTION: New element character on top of stack 
*******************************************/ 
inline void Stack::push(StackElement & ch) 
{ 
   if(top<MAX) 
   { 
      top++;          // increment top 
      arr[top]=ch;  // push onto stack 
   } 
   else 
   { 
      cout<<"Stack is full.\n";  // display stack is full 
   } 


} 
/******************************************* 
FUNCTION: topNpop() 
DESCRIPTION: Reads and pops top element off the stack 
PRECONDIION: Waiting for function call 
POSTCONDITION:  One element read and removed fromt he stack 
RETURN: Top element from stack 
********************************************/ 

inline StackElement Stack::topNpop() 
{ 
   if(top>-1) 
   { 
      return(arr[top]);  // returns top element 
      top--;            // remove froms stack 
   } 
   else 
   { 
      cout<<"Stack is empty.\n";  // display stack is empty 
      return(0); 

   } 

} 
/******************************************* 
FUNCTION: empty() 
DESCRIPTION: returns result value if stack is empty 
PRECONDITION: result=false 
POSTCONDITION: result may be true or remain false 
RETURN: result if true or false 
********************************************/          
inline bool Stack::empty() const 
{ 
   bool result=false;   // initialize bool as false 
   if (top==-1)          
   { 
      result=true;        // if top is -1 return result true 
      return(result); 
   } 
   else 
   { 
      return(result);     // else return false 
   } 
} 
class Queue                           // Queue class 
{ 
public: 
      Queue(){front=0, back=0;arr[MAX]=0;}   // Queue default constructor 
      void addq(QueueElement & ch);          // define addq 
      QueueElement frontNremoveq();         // define frontNremove 
private: 
      QueueElement arr[MAX];            // initialize QueueElement array 
      int front, back;                  // initialize int front and back 
    
}; 
/******************************************* 
FUNCTION: addq() 
DESCRIPTION: adds an element onto the queue 
PRECONDITION: Waiting for element to add 
POSTCONDITION: New element now on the queue 
********************************************/ 
inline void Queue::addq(QueueElement &ch) 
{ 
   if(front!=(back+1)%MAX) 
   { 
      arr[back]=ch;     // add element to back of queue 
      back=(back+1)%MAX; 
   } 
   else 
   { 
      cerr<<"Error Queue is full\n";  // display queue is full 
   } 
} 
/******************************************* 
FUNCTION: frontNremoveq() 
DESCRIPTION: reads and removes front element from queue 
PRECONDITION: front pointing to front of queue 
POSTCONDITION: front element is returned and then incremented 
********************************************/ 
inline QueueElement Queue::frontNremoveq() 
{ 
   if(front!=back) 
   { 
      return(arr[front]);    // return front element 
      front++;            // remove front element 
   } 
   else 
   { 
      cout<<"Queue is empty.\n";  // display queue is empty 
      return(0); 
   } 
} 

/***************************MAIN******************************/ 
int main() 
{ 
   Stack S;   // initialize stack 
   Queue Q;   // initialize queue 
   string s ; 
   int i=0;   // initialze int 'i' 
   char string[MAX];  // initialize char string 
   bool RESULT=false;  // initilize bool RESULT to false 
    
  
strcpy(string," "); 
//transform(s.begin(),s.end(),s.begin(),toupper); 

cout << "Please enter a line of text: " << endl; 

cin.getline (string,100); 

while(string[i]!=NULL) 
   { 
      S.push(string[i]);  // push chars individually from string to 
      Q.addq(string[i]);      // stack and queue 
      i++;      // next char 
   } 
   while(i>0) 
   { 
      if(S.topNpop()==Q.frontNremoveq())  // compare each element from 
      {                              // stack and queue 
         RESULT=true;  // if same for all chars return true 
      } 
      else 
      { 
         RESULT=false;  // if not same for any char break and return false 
         break; 
      } 
      i--; 
   }    


if(RESULT==true) 
   { 
      cout<<string<<" \nThis is a palindrome\n";  // display if true 
   } 
   else 
   { 
      cout<<string<<" \nThis is not a palindrome\n"; // display if false 
   } 
    
      cout<<s<<s<<endl; 

   return 0; 
}

redhead · 10-12-2005, 02:30 AM

Wouldn't it be much easier to use std::stack types for the stack, instead of creating your own stack class ?
Then have two stacks, one where the string is stored reversed, and compare the two, if one item in them don't match, then error out.

And for the toupper()/tolower() thingy you might wanna check this thread. As you can see there the shift from lowert to upper is actualy a logic or with 32, aswell as when it's to lowere you're using logic and.
Here is a small program for that

Code:

#include <string>
#include <iostream>
int main()
{
	std::string text("this iS a TEst");
	std::string sResult;
	for(unsigned int i = 0; i < text.size(); ++i)
	  {
	    if(text[i] >= 'A' && text[i] <= 'Z')
	      sResult += (text[i] | 32);
	    else
	      if(text[i] >= 'a' && text[i] <= 'z')
		sResult += (text[i] & (~32));
	      else
		sResult += text[i];
	  }
	std::cout << text << std::endl;
	std::cout << sResult << std::endl;
	return 0;
}

redhead · 10-12-2005, 04:00 AM

For a true palidrom, this would work:

Code:

#include <iostream>
#include <stack>

int main()
{
  std::string INput; /* normal input */
  std::string inPUT; /* altered input */
  std::stack <char> STak;   /* normal stack */
  std::stack <char> stAK;   /* altered stack */
  char ptr;
  std::cout << "Please enter a line: ";
  std::cout.flush();
  std::getline(std::cin, INput);
  /* convert the line */
  
  for(unsigned int i=0; i < INput.size(); ++i)
    {
      if(INput[i] >= 'A' && INput[i] <= 'Z')
	inPUT += (INput[i] | 32);
      else
	if(INput[i] >= 'a' && INput[i] <= 'z')
	  inPUT += (INput[i] & (~32));
	else
	  inPUT += INput[i];
      /* push onto first stack */
      STak.push(INput[i]);
    }
  /* push converted line _reversed_ onto second stack */
  for(int i=inPUT.size()-1; i >= 0; i--)
      stAK.push(inPUT[i]);
    
  /* the stacks will allways be of same size */
  while(stAK.size()>1&& (stAK.top() == STak.top()))
    { /*just pop those stacks */
      stAK.pop();
      STak.pop();
   }
  std::cout << inPUT << std::endl;
  std::cout << INput << std::endl;
  std::cout << "Is " << (stAK.size()>1? "not ":"") << "a palidrom" << std::endl;
  return 0;
}

But since your example is showing a "i am AM I" as beeing a palidrom, hence am <> AM isn't a true palidrom, but we'll handle it anyway..
this would do it:

Code:

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

int main()
{
  std::string INput; /* normal input */
  std::string inPUT; /* altered input */
  std::string temp;
  std::vector <std::string> words;
  std::stack <char> STak;   /* normal stack */
  std::stack <char> stAK;   /* altered stack */
  char *ptr;
  std::cout << "Please enter a line: ";
  std::cout.flush();
  std::getline(std::cin, INput);
  /* convert the line */
  
  for(unsigned int i=0; i < INput.size(); ++i)
    {
      if(INput[i] >= 'A' && INput[i] <= 'Z')
	inPUT += (INput[i] | 32);
      else
	if(INput[i] >= 'a' && INput[i] <= 'z')
	  inPUT += (INput[i] & (~32));
	else
	  inPUT += INput[i];
      /* push onto first stack */
      STak.push(INput[i]);
    }
  /* align the input line wordwise */
  temp=inPUT.substr(0);
  /* we assume they are using space between each words */
  ptr = strtok ((char*) temp.c_str()," ");
  while (ptr != NULL)
  {
    words.push_back(ptr);
    ptr = strtok (NULL, " ");
  }

  /* push converted line _reversed_wordwise_ onto second stack */
  for(int i=words.size()-1; i >= 0; i--)
    {
      for(unsigned int j=0; j < words[i].size(); ++j)
	  stAK.push(words[i][j]);
      if(i>0)
	stAK.push(' ');
    }
  /* the stacks will allways be of same size */
  while(stAK.size() > 1 && (STak.top() == stAK.top()))
    { /*just pop those stacks */
      stAK.pop();
      STak.pop();
    }
  std::cout << inPUT << std::endl;
  std::cout << INput << std::endl;
  std::cout << "Is " << (stAK.size()>1? "not ":"") << "a palidrom" << std::endl;
  return 0;
}

edit: just realised you should use a queue aswell, you could just change the second stack to beeing a queue, since C++ provides you with a queue class, I dont see why you would make your own..

Only change would be, that you ask for empty() uppon if it is or not a palidrom and you ask for first() instead of top(), something like this for the true palidrom program:

Code:

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

int main()
{
  std::string input; /* normal input */
  std::string INPUT; /* altered input */
  std::stack <char> stack;   /* normal stack */
  std::queue <char> queue;   /* altered stack */

  std::cout << "Please enter a line: ";
  std::cout.flush();
  std::getline(std::cin, input);
  /* convert the line */
  
  /* push onto stack and queue*/
  for(unsigned int i=0; i < input.size(); ++i)
    {
      if(input[i] >= 'A' && input[i] <= 'Z')
	queue.push(input[i] | 32);
      else
	if(input[i] >= 'a' && input[i] <= 'z')
	    queue.push(input[i] & (~32));
	else
	   queue.push(input[i]);
      stack.push(input[i]);
      INPUT += queue.back();
    }


  while(!queue.empty() && (stack.top() == queue.front()))
    { /*just pop those stacks/queues */
      stack.pop();
      queue.pop();
    }
  std::cout << input << std::endl;
  std::cout << INPUT << std::endl;
  std::cout << "Is " << (queue.empty()? "":"not ") << "a palidrom" << std::endl;
  return 0;
}

But since we still have to take advantage of the word like palidrom way, then this would do:

Code:

#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <vector>

int main()
{
  std::string input; /* normal input */
  std::string INPUT; /* altered input */
  std::string temp;
  std::stack <char> stack;   /* normal stack */
  std::queue <char> queue;   /* altered stack */
  std::vector <std::string> words;
  char *ptr;
  std::cout << "Please enter a line: ";
  std::cout.flush();
  std::getline(std::cin, input);
  /* convert the line */
  
  /* push onto stack and queue*/
  for(unsigned int i=0; i < input.size(); ++i)
    {
      if(input[i] >= 'A' && input[i] <= 'Z')
	INPUT += (input[i] | 32);
      else
	if(input[i] >= 'a' && input[i] <= 'z')
	    INPUT += (input[i] & (~32));
	else
	   INPUT += input[i];
      stack.push(input[i]);
    }
  temp=INPUT.substr(0);
  /* we assume they are using space between each words */
  ptr = strtok ((char*) temp.c_str()," ");
  while (ptr != NULL)
  {
    words.push_back(ptr);
    ptr = strtok (NULL, " ");
  }
 /* push converted line _wordwise_reverted_ onto queue */
  for(unsigned int i=0; i<words.size(); ++i)
    {
      for(int j=words[i].size()-1; j >=0; j--)
	  queue.push(words[i][j]);
      if(i<words.size()-1)
	queue.push(' ');
    }
  while(!queue.empty() && (stack.top() == queue.front()))
    { /*just pop those stacks/queues */
      stack.pop();
      queue.pop();
    }
  std::cout << input << std::endl;
  std::cout << INPUT << std::endl;
  std::cout << "Is " << (queue.empty()? "":"not ") << "a palidrom" << std::endl;
  return 0;
}

jason07 · 10-12-2005, 08:05 AM

Which one tat exactly same as my question ask??
like below???

Output:
for correct palindrome:

Please enter a line of text
I am A.I

i AM a.i

This is a palindrome

for incorrect palindrome:

Please enter a line of text
I like A

i LIKE a

This is not a palindrome

redhead · 10-12-2005, 09:25 PM

What are you asking here ?? should the program guess what you've written ? given that
A.I should be a palindrome for I am I don't get i then... Since a palindrome is something like rotator which will produce the same word no matter if you read from left to right or the other way around..
Your program should do it word wise, like this is good is this since none of these words are palindromes themself, but the form of the sentence is, the last version of my program will tell you the sentence is, since it looks at the words and compare them, where the first version will look for a true palindrome like rotator where each words given in the sentence themself should also be palindromes aswell as the sentence should form a palindrome.

teknomage1 · 10-12-2005, 09:33 PM

I suspect your coding skills are being exploited for someone's homework assignment, redhead.

redhead · 10-12-2005, 10:15 PM

I know, but yesterday I was bored, and it made a nice break in my routine to fresh up on my knowledge of queue and stack implementation in C++

But the fact that his first post showed some degree of knowledge in using classes, fooled me into thinking that this was just someone blinded by looking too long at their own mistakes and in need of a small code segment which did it right, in order to determain where he went wrong.

teknomage1 · 10-12-2005, 10:22 PM

You are too kind, as always.