思路与算法

按明确的优先级递归下降，把中缀表达式转换成后缀Token序列：表达式层处理加减、乘除层处理乘除，一元层处理负号，幂层递归处理右结合。随后用值栈逐项执行后缀操作；幂指数1..10直接有限次乘法，所有中间乘法先用128位核界。

正确性说明

每个语法层只消费该层能结合的运算，括号对子表达式递归，幂的右侧递归使其右结合。由表达式结构归纳，后缀序列与原式意义相同。后缀中每个算符位于其操作数之后，栈取出的顺序是先右后左；运算归纳保证每个栈值为相应子表达式精确值。除法使用向0截断，与本地约定一致。

复杂度

字符扫描与后缀构建O(L)，栈求值每个幂最多10次乘法，仍O(L)；初始化及空间O(L)，递归最深O(L)。用128位仅做中间安全检查，结果按声明域保存64位。

易错点

幂右结合，2^3^2是512；幂优先于一元负号，-2^2是-4。不能用浮点pow计算整数。多位数字必须整体识别，不能把除法误写成向负无穷取整。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Token {
    char op;
    ll value;
};
struct Parser {
    string s;
    size_t at = 0;
    bool powers;
    vector<Token> post;
    Parser(string text, bool allow) : s(text), powers(allow) {
    }
    void spaces() {
        while (at < s.size() && isspace((unsigned char)s[at]))
            ++at;
    }
    bool take(char c) {
        spaces();
        if (at < s.size() && s[at] == c) {
            ++at;
            return true;
        }
        return false;
    }
    void atom() {
        spaces();
        if (take('(')) {
            expr();
            if (!take(')'))
                throw 1;
            return;
        }
        if (at >= s.size() || !isdigit((unsigned char)s[at]))
            throw 1;
        ll x = 0;
        while (at < s.size() && isdigit((unsigned char)s[at])) {
            x = x * 10 + s[at++] - '0';
            if (x > 1000000000LL)
                throw 1;
        }
        post.push_back({'n', x});
    }
    void power() {
        atom();
        if (take('^')) {
            if (!powers)
                throw 1;
            unary();
            post.push_back({'^', 0});
        }
    }
    void unary() {
        if (take('-')) {
            unary();
            post.push_back({'~', 0});
        } else
            power();
    }
    void term() {
        unary();
        while (true) {
            if (take('*')) {
                unary();
                post.push_back({'*', 0});
            } else if (take('/')) {
                unary();
                post.push_back({'/', 0});
            } else
                break;
        }
    }
    void expr() {
        term();
        while (true) {
            if (take('+')) {
                term();
                post.push_back({'+', 0});
            } else if (take('-')) {
                term();
                post.push_back({'-', 0});
            } else
                break;
        }
    }
    ll run() {
        expr();
        spaces();
        if (at != s.size())
            throw 1;
        vector<ll> stack;
        auto checked = [](__int128 v) {
            if (v > 1000000000000LL || v < -1000000000000LL)
                throw 1;
            return (ll)v;
        };
        for (auto t : post) {
            if (t.op == 'n') {
                stack.push_back(t.value);
                continue;
            }
            if (t.op == '~') {
                if (stack.empty())
                    throw 1;
                stack.back() = -stack.back();
                continue;
            }
            if (stack.size() < 2)
                throw 1;
            ll b = stack.back();
            stack.pop_back();
            ll a = stack.back();
            stack.pop_back();
            ll v = 0;
            if (t.op == '+')
                v = checked((__int128)a + b);
            else if (t.op == '-')
                v = checked((__int128)a - b);
            else if (t.op == '*')
                v = checked((__int128)a * b);
            else if (t.op == '/') {
                if (!b)
                    throw 1;
                v = a / b;
            } else {
                if (b < 1 || b > 10)
                    throw 1;
                v = 1;
                while (b--)
                    v = checked((__int128)v * a);
            }
            stack.push_back(v);
        }
        if (stack.size() != 1)
            throw 1;
        return stack.back();
    }
};

int main() {
    string s;
    getline(cin, s);
    try {
        Parser p(s, true);
        cout << p.run() << "\n";
    } catch (...) {
        cout << "NO\n";
    }
}