#include <iostream>
using namespace std;
class Stack
{
private:
    int size_;
    int top;
    int* S;
public:
    Stack(int size_);
    ~Stack();
    void push(int x);
    int isFull();
    void display();
    int peek(int index);
    int stackTop();
    int isEmpty();
    int pop();
};
int Stack::pop()
{
    int x = 1;
    if(isEmpty())
    {
        cout<<"Stack UnderFLow"<<endl;
    }
    else
    {
        x = S[top];
        top--;
    }
    return x;
}
int Stack::isEmpty()
{
    if(top==-1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int Stack::stackTop()
{
    if(isEmpty())
    {
        return -1;
    }
    return S[top];
}
int Stack::peek(int index)
{
    int x= -1;
    if(top-index+1<0 || top-index+1 == size_)
    {
        cout<<"invalid position"<<endl;
    }
    else
    {
        x = S[top-index+1];
    }
    return x;
}
void Stack::display()
{
    for(int i = top; i>=0; i--)
    {
        cout<<S[i]<<"|" << flush;
    }
    cout<< endl;
}
Stack::Stack(int size_)
{
    this->size_ = size_;
    top = -1;
    S = new int[size_];
}
Stack::~Stack()
{
    delete[] S;
}
void Stack::push(int x)
{
    if(isFull())
    {
        cout << "Stack OverFlow" <<endl;
    }
    else
    {
        top++;
        S[top]=x;
    }
}
int Stack::isFull()
{
    if(top==size_-1)
    {
        return 1;
    }
    return 0;
}
int main()
{
    int A[] = {1, 3, 5, 7, 9};
    Stack stk(sizeof(A)/sizeof(A[0]));
    // Populate stack with array elements
    for (int i=0; i<sizeof(A)/sizeof(A[0]); i++)
    {
        stk.push(A[i]);
    }
    stk.push(11);
    cout << "Stack full: " << stk.isFull() << endl;

    // Display stack;
    cout << "Stack: " << flush;
    stk.display();


    // Peek
    cout << "Peek at 0th: " << stk.peek(0) << endl;
    cout << "Peek at 3th: " << stk.peek(3) << endl;
    cout << "Peek at 10th: " << stk.peek(10) << endl;

    // Top element
    cout << "Top element: " << stk.stackTop() << endl;

    // Pop out elements from stack
    cout << "Popped out elements: " << flush;
    for (int i=0; i<sizeof(A)/sizeof(A[0]); i++)
    {
        cout << stk.pop() << ", " << flush;
    }

     cout << endl;
     stk.pop();
     cout<<"Stack empty: " << stk.isEmpty() << endl;
     return 0;
}

#include <iostream>
using namespace std;
class Node
{
public:
    int data;
    Node* next;
};
class Stack
{
private:
    Node* top;
public:
    Stack();
    ~Stack();
    void push(int x);
    int peek(int index);
    int isEmpty();
    int stackTop();
    int isFull();
    int pop();
};
int Stack::pop()
{
    Node* p;
    int x = -1;
    if(top==nullptr)
    {
        cout << "Stack Underflow!" << endl;
    }
    else
    {
        p = top;
        x = p->data;
        top = top->next;
        delete p;
    }
    return x;
}
int Stack::isEmpty()
{
    if(top==nullptr)
        return 1;
    return 0;
}
Stack::peek(int index)
{
    if(isEmpty())
    {
        return -1;
    }
    else
    {
        Node* p =top;
        for(int i = 0; p!=nullptr&&i<index-1; i++)
        {
            p = p->next;
        }
        if (p!=nullptr)
        {
            return p->data;
        }
        else
        {
            return -1;
        }

    }
}
Stack::Stack()
{
    top = nullptr;
}
Stack::~Stack()
{
    Node* p = top;
    while(top)
    {
        top = top->next;
        delete p;
        p = top;
    }
}
void Stack::push(int x)
{
    Node* t = new Node;
    if(t==nullptr)
    {
        cout<<"Stack Overflow"<<endl;
    }
    else
    {
        t->data = x;
        t->next = top;
        top = t;
    }
}
int Stack::stackTop()
{
    if(top)
    {
        return top->data;
    }
    return -1;
}
int Stack::isFull()
{
    Node* t = new Node;
    int r=t?1:0;
    delete t;
    return r;
}
int main()
{
    int A[] = {1, 3, 5, 7, 9};
    Stack stk;
    // Populate stack with array elements
    for (int i=0; i<sizeof(A)/sizeof(A[0]); i++)
    {
        stk.push(A[i]);
    }
    cout << "Stack peek at 3rd: " << stk.peek(3) << endl;
    cout << "Stack peek at 10th: " << stk.peek(10) << endl;
    cout << "Stack top: " << stk.stackTop() << endl;
    cout << "Stack full: " << stk.isFull() << endl;
    cout << "Stack empty: " << stk.isEmpty() << endl;

    // Pop out elements from stack
    cout << "Popped: " << flush;
    for (int i=0; i<sizeof(A)/sizeof(A[0]); i++)
    {
        cout << stk.pop() << ", " << flush;
    }
    cout << endl;

    // Underflow
    cout << stk.pop() << endl;


    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
class Stack
{
private:
    int size_;
    int top_;
    char* S_;
public:
    Stack(int size_);
    ~Stack();
    int isEmpthy();
    int isFull();
    void push(char x);
    void pop();
};
void Stack::pop()
{
    if(isEmpthy())
    {
        cout<<"Stack underflow!"<<endl;
    }
    else
    {
        top_;;
    }
}
int Stack::isFull()
{
    if(top_==size_-1)
    {
      return 1;
    }

    return 0;
}
void Stack::push(char x)
{
    if(isFull())
    {
        cout<<"Stack OverFlow"<<endl;
    }
    else
    {
        top_++;
        S_[top_] = x;
    }

}

int Stack::isEmpthy()
{
    return (top_==-1)?1:0;
}
Stack::Stack(int size_)
{
    this->size_ = size_;
    top_ = -1;
    S_ = new char[size_];
}
Stack::~Stack()
{
    delete[] S_;
}
bool isBalance(char* exp)
{
    //create a stack
    Stack stk((int)strlen(exp)); // strlen is function that from cstring library
    // Process expression
    for(int i =0; i<strlen(exp);i++)
    {
        // found : pusth to stack
        if(exp[i]=='(')
        {
            stk.push(exp[i]);
        }
        else if(exp[i]==')')
        {
            // if stack is empthy : unbalanced expression
            if(stk.isEmpthy())
            {
                return false;
            }
            else
            {
                stk.pop();
            }
        }

    }
    return stk.isEmpthy()?true:false;

}
int main()
{
    char E[] = "((a+b)* (c-d))";
    cout<< isBalance(E)<<endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <map>
using namespace std;
class Stack
{
private:
    int size_;
    int top_;
    char* S_;
public:
    Stack(int size_);
    ~Stack();
    int isEmpthy();
    int isFull();
    void push(char x);
    void pop();
    char top();
};
char Stack::top()
{
    return S_[top_];
}
void Stack::pop()
{
    if(isEmpthy())
    {
        cout<<"Stack underflow!"<<endl;
    }
    else
    {
        top_;;
    }
}
int Stack::isFull()
{
    if(top_==size_-1)
        return 1;
    return 0;
}
void Stack::push(char x)
{
    if(isFull())
    {
        cout<<"Stack OverFlow"<<endl;
    }
    else
    {
        top_++;
        S_[top_] = x;
    }

}

int Stack::isEmpthy()
{
    return (top_==-1)?1:0;
}
Stack::Stack(int size_)
{
    this->size_ = size_;
    top_ = -1;
    S_ = new char[size_];
}
Stack::~Stack()
{
    delete[] S_;
}
bool isBalance(char* exp)
{
    //Create a Map
    map<char, char> mapping;
    mapping['}'] = '{';
    mapping[')'] = '(';
    mapping[']'] = '[';

    // Create map iterator
    map<char, char>::iterator itr;

    //Create a Stack
    Stack stk((int)strlen(exp));

    for(int i =0;i<(int)strlen(exp);i++)
    {
        if(exp[i]==' { ' || exp[i]==' ( ' || exp[i]== ' [ ')
        {
            stk.push(exp[i]);
        }
        else
        {
            char temp = stk.top();
            if(temp == itr->second)// itr->first is key, itr->second is value
            {
                stk.pop();
            }
            else
            {
                return false;
            }
        }
    }
    return stk.isEmpthy()?true:false;
}
int main()
{
    char E[] = "{([a+b]* [c-d])/e}";
    cout<< isBalance(E)<<endl;

    return 0;
}