string and stack comparison failure

[ace8957]

Hi all,

So I'm working on this program to detect if the w' in a string in the form of w$w' satisfies the condition that w' is the reverse of w. The only problem is that I have a logic error that I don't understand.

If I input the string "123456$654321" the program says that the string satisfies the condition, which is correct. However, when I put in "123456$654311" the program still says that the string satisfies the condition, which is wrong. I know it sounds simple, but this one logic error has baffled me for about 5 hours now and I'm at my wits end, so if any of you have any input, it would be greatly appreciated.

The code is all in one file for convenience at this point:

#include <iostream>
#include <string>
using namespace std;
typedef char stacktype;


class Stack{
    private:
    int top;
    int size;
    stacktype *arr;

    public:
    Stack(int size) {
        if (size <= 0) {
            throw string("Invalid stack size.");
        }
        arr = new stacktype[size];
        top = -1;
    }//end copy constructor

    void push(stacktype value) {
        if(top==size) {
            throw string("Stack storage overflow");
        }
        top++;
        arr[top]=value;
    }//end push

    stacktype peek() {
        if(top == -1) {
            throw string("Stack empty.");
        }
        return arr[top];
    }//end peek

    void pop() {
        if(top == -1) {
            throw string("Stack empty");
        }
        top--;
    }//end pop

    bool isEmpty() {
        return (top == -1);
    }//end isEmpty

    int getTop() {
        return top;
    }//end getTop


    ~Stack() {
        delete[] arr;
    }//end destructor

};//end stack class

//void stringcom(string str);//prototype


void stringcomp(string str) {

    cout << "inside function." << endl;
    int i=0;
    bool inlang;//tells if the string is in the language
    Stack mystack(str.size());
    cout << "Stack created" << endl;
    while(str[i] != '$')
    {
        mystack.push(str[i]);
        i++;
    }//end while loop

    //increment i to skip $
    i++;



    //match reverse of w as stipulated
    inlang = true;
    int k = i-2;

    while(inlang && (i<str.size()))
    {
        try
       {
            if(mystack.peek() == str[k])
            {
                 mystack.pop();
                i++;
                k--;
            }
            else {
                inlang = false;
            }
        }//end try

       catch (string failure)
        {
            cout << failure << endl;
            inlang=false;
        }//end catch



    }//end while

    if(inlang && mystack.isEmpty()) {
        cout << "The string is in the language." << endl;
    }
    else {
        cout << "The string is not in the language." << endl;
    }

}//end function





int main() {

	string mystring;
	mystring = "123456$654311";
	stringcomp(mystring);

	return 0;
}

[mitrmkar]

Basically you are pushing the left-hand side of the string onto the stack and then comparing that data with the very same left-hand side of the string. The right-hand side of the string is not involved in the comparisons.

[ixmike88]

no time to look at the function right now, so sorry if you wanted feedback on that

but this worked fine for me:

string str="123456$654321";
int pos;
pos = str.find('$');

int len = (pos * 2) + 1;

if(len != str.size())
{
	cout << "error"
	return 0;
}

for(int i = 0; i < pos; i++)
{
	if(str[i] != str[len - i - 1])
	{
		cout << "error";
		return 0;
	}
}

[Earth Wyrm]

Mitrmkar's right. See that you are initialising k as an index to the character directly before the $, rather than to the character at the end of the string.

[ace8957]

Thanks very much, I will make changes to fix the comparison. Hopefully that the extent of the issues.