Stacks - balanced parentheses

[gropedersen]

Hi all,

I am working on an assignment on creating a program that recognizes whether an expression has balanced parentheses or not. The program has to use ADT (Abstract Data Type) stacks.

The user should input all data in form of an algebraic expression, fx (a+b)/(d-e) or ((a+b). The program should then determine whether the parantheses in the expression are balanced.

I have written a program, ... and it works and gives the correct output. So why am I writing?

Well, I would appreciate any opinion on the program. I just started learning about stacks so I am uncertain if I solved it the best way.

Here comes the entire code - and many thanks for your help.

#include <stdlib.h>
#include <iostream>
using std::cout;
using std::cin;
using std::endl;

const int maxstack = 100; 
typedef char stackitems; 


// ************ STRUCT STACK ****************
struct stack
{
    stackitems data[maxstack] ;   // array where data is stored 
    int stacktop ;  		      // when it is -1, stack is empty
};

stack s;


// ************ FUNCTION INITSTACK ****************
void initstack(stack & s) // empty the stack
{
    s.stacktop = -1; // set stacktop to be empty
}


// ************ FUNCTION ISEMPTY ****************
bool isEmpty(const stack& s) // returns true or false
{
    return s.stacktop==-1; // function is true if stacktop has value of -1 
}

	
// ************ FUNCTION POP ****************
void pop ( stack & s, stackitems & x) // removes the top item
{
    if (isEmpty(s))   				// if stack is empty, cannot remove data
	  {
		cout << "Stack underflow"<<endl;
		exit(1); //terminate the program
	}
	else
	{
		x = s.data[s.stacktop];    // retrieve data first
		s.stacktop--;		       // remove from stacktop
		cout << "Has popped data '" << x << "' from stack.\n"; // display info to the user
	}
}

// ************ FUNCTION PUSH ****************
void push( stack & s, const stackitems & x)
// places element x on the stack
{
     if (s.stacktop == maxstack -1)   // not more than maxstack-1 is allowed
     { 
		cout<<"Stack overflow";  // items on the stack.
		exit(1); //terminate the program
      }  
    else
    {
		s.stacktop++;			 // move the top of the stack up
		s.data[s.stacktop] = x;  // add new item,x
		cout << "Has added data '" << x << "' to stack.\n"; // display message to the user 
    }
}

// ************ FUNCTION TOP ****************
stackitems top(const stack& s)
//returns the top item from the stack in parameter x
{
     if (isEmpty(s))
   {  
		cout<<"Stack underflow"<<endl;
		exit(1);
    }
    else
		return  s.data[s.stacktop] ;
}

// ************ FUNCTION CHECK ****************
void check()
{    
    const char leftparen = '(';
    const char rightparen = ')';

    bool error = false; 
    char ch;
	
	cout << "Please enter an algebraic expression: ";
	cin.get(ch);

	while (( ch != '\n')  && (!error) )
    {
		if (ch == leftparen)
			 push(s,ch);
		if (ch == rightparen)
			if (isEmpty(s))
				error = true;
			else
				pop(s,ch);
			cin.get(ch);
	}
	if ((!error) && isEmpty(s))
		cout<<"\nResult: This expression is valid. \n"<<endl;
	else
		cout <<"\nResult: This expression is invalid. \n"<<endl;
}

// ************ FUNCTION MAIN ****************
void main ()
{
    initstack(s);  // initialising stack to -1; i.e. it is empty 
	check();

} // end main

[orko]

if (isEmpty(s))                 // if stack is empty, cannot remove data
  {
    cout << "Stack underflow"<<endl;
    exit(1); //terminate the program
}

You can write:

if (isEmpty(s))                 // if stack is empty, cannot remove data
  {
    throw invalid_argument("Stack Underflow");
}

same in push(), top() and other functions.
then the main() should be:

void main ()
{
try {
    initstack(s);  // initialising stack to -1; i.e. it is empty 
    check();
  }
catch (exception &e) {
    cout << "\nException <" << e.what() << "> occurred.\n";
  }
}

this is just another way of writing.... nothing else.

and instead of array, isn't it possible to use array by calling pointer first.... thus u can fix the array size later..... n u can set a default size in case.
i m also learning these stuffs this sem.... nice to share with u.... cheers.

[iamthwee]

>I just started learning about stacks so I am uncertain if I solved it the best way.

It depends what your definition of best way is. If this is an assignment it will probably suffice.

Personally, I would have used classes instead of structs. Does it really matter? Probably not, just preference here.

Also, you could have designed your stack using templates instead. The advantage for doing this means that you can declare a stack of a generic type. Say a stack of strings, or integers. However, in your case, this criteria probably isn't important.

Just one other thing, void main, change that to int main.

[gropedersen]

Thanks for your help! I tried first to use classes but had problems making it work, so when struct worked out I was very happy for that...

Regarding the throw and try-catch commands, I want to learn more about this and be able to use it, I have tried but am not quite sure how this works. My textbook is written for experienced C++ users (or at least, that is my impression) and they don't go into much detail on the actual implementation and how you really use these and other commands.
Quote from textbook: "Usually, the C++ exception class exception (...) is used as the base class for the exception. (..) You will need to use the std namespace if you base your class on the C++ exception class exception. " (Carrano & Prichard, Data Abstraction and Problem Solving with C++, p. 152).

So - what does this mean? Do I use #include <exception> and then using std::...? Can anyone help?

[Lerner]

The throw/catch stuff is nice, and eventually you should learn how to use it, but for now I'd concentrate on the use of stacks and use of classes/structs (the only difference between classes and structs in C++ is that struct members have public access by default whereas class members have private access by default). Your functions to manipulate and interrogate stacks seem logical from what I can tell, but I would suggest you learn about member functions instead of stand alone function to do the manipulation. In particular I would suggest you replace your current functions with functions that are members of the stack struct (don't erase your current functions, the function bodies will be the same, it's just how you declare them and the syntax for defining them outside the interface that's different). I would also suggest you learn about data access by making the member variables private rather than public and how to use public accessor and mutator functions to access and manipulate the data. Learning how to write operators that allow you to write/read from screen/file, copy one object to another, use dynamic memory to declare size of stack on the fly, compare one struct object to another, assign one struct object to another, etc. would all be cool and very educational. I'd also suggest you learn how to put the interface into a header file and the implementation into a cpp file. You could even consider implementing a template version of the stack class. After all that then I'd toss throw/catch stuff to assist validating data entry and allowing user to expeditiously correct data entry mistakes without turning off or crashing program for a truly modern milly version of your current program.

In other words you've got a good start and seem to understand what to do with stacks in general, now learn how to leverage that knowledge in the spirit of C++ having fun along the way!