09

// main.cpp
#include<iostream>
using namespace std;
#define shift(x) x = x->next
class linklist;
class node{
private:
	char data;
	node *next;
public:
	node():data(0), next(0){};
	node(char x):data(x), next(0){};

	friend class linklist;
};
class linklist{
private:
	node *first;
public:
	linklist():first(0){};
	void push(char x);
	void pop();
	char top();
	bool empty();
};
void linklist::push(char x){
	node *newnode = new node(x);
	newnode->next = first;
	first = newnode;
}
void linklist::pop(){
	if (first){
		shift(first);
	}
}
char linklist::top(){
	//cout << first->data;
	return first->data;
}
bool linklist::empty(){
	return !first;
}
bool solve(string s){
	linklist l1;
	for (char x : s){

		if (x == '(') l1.push(x);
		else if (!l1.empty() && x == ')') l1.pop();
		else if (x == ')') return 0;
	}
	return l1.empty();
}
int main(){
	string s;
	while (1){
		cout << "Enter your expression: ";
		if (cin >> s && s != "EOF"){
			cout << s << endl;
			cout << (solve(s)? "Balanced Parentheses":"Error!! Left parentheses have no matching right parentheses");
			cout << endl;
		}else break;
	}
}