rec.

明明开到了 1e5 还没过。。

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

char a[N];
int n;
int c1[N], c2[N], c3[N];
int l1[N], l2[N], l3[N];
string t[N];
int top2 = 0;
string s[N];
int top = 0;

int to_num(string s) {
	int sum = 0, len = s.size();
	for (int i = 0; i < len; i++) sum = sum * 10 + s[i] - '0';
	return sum;
}

int calc(int x, int y, char op) {
	if (op == '+') return x + y;
	if (op == '-') return x - y;
	if (op == '*') return x * y;
	if (op == '/') return x / y;
	if (op == '^') {
		int res = 1;
		for (int i = 1; i <= y; i++) res *= x;
		return res;
	}
	return -1;
}

void dfs(int l, int r) {
	if (l1[r] >= l && l1[r] <= r) {
		dfs(l, l1[r] - 1);
		dfs(l1[r] + 1, r);
		string k;
		k.push_back(a[l1[r]]);
		s[++top] = k;
	}
	else if (l2[r] >= l && l2[r] <= r) {
		dfs(l, l2[r] - 1);
		dfs(l2[r] + 1, r);
		string k;
		k.push_back(a[l2[r]]);
		s[++top] = k;
	}
	else if (l3[l] >= l && l3[l] <= r) {
		dfs(l, l3[l] - 1);
		dfs(l3[l] + 1, r);
		string k;
		k.push_back(a[l3[l]]);
		s[++top] = k;
	}
	else if (a[l] == '(' && a[r] == ')') dfs(l + 1, r - 1);
	else {
		string k;
		k.push_back(a[l]);
		s[++top] = k;
	}
}

int main() {
	scanf("%s", a + 1);
	n = strlen(a + 1);
	int x = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i] == '(') ++x;
		if (a[i] == ')') --x;
		if (a[i] == '+' || a[i] == '-') c1[x] = i;
		if (a[i] == '*' || a[i] == '/') c2[x] = i;
		l1[i] = c1[x];
		l2[i] = c2[x];
	}
	for (int i = n; i; i--) {
		if (a[i] == ')') ++x;
		if (a[i] == '(') --x;
		if (a[i] == '^') c3[x] = i;
		l3[i] = c3[x];
	}
	dfs(1, n);
	while (top > 1) {
		for (int i = 1; i <= top; i++) cout << s[i] << " ";
		cout << "\n";
		top2 = 0;
		int f = 0;
		for (int i = 1; i <= top; i++) {
			if (isdigit(s[i][0])) t[++top2] = s[i];
			else if (!f) {
				int y = to_num(t[top2--]);
				int x = to_num(t[top2--]);
				t[++top2] = to_string(calc(x, y, s[i][0]));
				f = 1;
			} else t[++top2] = s[i];
		}
		top = top2;
		for (int i = 1; i <= top; i++) s[i] = t[i];
	}
	cout << s[top];
	return 0;
}