p215.ans1
======================
-1
-30
-1
0
4
6
0
0
0
14

=================
p215.in1
======================
print (80+4*75)/(56-2^ 2^ 3)
print 30/-1
print 31%-5
print 0^3
print 2+2
define 2 3
print 2+2
define 3 x
print 2+2
define x 2
print 2+2
define 2 5
print 2+2
define x 7
print 2+2

=================
statement.txt
======================
215. PL/Cool
time limit per test: 0.5 sec.
memory limit per test: 65536 KB
input: standard
output: standard



The new IMB compiler "Unvisual Age for PL/Cool" is planned for release next month. Your task in this problem is to write the interpreter for the PL/Cool language so that the compiler programmers could test their product.

Program on PL/Cool can contain expressions. Each expression can contain integer constants and variables. The following operations are allowed: + (add), - (substract), * (multiply), / (divide), % (modulo), and ^ (raise). ll operations have their usual meaning and priority (^) > (*) = (/) = (%) > (+) = (-), all operations except ^ are evaluated from left to right, ^ is evaluated from right to left. Parenthesis can be used to change the order of evaluation, as usually. Unary minus and plus are allowed, their priority in this case is the highest.

Divide operation acts like integer division: first both operands are replaced with their absolute values, next integer division is performed, remainder is dropped, and finally the sign of the quotient is set equal to the sign of the true quotient of the operands. Taking modulo is perfomed the same way, except that the quotient is dropped and remainder is kept. For example, (80+4*75)/(56-2^2^3) = -1.

Program may contain variables. Variable name starts with a letter, which may be followed by letters and digits. Variable names are case insensitive. Maximal name length is 10 characters.

PL/Cool has two operators: "print" and "define". Program is the sequence of the operators, one on a line.

Operator "print" has the following syntax:

print <expression>


Here <expression> is any expression that may contain variables and integer constants. Operator "print" prints the value of the expression.

Operator "define" has the following syntax:

define <operand1> <operand2>


Here <operand1> and <operand2> are either variables or non-negative integer constants. After execution of the "define" operator, all occurences of the <operand1> are replaced with the <operand2>. Define operator can be used even to change the value of the integer constants, for example after

define 2 4

the value of 2+2 is 8.

Note that substitution is performed recursively, until some undefined constant is met, for example the following sequence of operators prints 8 and 10:

define 2 4
define 3 2
print 3+3
define 4 5
print 3+3


An attempt to redefine some variable or constant is ignored. An attempt to make a definition that leads to circular dependence is also ignored. For example, the following sequence prints 4 and 4, because the last two definitions are ignored.

define 2 4
define 3 2
define 2 5
print 3
define 4 2
print 3


If some identifier is used in the expression that is not yet defined to be substituted by some integer constant, its value is set to zero. For example, the following operator prints 3:

print x + 3


Input

Input file contains the program on PL/Cool. All numbers in the expressions, including numbers that occur during expression evaluation, do not exceed 109 by their absolute value. The total number of "define" operators does not exceed 30000, the total number of "print" operators does not exceed 2000, the length of each line does not exceed 200 characters.

In case of division denominator is never zero, zero is not raised to zero power and power exponent is always non-negative.

Output

Output file must contain the output of all print operators in the order they are executed, one on a line.

Sample test(s)

Input
print (80+4*75)/(56-2^ 2^ 3)
print 30/-1
print 31%-5
print 0^3
print 2+2
define 2 3
print 2+2
define 3 x
print 2+2
define x 2
print 2+2
define 2 5
print 2+2
define x 7
print 2+2

Output
-1
-30
-1
0
4
6
0
0
0
14
Author:	Andrew Stankevich
Resource:	Petrozavodsk Summer Trainings 2003
Date:	2003-08-30

=================
p215.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

vector<string> lines;
map<string, string> parent;

string normalize(const string& s) {
    if(s.empty() || isdigit(s[0])) {
        return s;
    }
    string r = s;
    for(char& c: r) {
        c = tolower(c);
    }
    return r;
}

string find(const string& s) {
    auto it = parent.find(s);
    if(it == parent.end()) {
        return s;
    }
    return it->second = find(it->second);
}

