DaniWeb Forum Index > Software Development > C++

C++ RSS

stacks problem

Please support our C++ advertiser: Intel Parallel Studio Home

Thread Solved

•

Join Date: Sep 2008

Posts: 20

Reputation: kyosuke0 is an unknown quantity at this point

Solved Threads: 0

kyosuke0

Offline

Newbie Poster

stacks problem

Dec 5th, 2008

the program i have to write involves a dynamically linked stack to evaluate if the grouping symbols '(' , ')' , '{' , '}' , '[' , ']' in expressions are balanced. The expression is input through keyboard.

For example:
expression: {A+(B-C)*D} is balanced
expression: T+{(R+M)/G-V*L is not balanced
expression: )A( is not balanced
expression: (A) is balanced

I do not have to do anything to the variables and operators but just determine if the grouping symbols are balanced. The stipulations are that i have to use a stack and that i can not use a counter to simply count the number of grouping symbols because that would evaluate )A( as balanced.

what iv come up with so far is to take the input as a string, convert it to individual characters, input to a stack using a for loop with the length of the string as the cutout.

what i can't seem to figure out is how to evaluate if the expression is balanced using only the pop, push, and top functions allowed with stacks. The only thing i can come up with is a complicated nested if,switch, and while statements that i am only half sure will work so there must be a simpler way.

any help or point into the right direction is greatly appreciated

•

Join Date: Apr 2008

Posts: 671

Reputation: Freaky_Chris is a jewel in the rough

Solved Threads: 113

Freaky_Chris Freaky_Chris is offline

Offline

Practically a Master Poster

Re: stacks problem

Dec 5th, 2008

loop throught all the elements on the stack, check what it is either ()[]{} and use 3 different boolean values, 1 for each brace type ie 1 for () 1 for [] and 1 for {}. then toggle states...if that makes sense and if the state wouldn't chage then you know they are not balanced.

That was poorly worded i think sorry

Chris

Knowledge is power -- But experience is everything

•

Join Date: Nov 2008

Posts: 397

Reputation: StuXYZ is a glorious beacon of light

Solved Threads: 72

StuXYZ

Offline

Posting Whiz

Re: stacks problem

Dec 5th, 2008

This is easy.... Count
If you get below zero then you have failed,
and if you get not-zero at the end you have failed.
You might want to check scope bridges. I.e.
(a{b+c)} which I would pass as fail.
but that is easy to modify the code below to include.

Example of pseudo code for JUST ( and ).

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
string A = "(expession) with ) ( ";
int b(0);
for(int i=0;i<A.length();i++)
 {
   if (A[i]=='(') b++;
   if (A[i]==')') 
     {
       b--;
       if (b<0) failed();
     }
} 
 
if (b!=0) failed();
success();
string A = "(expession) with ) ( ";
int b(0);
for(int i=0;i<A.length();i++)
 {
   if (A[i]=='(') b++;
   if (A[i]==')') 
     {
       b--;
       if (b<0) failed();
     }
} 

if (b!=0) failed();
success();

[/code]

Additionally, I am sorry BUT you cannot use boolean values as suggested by freaky_chris since
the expression ((x+y)) would fail. And that is not acceptable.

Last edited by StuXYZ; Dec 5th, 2008 at 6:30 pm. Reason: added comment on freaky_chris's quicker comment.

•

Join Date: Apr 2008

Posts: 671

Reputation: Freaky_Chris is a jewel in the rough

Solved Threads: 113

Freaky_Chris Freaky_Chris is offline

Offline

Practically a Master Poster

Re: stacks problem

Dec 5th, 2008

•

Originally Posted by StuXYZ

This is easy.... Count
If you get below zero then you have failed,
and if you get not-zero at the end you have failed.
You might want to check scope bridges. I.e.
(a{b+c)} which I would pass as fail.
but that is easy to modify the code below to include.

Example of pseudo code for JUST ( and ).
Help with Code Tags

c++ Syntax (Toggle Plain Text)
string A = "(expession) with ) ( ";
int b(0);
for(int i=0;i<A.length();i++)
 {
   if (A[i]=='(') b++;
   if (A[i]==')') 
     {
       b--;
       if (b<0) failed();
     }
} 
 
if (b!=0) failed();
success();
string A = "(expession) with ) ( "; int b(0); for(int i=0;i<A.length();i++) { if (A[i]=='(') b++; if (A[i]==')') { b--; if (b<0) failed(); } } if (b!=0) failed(); success();
[/code]

Additionally, I am sorry BUT you cannot use boolean values as suggested by freaky_chris since
the expression ((x+y)) would fail. And that is not acceptable.

ooh, valid point. I hadn't though about that one i do apologise...
Chris

Knowledge is power -- But experience is everything

•

Join Date: Nov 2008

Posts: 32

Reputation: Ahmed_I is an unknown quantity at this point

Solved Threads: 1

Ahmed_I

Offline

Light Poster

Re: stacks problem

Dec 5th, 2008

You can traverse through the string using a pointer ofcourse :-
-if u find any open braces (and i mean OPEN ' (,{,[ ') Push it to the stack.
-While u still traversing the expression if u find any CLOSED braces(and i mean Closed ' ) , } , ]' Pop the stack and compare the popped element with the closed brace u found if it is correct then the expression is balanced if it doesn't then it is invalid expression.

Note :- I think that is the way that some compilers check for the syntax errors that occur because the braces.

•

Join Date: Sep 2008

Posts: 20

Reputation: kyosuke0 is an unknown quantity at this point

Solved Threads: 0

kyosuke0

Offline

Newbie Poster

Re: stacks problem

Dec 5th, 2008

thanks everyone i will put everything together and see if it works

Last edited by kyosuke0; Dec 5th, 2008 at 7:39 pm.

•

Join Date: Sep 2008

Posts: 20

Reputation: kyosuke0 is an unknown quantity at this point

Solved Threads: 0

kyosuke0

Offline

Newbie Poster

Re: stacks problem

Dec 6th, 2008

so i got it kinda working in the sense that no matter what is input the program evaluates the expression as unbalanced here is the code

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
void eval()
{
	string exp;
	int num;
	linkedStackType<char>stack;
 
 
	cout << endl << "Input evaluation: ";
	cin >> exp;
	cout << endl << exp;
	num = exp.length();
 
	for(int x=0; x<num; x++)
	{
		if(exp[x] == '(' || exp[x] == '{' || exp[x] == '[')
		{
			stack.push(exp[x]);
		}
		else if(exp[x] == ')' || exp[x] == '}' || exp[x] == ']')
		{
			if(exp[x] == stack.top())
			{
				stack.pop();
			}
		}
	}
 
	if(stack.isEmptyStack())
	{
		cout << endl << "is balanced" << endl << endl;
	}
	else
	{
		cout << endl << "is not balanced" << endl << endl;
	}
}
void eval()
{
	string exp;
	int num;
	linkedStackType<char>stack;
	
	
	cout << endl << "Input evaluation: ";
	cin >> exp;
	cout << endl << exp;
	num = exp.length();
	
	for(int x=0; x<num; x++)
	{
		if(exp[x] == '(' || exp[x] == '{' || exp[x] == '[')
		{
			stack.push(exp[x]);
		}
		else if(exp[x] == ')' || exp[x] == '}' || exp[x] == ']')
		{
			if(exp[x] == stack.top())
			{
				stack.pop();
			}
		}
	}
	
	if(stack.isEmptyStack())
	{
		cout << endl << "is balanced" << endl << endl;
	}
	else
	{
		cout << endl << "is not balanced" << endl << endl;
	}
}

this is the function definition and you can assume that the member functions to the stack class are all correct with the "isEmptyStack" returning a value of true if the stack is empty.

any help is appriciated

Last edited by kyosuke0; Dec 6th, 2008 at 3:40 am.

•

Join Date: Apr 2008

Posts: 671

Reputation: Freaky_Chris is a jewel in the rough

Solved Threads: 113

Freaky_Chris Freaky_Chris is offline

Offline

Practically a Master Poster

Re: stacks problem

Dec 6th, 2008

Not too basd, the reason is this code here

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
if(exp[x] == stack.top())
{
	stack.pop();
}
if(exp[x] == stack.top())
{
	stack.pop();
}

This should be a comparison to the opposite of stack.top() for example you are comparing like this -> ']' == '[' which will never be true. You will need to check that the brace type is the same and is opposite to the one of the top of the stack, if thats true then pop. if it isn't true, then break out of your loop since it is unbalanced.

Chris

Knowledge is power -- But experience is everything

•

Join Date: Sep 2008

Posts: 20

Reputation: kyosuke0 is an unknown quantity at this point

Solved Threads: 0

kyosuke0

Offline

Newbie Poster

Re: stacks problem

Dec 6th, 2008

i understand, i will make the corrections and try agin

thank you very mutch

•

Join Date: Sep 2008

Posts: 20

Reputation: kyosuke0 is an unknown quantity at this point

Solved Threads: 0

kyosuke0

Offline

Newbie Poster

Re: stacks problem

#10

Dec 6th, 2008

now whenever an expression that starts with a close group symbol it asserts an error at "else if(exp[x] == '}')" for all close group symbols.

it does this for expressions like:
)A(
AEW}de{

here is the updated code

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
void eval()
{
	string exp;
	int num;
	linkedStackType<char>stack;
 
 
	cout << endl << "Input evaluation: ";
	cin >> exp;
	cout << endl << exp;
	num = exp.length();
 
	for(int x=0; x<num; x++)
	{
		if(exp[x] == '(' || exp[x] == '{' || exp[x] == '[')
		{
			stack.push(exp[x]);
		}
		else if(exp[x] == ')' || exp[x] == '}' || exp[x] == ']')
		{
			if(exp[x] == ')')
			{
				if(stack.top()=='(')
                                {
                                      stack.pop();
                                }
                        }
                        else if(exp[x] == '}')
                        {
                                if(stack.top()=='{')
                                {
                                      stack.pop();
                                }
                        }
                         else if(exp[x]==']')
                         {
                                if(stack.top()=='[')
                                {
                                      stack.pop();
                                }
			}
		}
	}
 
	if(stack.isEmptyStack())
	{
		cout << endl << "is balanced" << endl << endl;
	}
	else
	{
		cout << endl << "is not balanced" << endl << endl;
	}
}
void eval()
{
	string exp;
	int num;
	linkedStackType<char>stack;
	
	
	cout << endl << "Input evaluation: ";
	cin >> exp;
	cout << endl << exp;
	num = exp.length();
	
	for(int x=0; x<num; x++)
	{
		if(exp[x] == '(' || exp[x] == '{' || exp[x] == '[')
		{
			stack.push(exp[x]);
		}
		else if(exp[x] == ')' || exp[x] == '}' || exp[x] == ']')
		{
			if(exp[x] == ')')
			{
				if(stack.top()=='(')
                                {
                                      stack.pop();
                                }
                        }
                        else if(exp[x] == '}')
                        {
                                if(stack.top()=='{')
                                {
                                      stack.pop();
                                }
                        }
                         else if(exp[x]==']')
                         {
                                if(stack.top()=='[')
                                {
                                      stack.pop();
                                }
			}
		}
	}
	
	if(stack.isEmptyStack())
	{
		cout << endl << "is balanced" << endl << endl;
	}
	else
	{
		cout << endl << "is not balanced" << endl << endl;
	}
}