Meh, I can do this without using a stack, but this assignment requires me to...

[Sorc.Polgara]

Ok, so here is the assignment:

ASSIGNMENT #3
A stack can be used to recognize certain types of patterns. Consider the pattern STRING1#STRING2 where neither STRING1 or STRING2 contain the character '#' and STRING2 is the reverse of STRING1. For example, the string A32w#w23A matches the pattern but A3qX#Xq2A does not.

Write a program (Using your stack routines) that reads strings and indicates if the string matches the pattern. You may use this TESTFILE to check your work.

Here is what is in the testfile the professor provided:

Axd%k#k%dxA
I*88h(#(h89*I
elbewashere#erehsaw
thiswillwork#thiswillwork
lasttest#tsettsal

Ok, so from looking at the test file I realized that you are just not looking for a pattern like Abc123#321cbA and test#test, but also something like this helloworld#helloworld.

My problem is that I have a feeling that somehow using a stack to look for the pattern should enable you to detect all three of the cases.  Meaning, you shouldn't have to test for more than one case, but one test should work for all three... I just have a feeling this is what the professor wants.  I haven't asked the professor since the next class is on Tuesday.

I tried visualizing the 3 cases by drawing what they would look like when put in a single stack and also if I were to use two stacks; fill one stack until I reach the character '#' and then fill the other stack.  However I can't figure out an algorithm using a stack or stacks that would test for all 3 cases in one.  The first two, Abc123#321cbA and test#test I can see how they both could be tested using the same algorithm, but the other case helloworld#helloworld I can't figure out.

NOTE:  The stack class I'm using is a template stack class that I wrote and has the same functions as the STL stack class.  My professor doesn't want us to use the STL one, but write our own.

NOTE2:  Like I said in the title, I can easily do this not using a stack and even using a stack(s) but I'd have to test for the 3rd possible case with a separate algorithm.

[Arta]

Why does 'helloworld#helloworld' match the pattern? I would say it does not. String1 is not the reverse of string2 in that case.

[Sorc.Polgara]

Aight, I guess I'll wait to ask my professor whether something like helloworld#helloworld is a valid pattern.

[Arta]

I doubt it is. If I'm right about that, then this assignment becomes very easy

[Sorc.Polgara]

I doubt it is. If I'm right about that, then this assignment becomes very easy

Yes.  So easy, it's kind of a stupid and inefficient way of learning to use a stack.  I mean, you could simply use the string manipulation routine _strrev() or write your own routine, and look for equivalence.

Something like requiring us to write a postfix or prefix calculator would be much better.

Having us write our own stack class is probably the only thing beneficial in the assignment.  My templated stack class that I wrote is much more advanced than the stack class he expects us to write, which is one that isn't templated and only has push, pop, and isEmpty.


EDIT:  Looks like I'm not the only one that finds it stupid to use it for string reversal.

Some stack applications:

1. To model "real stack" in computer world: Recursion, Procedure Calling, etc.
2. Checking palindrome (although checking palindrome using Queue & Stack is 'stupid').
3. To read an input from keyboard in text editing with backspace key.
4. To reverse input data, (another stupid idea to use stack for reversing data).
5. Checking balanced parentheses.
6. Postfix calculation.
7. Converting mathematical expressions. Prefix, Infix, or Postfix.

Found this quote from here.

[Yoni]

NO, IT'S NOT STUPID. This is an algorithms question, not a programming question. They want to see if you know what LIFO means. JEEZ.

It's one of those basic algorithms questions, you know? They always make you do those things, not because they're practical, but because they're theoretical.

Check if something is <string><special_char><rev_string>.

One of the classic ones.

Implement a stack with 2 queues. Implement a queue with 2 stacks.

Nobody ever does this, do they?

A binary heap can be built in 2n steps. Prove it can be built in cn + O(log n) steps where c < 2.

2 is as good as any number.

Show that quicksort outperforms mergesort in the average case.

Not all cases are average. PFFFFFFFT.

Edit: I'm an asshole.

[Sorc.Polgara]

Aight.  I'll think about what you've said, since you are more knowledgeable than I am.