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

struct Node {
    int left;
    int right;
    bool flag;
    Node() : left(-1), right(-1), flag(true) {}
    Node(int l, int r) : left(l), right(r), flag(true) {}
};

bool solve(string &s) {
    vector<int> pstack, sstack;
    vector<Node> nodes(s.size());
    int temp;
    for (int i = 0; i < s.size(); i++) {
        nodes[i].left = i > 0 ? i - 1 : -1;
        nodes[i].right = i < s.size() - 1 ? i + 1 : -1;
        nodes[i].flag = true;
        if (s[i] == '(') {
            pstack.push_back(i);
        } else if (s[i] == '*') {
            sstack.push_back(i);
        } else if (s[i] == ')') {
            if (pstack.size() > 0) {
                temp = pstack.back();
                pstack.pop_back();
            } else if (sstack.size() > 0) {
                temp = sstack.back();
                sstack.pop_back();
            } else {
                return false;
            }
            nodes[temp].flag = false;
            nodes[i].flag = false;
            if (nodes[temp].left >= 0) {
                nodes[nodes[temp].left].right = nodes[temp].right;
            }
            if (nodes[temp].right >= 0) {
                nodes[nodes[temp].right].left = nodes[temp].left;
            }
            if (nodes[i].left >= 0) {
                nodes[nodes[i].left].right = nodes[i].right;
            }
            if (nodes[i].right >= 0) {
                nodes[nodes[i].right].left = nodes[i].left;
            }
        }
    }
    for (int i = s.size() - 1; i >= 0; i--) {
        if (!nodes[i].flag) {
            continue;
        }
        if (s[i] == '(') {
            return false;
        }
        if (s[i] == '*' && pstack.size() > 0) {
            temp = pstack.back();
            pstack.pop_back();
            nodes[temp].flag = false;
            nodes[i].flag = false;
            if (nodes[temp].left >= 0) {
                nodes[nodes[temp].left].right = nodes[temp].right;
            }
            if (nodes[temp].right >= 0) {
                nodes[nodes[temp].right].left = nodes[temp].left;
            }
            if (nodes[i].left >= 0) {
                nodes[nodes[i].left].right = nodes[i].right;
            }
            if (nodes[i].right >= 0) {
                nodes[nodes[i].right].left = nodes[i].left;
            }
        }
    }

    return true;
}

int main(void) {
    string in = "*(*()";
    cout << solve(in) << endl;
    return 0;
}