stacks problem

[kyosuke0]

the program i have to write involves a dynamically linked stack to evaluate if the grouping symbols '(' , ')' , '{' , '}' , '[[/B]' , '[B]]' 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

[Freaky_Chris]

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

[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.
icode}[/icode] which I would pass as fail.
but that is easy to modify the code below to include.

Example of pseudo code for JUST ( and ).

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();

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.

[Freaky_Chris]

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

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();

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

[Ahmed_I]

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.

[kyosuke0]

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

[kyosuke0]

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

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

[Freaky_Chris]

Not too basd, the reason is this code here

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

[kyosuke0]

i understand, i will make the corrections and try agin

thank you very mutch

[kyosuke0]

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

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

[Freaky_Chris]

Thats because the stack will be empty so you need to check stack.isEmptyStack(), if its empty break out because its unbalanced, if its not empty continue on and check.

Chris

[kyosuke0]

nvm i figured it out

thanks for the help everyone