#include<iostream>
#include<string>
using namespace std;

#define MAX_SIZE 50

class Stack
{
    char a[MAX_SIZE];
    int top;

    public:
    Stack() { top = 0; }

    void push(char x)
    {
        if (top >= MAX_SIZE)
            return;
        a[top] = x;
        top += 1;
    }

    char pop()
    {
        if (top <= 0)
            return -1;
        char x = a[top - 1];
        a[top - 1] = 0;
        top -= 1;
        return x;
    }

    void print()
    {
        for(int i = 0; i < top; i++)
            cout << a[i] << "\n";
    }

    bool empty() { return top == 0; }

    bool full() { return top == MAX_SIZE; }
};

int main()
{
    string exp;
    Stack s;
    cout << "Enter expression to test: ";
    cin >> exp;
    int len = exp.length();
    for(int i = 0; i < len; i++)
    {
        char ch = exp[i];
        if(ch == '(' || ch == '[' || ch == '{' || ch == '<')
            s.push(ch);
        else if (ch == ')')
        {
            if (s.empty())
            {
                cout << "Invalid expression.";
                return 0;
            }
            char check = s.pop();
            if (check != '(')
            {
                cout << "Invalid expression.";
                return 0;
            }
        }
        else if (ch == ']')
        {
            if (s.empty())
            {
                cout << "Invalid expression.";
                return 0;
            }
            char check = s.pop();
            if (check != '[')
            {
                cout << "Invalid expression.";
                return 0;
            }
        }
        else if (ch == '>')
        {
            if (s.empty())
            {
                cout << "Invalid expression.";
                return 0;
            }
            char check = s.pop();
            if (check != '<')
            {
                cout << "Invalid expression.";
                return 0;
            }
        }
        else if (ch == '}')
        {
            if (s.empty())
            {
                cout << "Invalid expression.";
                return 0;
            }
            char check = s.pop();
            if (check != '{')
            {
                cout << "Invalid expression.";
                return 0;
            }
        }
    }
    if (!s.empty())
        cout << "Invalid expression.";
    else
        cout << "Valid expression.";
    return 0;
}