题意简述

给定一个（中缀）表达式，求出它的值，保证运算结果及中间过程在 long long 范围内。

解法

众所周知，中缀表达式转后缀表达式方法如下：

遍历中缀表达式中的元素，

1. 遇到一个数，则输出该数；
2. 遇到左括号，则将其入栈；
3. 遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，将左括号出栈；
4. 遇到运算符，只要栈顶符号的优先级不低于新符号（乘除>加减>左括号），取出栈顶并输出，最后将新符号入栈。

最后，依次取出并输出栈中所有剩余符号，输出序列就是一个与原表达式等价的后缀表达式。

求后缀表达式的值是容易的，或者我们可以在以上过程中直接求解。

但是，存在一些问题：

1. 数据存在负数，即一元负号运算符；
2. 数据存在乘幂运算符 ^，这个运算符是右结合（包括一元正负号运算符也是右结合的）的，以上给出的方法只解决左结合运算符；
3. 数据可能会出现多余括号情况。

对于问题一，我们可以在读入数字时考虑正负号，或者考虑将正负号标记为一元右结合运算符。对于后者，显然仅当上一个元素是左括号或其他二元运算符时会被标记。本篇题解采用后者。

对于问题二，有结论：在以上过程中，若遇到的运算符为右结合运算符，只需将情况 4 改为“只要栈顶符号的优先级低于新符号，取出栈顶并输出”。

对于问题三，由于过于简单，这里不再论述，详情参见代码。

AC Code

#include <bits/stdc++.h>
using namespace std;

bool delim(char c) { return c == ' '; }

bool is_op(char c) {
  return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

bool is_unary(char c) { return c == '+' || c == '-'; }

bool right_assoc(char c) { return c == -43 || c == -45 || c == '^'; }

int priority(char op) {
  switch (op) {
    case '+':
    case '-':
      return 1;
    case '*':
    case '/':
      return 2;
    case '^':
      return 4;
    case -43:
    case -45:
      return 3;
    default:
      return -1;
  }
}

long long qpow(long long a, long long b) {
  if (b < 0) return 0;
  if (b == 0) return 1;
  long long res = 1;
  for (; b > 0; b >>= 1) {
    if (b & 1) res *= a;
    a *= a;
  }
  return res;
}

void process_op(stack<long long>& st, char op) {
  if (op == '(') return;
  if (op < 0) {
    long long l = st.top();
    st.pop();
    switch (-op) {
      case '+':
        st.push(l);
        break;
      case '-':
        st.push(-l);
        break;
    }
  } else {
    long long r = st.top();
    st.pop();
    long long l = st.top();
    st.pop();
    switch (op) {
      case '+':
        st.push(l + r);
        break;
      case '-':
        st.push(l - r);
        break;
      case '*':
        st.push(l * r);
        break;
      case '/':
        if (r == 0) throw "division by zero";
        st.push(l / r);
        break;
      case '^':
        st.push(qpow(l, r));
        break;
    }
  }
}

long long evaluate(string& s) {
  stack<long long> st;
  stack<char> op;
  bool may_be_unary = true;
  for (int i = 0; i < (int)s.size(); i++) {
    if (delim(s[i])) continue;
    if (s[i] == '(') {
      op.push('(');
      may_be_unary = true;
    } else if (s[i] == ')') {
      while (!op.empty()) {
        char p = op.top();
        op.pop();
        if (p == '(') break;
        process_op(st, p);
      }
      may_be_unary = false;
    } else if (is_op(s[i])) {
      char cur_op = s[i];
      if (may_be_unary && is_unary(cur_op)) cur_op = -cur_op;
      while (
          !op.empty() &&
          ((!right_assoc(cur_op) && priority(op.top()) >= priority(cur_op)) ||
           (right_assoc(cur_op) && priority(op.top()) > priority(cur_op)))) {
        process_op(st, op.top());
        op.pop();
      }
      op.push(cur_op);
      may_be_unary = true;
    } else {
      long long num = 0;
      while (i < (int)s.size() && '0' <= s[i] && s[i] <= '9')
        num = (num * 10) + (s[i++] ^ '0');
      --i;
      st.push(num);
      may_be_unary = false;
    }
  }
  while (!op.empty()) {
    process_op(st, op.top());
    op.pop();
  }
  return st.top();
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  string ss;
  cin >> ss;
  try {
    cout << evaluate(ss) << "\n";
  } catch (const char* errorMsg) {
    cout << errorMsg << "\n";
  }
  return 0;
}

后记：关于 throw/try-catch 的解释

考虑到这玩意在 OI 界似乎不常见，这里解释一下，神犇请自行跳过。

简单来说，throw 可以抛出一个异常对象，这会使控制流沿调用栈向上（就是跳出当前函数/代码块），直到被 try-catch 捕获。若异常未被捕获，将调用 std::terminate，这将结束程序并返回一个非零值（通常似乎是 3）。

对于 try-catch 语句，当 try 块内抛出异常，会将异常对象与 catch 子句中声明的类型按顺序尝试匹配，特别地，catch(...) 可以捕获任何异常。

异常被捕获后，程序转入对应的 catch 块运行。

try-catch 的更多信息

好像也可以用 longjmp 函数实现类似效果，在 C 中可用。