I how to "count" parathesis without counting?????????????????

[imported_vr6]

Here is the exact problem from my lab..

4)Create several stacks with a combo of parathesis.

Ex:

combo1--------------------------( ( ) ) )---------------------no
combo2--------------------------( ( ) )-----------------------YES
combo3--------------------------( ( ( ( ) ) )-----------------no

Create the function which will check the entire array to see if it has equal amount of parathesis!! (( )) = TRUE!! (( ) = FALSE (LIKE IN MATH PROBLEMS!!). YOU ARE NOT TO COUNT THE ( )¡¦S!!!

**************************************
SO how is that done? how can you check to see if they have equal amount of parathesis without using a counter for each type of parathesis?
I also thought about using a modulus-- % but that would only tell me if there are odd or even number of parens, not if they are pairs or not..

 

[Descartes]

if (lengthOfExpression % 2 != 0) // equal amount

?

 

[itzlvx]

This is the same kind of question as "Balanced parenthesis"

Reading the array and using a stack. Push into the stack whenever you have "(". When you have a ")" pop from the stack a "(" if you cant pop a "(" its a no. When your done going through the array, and nothing is left in the stack then result is YES, else if theres something left inside its a NO.

 

[GtPrOjEcTX]

hmm....this would depend largely on his definition of counting the parenthesis.

how about incrementing a counter for every ( found and decrementing it for every ) found. if not zero at the end then false, otherwise true.

edit....ah! didn't read the initial problem stating to use stacks. the answer above mine is correct.

 

[Descartes]

Originally posted by: itzlvx
This is the same kind of question as "Balanced parenthesis"

Reading the array and using a stack. Push into the stack whenever you have "(". When you have a ")" pop from the stack a "(" if you cant pop a "(" its a no. When your done going through the array, and nothing is left in the stack then result is YES, else if theres something left inside its a NO.

I didn't read where he said he had to use a stack (although I see he has another thread on using a stack), so how would this be any better than the following?

char expression[] = "(())";
if (strlen(expression) % 2 != 0)
// unequal

[edit]Nevermind. Your response accommodated arbitrary expressions that include parens, but I was thinking the OP had an expression of *only* parens.[/edit]

 

[GtPrOjEcTX]

Originally posted by: Descartes
I didn't read where he said he had to use a stack

4)Create several stacks with a combo of parathesis.

 

[imported_vr6]

ok here is what the chunk of code looks like.

.. in main
void main()
{
STACK<char>charStack(5);
charStack.push('(');
charStack.push(')');
charStack.push(')');
charStack.push(')');
charStack.push('(');

cout <<"\n\nThis is the charStack" << endl;
cout <<"-----------------------" << endl;
charStack.Display();
}

 

[juiio]

An alternative to using stacks (yes I know it is in the problem description) would be to use recursion. Start on the end and work your way in.

 

[imported_vr6]

So if i was to use another stack to "count" the paren stack, i would have to creat an overloaded operator=??

 

[juiio]

Kwan1, you're misunderstanding. His suggestion was to read through each character in the string. When you get to a (, push onto the stack. When you get to a ), pop off the stack.

If you get to a ) and there is nothing left on the stack to pop, then the parens are mismatched with too many ). If you get to the end of the string and there are more items on the stack, the parens are mismatched with too many (.

 

[Descartes]

Originally posted by: GtPrOjEcTX

Originally posted by: Descartes
I didn't read where he said he had to use a stack

4)Create several stacks with a combo of parathesis.

Well, color me a moron Carry on...

 

[glugglug]

fastest way w/o stacks:

bool checkParens(char *array) //assuming array is \0 terminated string of chars
{
int level = 0;
char curchar;
while(curchar = *(array++))
{
switch(curchar)
{
case '(': level++; break;
case ')':
if(--level < 0) return false; //make this just level-- if you don't care about mismatch, just quantity, i.e. if )( is ok.
break;
}
}
return (level==0);
}

of course I think you're supposed to use a stack...

 

[GtPrOjEcTX]

note: the above is the implementation of my suggestion a few posts up...which is not what the problem is asking for

 

[imported_vr6]

Kwan1, you're misunderstanding. His suggestion was to read through each character in the string. When you get to a (, push onto the stack. When you get to a ), pop off the stack.

