#include <iostream>
#include <string>

using namespace std;

class RuntimeException{                                         // generic run-time exception for empty stack
private:
    string errorMsg;
public:
    RuntimeException(const string& err) {errorMsg = err;}
    string getMessage() const {return errorMsg;}
};

class StackEmpty:public RuntimeException{                       // empty stack
public:
    StackEmpty(const string& err):RuntimeException(err){}
};

class Snode{                                                    // Singly Linked List Node
public:
    char elem;                                                  // Linked list element value
    Snode *next;                                                //next item in the list
    friend class SLinkedList;                                   // provide SLinkedList access
};

class SLinkedList{                                              // Singly Linked List
public:
    SLinkedList();                                              // empty list constructor
    ~SLinkedList();                                             //destructor
    bool empty() const;                                         //is list empty?
    const char& front() const;                                  //return front element
    void addFront(const char& e);                               // add to front of list
    void removeFront();                                         //remove front item from list
    friend class LinkedStack;                                   // give LinkedStack access
private:
    Snode *head;                                                // head of list
};

Snode *head;

SLinkedList::SLinkedList()                                      // constructor
:head(NULL) {}

bool SLinkedList::empty() const{                                // is list empty?
    return head == NULL;}

const char& SLinkedList::front() const{                         // return front element
    return head-> elem;}

SLinkedList::~SLinkedList(){                                    // destructor
    while(!empty()) removeFront();}

void SLinkedList::addFront(const char& e){                      // add to front of list
    Snode *v = new Snode;                                       // create a new node
    v-> elem = e;                                               // store data
    v-> next = head;                                            // head now follows v
    head = v;                                                   // v is now head
}

void SLinkedList::removeFront(){                                // remove front item
    Snode *old = head;                                          // save the current head
    head = old-> next;                                          // skip over old head
    delete old;                                                 // delete old head
}

class LinkedStack{                                              // create stack element
public:
    LinkedStack();                                              // constructor
    int size() const;                                           // number of items in stack
    bool empty() const;                                         // is stack empty?
    const char& top() const throw(StackEmpty);                  // top element
    void push(const char& e);                                   // push element onto stack
    void pop() throw(StackEmpty);                               // pop the stack
private:
    SLinkedList S;                                              // linked list of elements
    int n;                                                      // number of elements
};

LinkedStack::LinkedStack()                                      // constructor
: S(), n(0) {}

int LinkedStack::size() const{                                  // number of items in the stack
    return n;}

bool LinkedStack::empty() const{                                // is stack empty?
    return n == 0;}

const char& LinkedStack::top() const throw(StackEmpty){         // get the top element
    if(empty()) throw StackEmpty("Top of empty stack");
    return S.front();
}

void LinkedStack::push(const char& e){                          // push element onto stack
    ++n;
    S.addFront(e);
}

void LinkedStack::pop() throw(StackEmpty){                      // push element onto stack
    if(empty()) throw StackEmpty("Pop from empty stack");
    --n;
    S.removeFront();
}

bool ArePair(char opening,char closing)                         // check for matching type
{
    if(opening == '(' && closing == ')') return true;
    else if(opening == '{' && closing == '}') return true;
    else if(opening == '[' && closing == ']') return true;
    return false;
}

bool ParenMatch(string e){                                      // check for matching openings and closings
    
    LinkedStack P;
    for(int i = 0; i < e.length(); i++)
    {
        if(e[i] == '(' || e[i] == '{' || e[i] == '[')
            P.push(e[i]);
        else if(e[i] == ')' || e[i] == '}' || e[i] == ']')
        {
            if(P.empty() || !ArePair(P.top(),e[i]))
                return false;
            P.pop();
        }
    }
    if (P.empty())
        return true;
    else
        return false;
}

int main()
{
    string expression;
    
    cout << "Enter an expression:  ";
    cin >> expression;
    
    LinkedStack Paren;
    
    if(ParenMatch(expression))
        cout << "Balanced\n";
    else
        cout << "Not Balanced\n";
    
    return 0;
}