Ad:

C++ Discussion Thread
Marked Solved
Views: 1073

Page 1
2
Next

You are currently viewing page 1 of this multi-page discussion thread

Dec 5th, 2008

stacks problem

Expand Post »

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

Similar Threads

kyosuke0

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

20 posts
since Sep 2008

Permalink

Dec 5th, 2008

Re: stacks problem

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

Freaky_Chris

Reputation Points: 325

Solved Threads: 118

Master Poster

Offline

702 posts
since Apr 2008

Permalink

Dec 5th, 2008

Re: stacks problem

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 ).

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.

StuXYZ

Reputation Points: 732

Solved Threads: 134

Practically a Master Poster

Offline

659 posts
since Nov 2008

Permalink

Dec 5th, 2008

Re: stacks problem

Click to Expand / Collapse Quote 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 ).
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

Freaky_Chris

Reputation Points: 325

Solved Threads: 118

Master Poster

Offline

702 posts
since Apr 2008

Permalink

Dec 5th, 2008

Re: stacks problem

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.

Ahmed_I

Reputation Points: 14

Solved Threads: 1

Light Poster

Offline

32 posts
since Nov 2008

Permalink

Dec 5th, 2008

Re: stacks problem

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

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

kyosuke0

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

20 posts
since Sep 2008

Permalink

Dec 6th, 2008

Re: stacks problem

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

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.

kyosuke0

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

20 posts
since Sep 2008

Permalink

Dec 6th, 2008

Re: stacks problem

Not too basd, the reason is this code here

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

Freaky_Chris

Reputation Points: 325

Solved Threads: 118

Master Poster

Offline

702 posts
since Apr 2008

Permalink

Dec 6th, 2008

Re: stacks problem

i understand, i will make the corrections and try agin

thank you very mutch

kyosuke0

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

20 posts
since Sep 2008

Permalink

Dec 6th, 2008

Re: stacks problem

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

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;
	}
}

other than that everything else works fine

kyosuke0

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

20 posts
since Sep 2008

Page 1
2
Next

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Quick sort and merge sort together using both vectors and arrays.

Next Thread in C++ Forum Timeline: Free C++ IDE for Windows XP

DaniWeb Message

Cancel Changes

User Name
Password