469,323 Members | 1,567 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,323 developers. It's quick & easy.

palindrome check programe using stack

18
hi, sorry to disturb again, currently i have an assignment on stacks and as show in the the title, i need to use stacks to determine palindrome.

i've done part of my code, here it is:
Expand|Select|Wrap|Line Numbers
  1.  
  2. // Write your name, student number, part-time/full time, degree here
  3. #include <string>
  4. #include <iostream>
  5. #define STACKSIZE 80
  6. #define TRUE 1
  7. #define FALSE 0
  8. using namespace std;
  9.  
  10. class Stack 
  11. {
  12.    public:
  13.           void StackInit();
  14.           int IsStackEmpty();
  15.           int IsStackFull();
  16.           int StackPush(char c);
  17.           char StackPop();
  18.           char ViewStackTop();
  19.    private:
  20.           char myStack[80];
  21.           int top;
  22. };
  23.  
  24. string pstring;
  25.  
  26. int main()
  27. {
  28.     // write your code here
  29.     cout << "This Is A Palindrome Check Programe" << endl;
  30.     cout << "Please Enter Anything For Palindrome Check" << endl;
  31.  
  32.     cin >> pstring;
  33.  
  34.  
  35.  
  36.  
  37.     system("pause");
  38.     return 0;
  39. }
  40.  
  41. void Stack::StackInit()
  42. {
  43.   top = -1;
  44. }
  45.  
  46. int Stack::IsStackEmpty()
  47. {
  48.   if (top == -1)
  49.     return TRUE;
  50.   return FALSE;
  51. }
  52.  
  53. int Stack::IsStackFull()
  54. {
  55.   if (top == (STACKSIZE - 1))
  56.     return TRUE;
  57.   return FALSE;
  58. }
  59.  
  60. int Stack::StackPush(char c)
  61. {
  62.   if (top == (STACKSIZE - 1))
  63.     return FALSE;
  64.   myStack[++top] = c;
  65.   return TRUE;
  66. }
  67.  
  68. char Stack::StackPop()
  69. {
  70.   if (top == -1)
  71.     return '\0';
  72.   return myStack[top--];
  73. }
  74.  
  75. char Stack::ViewStackTop()
  76. {
  77.   if (top == -1)
  78.     return '\0';
  79.   return myStack[top];
  80. }
  81.  
  82.  
  83.  
alright, i am stuck again, i need to ignore space, punct and digits, i know using isdigit / ispunct / isspace. however i ahh.. duno where to put them. hmmm, simple guide will do. thanks, meanwhile, i will be doing search on google as well. please help. thanks
Aug 16 '08 #1
7 22146
weaknessforcats
9,208 Expert Mod 8TB
It looks like you need an algorithm. All I see is some stack code, which is not complete.

Put a loop in main(). Create a stack and then parse the string from left to right pushing each letter or number onto the stack (use isalnum to determine a letter or a number).

Then create a second stack and oparse the string from right to left pushing each letter or number onto the stack.

Finally, in a third loop pop each stack and compare letters. If not equal, you do not have a palindrome. If equal, pop them both again. If the letters remain equal when the stacks are empty, you have a palindrome.

Note that the loops could be replaced by recursive calls. But since this might produce a lot of nested calls, loops are more efficient.

Then post agian.
Aug 16 '08 #2
xiaolim
18
Expand|Select|Wrap|Line Numbers
  1.  
  2. #include <ctype.h>
  3. #include <stdio.h>
  4. #include <string.h>
  5. #include <iostream>
  6. #define STACKSIZE 80
  7. #define TRUE 1
  8. #define FALSE 0
  9. using namespace std;
  10.  
  11. class Stack 
  12. {
  13.    public:
  14.           void StackInit();
  15.           int IsStackEmpty();
  16.           int IsStackFull();
  17.           int StackPush(char c);
  18.           char StackPop();
  19.           char ViewStackTop();
  20.    private:
  21.           char myStack[80];
  22.           int top;
  23. };
  24.  
  25.  
  26. char input[100], output[100];
  27. Stack s;
  28.  
  29. int main()
  30. {
  31.     char c;
  32.     s.StackInit();
  33.     // write your code here
  34.     cout << "This Is A Palindrome Check Programe" << endl;
  35.     cout << "Please Enter Anything For Palindrome Check" << endl;
  36.     fflush(stdin);
  37.     cin.getline(input, 100);
  38.  
  39.     for (int i=0;i<strlen(input);i++)
  40.  
  41.  
  42.     //check input is upper and convert to lower
  43.     while (input[i])
  44.     {
  45.     c=input[i];
  46.     putchar (tolower(c));
  47.     i++;
  48.     }
  49.  
  50.     //check input have punct or space
  51.     if (isspace(input[i]))
  52.  
  53.  
  54.  
  55.     //pass converted string to a temp
  56.     c = input[i];
  57.  
  58.     //check input is only alpha and push to stack
  59.     if(isalpha(input[i]))   
  60.     s.StackPush(input[i]);
  61.     i++;
  62.  
  63.  
  64.     //compare 1st 2 char with last 2 char
  65.     if strcmp( ?????? )
  66.  
  67.     //output
  68.     cout << "The String " << c << "Is A Palindrome." << endl;
  69.  
  70.     else
  71.  
  72.     cout << "The String " << c << "Is Not A Palindrome." << endl;    
  73.  
  74.  
  75.  
  76.     system("pause");
  77.     return 0;
  78. }
  79.  
  80. void Stack::StackInit()
  81. {
  82.   top = -1;
  83. }
  84.  
  85. int Stack::IsStackEmpty()
  86. {
  87.   if (top == -1)
  88.     return TRUE;
  89.   return FALSE;
  90. }
  91.  
  92. int Stack::IsStackFull()
  93. {
  94.   if (top == (STACKSIZE - 1))
  95.     return TRUE;
  96.   return FALSE;
  97. }
  98.  
  99. int Stack::StackPush(char c)
  100. {
  101.   if (top == (STACKSIZE - 1))
  102.     return FALSE;
  103.   myStack[++top] = c;
  104.   return TRUE;
  105. }
  106.  
  107. char Stack::StackPop()
  108. {
  109.   if (top == -1)
  110.     return '\0';
  111.   return myStack[top--];
  112. }
  113.  
  114. char Stack::ViewStackTop()
  115. {
  116.   if (top == -1)
  117.     return '\0';
  118.   return myStack[top];
  119. }
  120.  
  121.  
  122.  
