string advance() {
    string s = token;
    if (!(cin >> token))
        token = "$";
    return s;
}
node *readE();
node *readP() {
    if (token == "(") {
        advance();
        node *cur = readE();
        advance();
        return cur;
    }
    return leaf(advance());
}
node *readF() {
    node *cur = readP();
    if (token == "^")
        cur = new node(advance(), cur, readP());
    return cur;
}
node *readT() {
    node *cur = readF();
    while (prio[token] == prio["*"])
        cur = new node(advance(), cur, readF());
    return cur;
}
node *readE() {
    node *cur = readT();
    while (prio[token] == prio["+"])
        cur = new node(advance(), cur, readT());
    return cur;
}