If you get to a ) and there is nothing left on the stack to pop, then the parens are mismatched with too many ). If you get to the end of the string and there are more items on the stack, the parens are mismatched with too many (.

What do u mean each character in the string? The directions says to create a stack of parenthesis, then write a function to check it. So do u mean put the parenthesis in a string first, then read it into the stack?? I am a noob at this sorry if i am frustrating to you guys.

Thanks.

 

[GtPrOjEcTX]

The wording of this problem is horrible which is why we are responding the way we are....

several stacks and then function which will check the entire array is what was throwing me off. How do you get from the stack to the array? Just popping everything off into a char?

we thought you started out with an array "(()" and then using stacks to figure out if they were even.

so you're going to have a stack of just

(
(
(
)
)

for example. gotcha.

for those 3 combos, Descartes solution would work...if you pop all of them off, and do a length of, anything odd is going to be a no, anything even is going to be a yes. however if you could have a combo of (()))) it would still be even, but incorrectly giving a yes answer.

I would (pseudocode)

while stack.size > 0
   x = pop.stack
   if x = (
      push(x).stack1
   if x = )
      push(x).stack2

if stack1.size != stack2.size
   cout << "No"
else
   cout << "yes"

 

[kt]

Originally posted by: Kwan1

Kwan1, you're misunderstanding. His suggestion was to read through each character in the string. When you get to a (, push onto the stack. When you get to a ), pop off the stack.

If you get to a ) and there is nothing left on the stack to pop, then the parens are mismatched with too many ). If you get to the end of the string and there are more items on the stack, the parens are mismatched with too many (.

What do u mean each character in the string? The directions says to create a stack of parenthesis, then write a function to check it. So do u mean put the parenthesis in a string first, then read it into the stack?? I am a noob at this sorry if i am frustrating to you guys.

Thanks.

Seems like a stack of parenthesis has already been created for you in the main function. What these guys have been saying (I think) is traverse the stack of parenthesis (let's call this ORIGINAL). If you encounter a "(" push it into another stack (let's call this COUNTER) and if you encounter a ")" pop it out of the COUNTER stack.

If at the end the COUNTER stack is NOT empty, that means you have too many "(".
If you reach a ")" and the COUNTER stack IS empty, that means you have too many ")".
If have fully traversed ORIGINAL stack and the COUNTER stack IS empty, you have an even "(" and ")".

-edit-
The pseudo code posted above my post works too.

 

[imported_vr6]

well to help clear things up, the stack is implemented using an array. We wrote a STACK class which has an arrayptr, a size, and a top.

in header file.

private:
int size; //#of elements in stack
int top; //location of top element
T *stackPtr //pointer to the stack, T is the type, since we are using templates.

 

[imported_vr6]

while stack.size > 0
? x = pop.stack
? if x = (
???push(x).stack1
? if y = )
???push(x).stack2

if stack1.size != stack2.size
? cout << "No"
else
? cout << "yes"

what are the question marks??

edit- what is f x and f y?

 

[GtPrOjEcTX]

what browser are you using? they show up as blanks for me.

to get around the concatenation of the posting (they take the spaces out of the front) I used the null character (ASCII 255) instead of space. this usually shows up as a space. in your case, question marks.


btw, I just editted the post...I had the variable y in there when I was using x.
also for your edit edit- what is f x and f y?

that is if x, and the second is now if x as well.

 

[imported_vr6]

ok i got it. I am using crazybrowser, that is probably what caused it, heres what my function looks like. Thanks for all the help Gtprojectx, descartes, kt, and everybody else. I hope he doesn't consider this method "counting"


template<class T>
void STACK<T>::count(T &popValue)
{
STACK<char>char1(10);
STACK<char>char2(10);
while( !isEmpty() )
{
popValue = stackPtr[top];
if ( popValue == '(')
{
char1.push(popValue);
top = top - 1;
}
if( popValue == ')' )
{
char2.push(popValue);
top = top - 1;
}
}
if( char1.top == char2.top )
{
cout << "True" << endl;
}
if( char1.top != char2.top )
{
cout << "False" << endl;
}

}

edit-btw, how does one use the ascii character for blank space?

 

[GtPrOjEcTX]

edit-btw, how does one use the ascii character for blank space?

hold down alt, then keypad 255

 

[imported_vr6]

sweet thanks Gt!