alright, i tried, i briefly list out what i should do.

1. StackInit.
2. promt user to enter anything.
3. check if is uppercase, if yes, convert to lowercase then move to next char
4. ignore all space and punct.
5. pass the converted string to another temp var.
6. check if is only alpha, if yes, push char in stack. if not, ignore go to next char
7. pop the last 2 char.
8. compare 1st 2 char with last 2 char, if is similar, then output result, if not, display msg.

so, quite alot of problem, maybe someone can help me check out n tell me where i go wrong? i keep can't compile on the "tolower" part. thanks alot
Aug 18 '08 #3
weaknessforcats
9,208 Expert Mod 8TB
OK, I see where you are trying to build a stack of the letters as you go from left to right.

Where is the stack for the letters when you go from right to left? I see only one stack.

When you get to strcmp(????) both stacks need to be complete. You then pop from eaxch stack and if the two stacks are identical, you have a palindrome.
Aug 18 '08 #4
xiaolim
18
Expand|Select|Wrap|Line Numbers
  1.  
  2. int main()
  3. {
  4.     char input[100], output[100];
  5.     Stack s1;
  6.     Stack s2;
  7.     Stack s3;
  8.     s1.StackInit();
  9.  
  10.     // write your code here
  11.     cout << "This Is A Palindrome Check Programe" << endl;
  12.     cout << "Please Enter Anything For Palindrome Check" << endl;
  13.     fflush(stdin);
  14.     cin.getline(input, 100);
  15.  
  16.  
  17.     for (int i=0;i<strlen(input);i++)
  18.  
  19.     {
  20.      if (isupper(input[i]))
  21.      input[i]=tolower(input[i]);
  22.  
  23.      if (isspace(input[i]))
  24.      i++;
  25.  
  26.      if (ispunct(input[i]))
  27.      i++;
  28.  
  29.      if (isalpha(input[i]))
  30.      s1.StackPush(input[i]) & s2.StackPush(input[i]);
  31.  
  32.      }
  33.  
  34.  
  35.  
  36.       cout << "Reverse String: ";
  37.       while (!s1.IsStackEmpty())
  38.       cout << s1.StackPop();
  39.       cout << "" << endl;
  40.  
  41.  
  42.  
  43.     system("pause");
  44.     return 0;
  45. }
  46.  
  47.  
alright, i' ve made some changes in my code. As shown in the code, i declared 3 stack, then i push input to stack1 & stack2 and get them back in reverse order. so now i want to push the reversed string to stack3 and then do a compare if they matches or not. so how do i push them back?
Aug 19 '08 #5
weaknessforcats
9,208 Expert Mod 8TB
I don't think you've got the idea yet.

Take the palimdrome: Madam, I'm Adam.

First, convert to lower case: madam i'm adam
Second: Replace all punctuation with a space: madam i m adam
Third: Create two stacks.
Fourth: Stack one push from the left to right
m
a
d
a
m
i
m
a
d
a
m

Fifth:Stack two push from the right to left:
m
a
d
a
m
i
m
a
d
a
m

Now can you see the two stacks are the same? You test this by popping each stack and comparing letters. If the letters match, pop again and repeat. When the stacks are empty and the letters always matchedm, then you have a palinrome.

There's no third stack.
Aug 20 '08 #6
#include<iostream>
using namespace std;
int main()
{
int first;
int last;
first=0;
char arr[100];
cout<<"\t\t**********Palindrome**********"<<endl<< endl<<endl;
cout<<"Enter a word to check wether it is a Palindrome: "<<endl<<endl;
cin>>arr;
last=strlen(arr)-1;
if(arr[first]==arr[last])
{

cout<<"It is a Palindrome"<<endl;
while(first<100)
{
first ++;
last --;
}
}
else
{
cout<<"It is NOT a Palindrome"<<endl;
}
system("PAUSE");
return 0;
}
Apr 2 '10 #7
newb16
687 512MB
Dug up thread is dug up.
Apr 2 '10 #8

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

24 posts views Thread by Runic911 | last post: by
4 posts views Thread by Lorin Leone | last post: by
32 posts views Thread by ramakrishnadeepak | last post: by
5 posts views Thread by rubyhuang | last post: by
2 posts views Thread by bigtd08 | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by Gurmeet2796 | last post: by
reply views Thread by harlem98 | last post: by
reply views Thread by listenups61195 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.