int64_t resolve_token(const string& token) {
    string r = find(normalize(token));
    if(!r.empty() && isdigit(r[0])) {
        return stoll(r);
    }
    return 0;
}

int64_t power(int64_t base, int64_t exp) {
    bool neg = base < 0 && exp % 2 == 1;
    __int128 b = abs(base), result = 1;
    while(exp > 0) {
        if(exp & 1) {
            result *= b;
        }
        b *= b;
        exp >>= 1;
    }
    return neg ? -(int64_t)result : (int64_t)result;
}

int64_t custom_div(int64_t a, int64_t b) {
    int64_t sign = ((a >= 0) == (b >= 0)) ? 1 : -1;
    return sign * (abs(a) / abs(b));
}

int64_t custom_mod(int64_t a, int64_t b) {
    int64_t sign = ((a >= 0) == (b >= 0)) ? 1 : -1;
    int64_t rem = abs(a) % abs(b);
    return rem == 0 ? 0 : sign * rem;
}

struct Parser {
    const string& s;
    int pos;

    Parser(const string& str) : s(str), pos(0) {}

    void skip() {
        while(pos < (int)s.size() && s[pos] == ' ') {
            pos++;
        }
    }

    string read_token() {
        skip();
        if(pos >= (int)s.size()) {
            return "";
        }
        int start = pos;
        if(isdigit(s[pos])) {
            while(pos < (int)s.size() && isdigit(s[pos])) {
                pos++;
            }
        } else if(isalpha(s[pos])) {
            while(pos < (int)s.size() && isalnum(s[pos])) {
                pos++;
            }
        }
        return s.substr(start, pos - start);
    }

    int64_t parse_expr() {
        int64_t val = parse_term();
        while(true) {
            skip();
            if(pos < (int)s.size() && (s[pos] == '+' || s[pos] == '-')) {
                char op = s[pos++];
                int64_t r = parse_term();
                val = op == '+' ? val + r : val - r;
            } else {
                break;
            }
        }
        return val;
    }

    int64_t parse_term() {
        int64_t val = parse_power();
        while(true) {
            skip();
            if(pos < (int)s.size() &&
               (s[pos] == '*' || s[pos] == '/' || s[pos] == '%')) {
                char op = s[pos++];
                int64_t r = parse_power();
                if(op == '*') {
                    val *= r;
                } else if(op == '/') {
                    val = custom_div(val, r);
                } else {
                    val = custom_mod(val, r);
                }
            } else {
                break;
            }
        }
        return val;
    }

    int64_t parse_power() {
        int64_t val = parse_unary();
        skip();
        if(pos < (int)s.size() && s[pos] == '^') {
            pos++;
            return power(val, parse_power());
        }
        return val;
    }

    int64_t parse_unary() {
        skip();
        if(pos < (int)s.size() && s[pos] == '-') {
            pos++;
            return -parse_unary();
        }
        if(pos < (int)s.size() && s[pos] == '+') {
            pos++;
            return parse_unary();
        }
        return parse_atom();
    }

    int64_t parse_atom() {
        skip();
        if(pos < (int)s.size() && s[pos] == '(') {
            pos++;
            int64_t val = parse_expr();
            skip();
            if(pos < (int)s.size() && s[pos] == ')') {
                pos++;
            }
            return val;
        }
        return resolve_token(read_token());
    }
};

void read() {
    string line;
    while(getline(cin, line)) {
        lines.push_back(line);
    }
}

void solve() {
    // This is a fairly simple problem conceptually, but requires some parsing.
    // For the links of "define", we can use path compression.

    for(auto& line: lines) {
        int i = 0;
        while(i < (int)line.size() && line[i] == ' ') {
            i++;
        }
        if(line.compare(i, 5, "print") == 0) {
            string expr = line.substr(i + 5);
            Parser p(expr);
            cout << p.parse_expr() << "\n";
        } else if(line.compare(i, 6, "define") == 0) {
            string rest = line.substr(i + 6);
            istringstream iss(rest);
            string op1, op2;
            iss >> op1 >> op2;
            string a = normalize(op1), b = normalize(op2);
            if(!parent.count(a)) {
                string rb = find(b);
                if(rb != a) {
                    parent[a] = b;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
