Categories: MSDN / DotNet / Java / Scripts / Linux / PHP Ask - La ask - La Answer
Programmers Tech >> Developer Tech >> C++

Help - Stacks

I'm taking a class and need some help. The book doesn't cover this area well. Can anyone help me with some code for this problem: I need to determine whether the parentheses in an expression are correctly balanced. That means that each left-facing parentheses is matched by a right-facing parentheses. For example, if using this string (a+b) / (c+d), each character starting from the left is eamined.

I know this may be a little vague, my email is CHIEFLFO@HOTMAIL.COM. If you can assist me, I can send you more info.

Thanks a lot

Chief
[579 byte] By [chief] at [2007-11-11 8:01:29]
«« Fixed characters in the TextBox?
»» Refresh the Servlet
# 1 Re: Help - Stacks
Hi,
if you only need to check whether the parenthesis are properly balanced, then do the
following:
initialze an
int couner = 0;

loop through the string. every time you encounter an opening bracket - increment the counter, every time you encounter a closing bracket decrement the counter.
if your counter is smaller than 0 at any time your brackets are inbalanced. when you have processed the whole string, your counter should be 0 if the brackets are balanced.

This is a 10 lines max code and I leave it for you as an excercise ;-)

Cheers,

D
drkybelk at 2007-11-11 21:01:45 >
# 2 Re: Help - Stacks
Hi,
on second thought: it is not much more difficult to use stacks either.
create an empty stack
if you encounter a '(' push it onto the stack, if you find a ')' pop one off the stack if possible. if you can't pop -> the brackets are inbalanced. at the end your stack must be empty for well balanced expressions.
again: 10 lines or so, if you use STL...

D
drkybelk at 2007-11-11 21:02:39 >
# 3 Re: Help - Stacks
Thanks D,

Easier said than done. Reading the part about stacks, I think I understand how the stacks work and the examples shown all deal with names, one on top of the other. Where I'm stuck is on how does each character in the string get examined, starting from the left. What you said on your second reply is what I have to do. If it's a left-facing parentheses, it gets pushed onto the stack, and if it's a right-facing parentheses, the top stack element is popped

Chief
chief at 2007-11-11 21:03:44 >
# 4 Re: Help - Stacks
Hi,

stack<char> charStack;
for(i=0; i<sizeOfYourString;i++)
{
if(yourString[i] == ')')
charStack.push('(');
else if(yourString[i] == '(')
charStack.pop();
...
}

I leave you to fill in the bits and debug...

D

}
drkybelk at 2007-11-11 21:04:44 >
# 5 Re: Help - Stacks
Thanks D.

Chief
chief at 2007-11-11 21:05:49 >
Developer Tech
C++

Developer Tech

All Classified

Developer Tech New Topic

Developer Tech Hot Topic