题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2175
题意：给出一个字符串形式的逆波兰式，其中每个大写字母表示运算符，每个小写字母表示一个变量。为了求表达式的值，显然可以维护一个栈，遇到运算符时先pop两个，push运算的结果……
为了使用同样的算法，并将push和pop操作换成如下的过程，还能得到相同的值，必须将这个字符串改变一下形式（比如交换字母的顺序），问变形后的字符串（为了保证结果唯一，规定xPy和yPx不同，并且相同的运算符之间不具有传递性，比如xPyPz != xP(yPz)）。
push(a): 将a放到一个队列的尾部
b = pop(): 从对首弹出一个元素赋给b
数据规模：样例个数T<=200，每个样例的字符串长度<=10000
2 xyPzwIM abcABdefgCDEF
wzyxIPM gfCecbDdAaEBF
思路：
1. 研究一下样例，将结果还原为中缀式，不难发现结果的最后一个字符一定是前缀式的最后一个字符，也就是表达式树的根节点
2. 如果在表达式树上模拟一下这个还原过程，也不难发现：所求结果很可能是按照BFS的顺序遍历表达式树的节点（模拟的过程可以大概理解证明的框架）
这样如果建树然后BFS，复杂度刚好是O(n)，过得去。
既然是BFS，就是按深度递增的顺序的依次遍历每层结点，还可以换个思路，递归求出每个节点的深度，然后按照前缀式的顺序进行一次稳定排序，这样排序的结果刚好是所求字符串的逆串。
稳定排序如果使用计数排序，这个复杂度也会是O(n)级别的。
3. 因为这里的表达式树是二叉树，所以直接用ls[]和rs[]维护左右儿子就行了，建树时间复杂度和空间复杂度都是O(n)
4. 由1可以知道树根节点标号一定是n-1（节点标号从0开始）
# include <cstdio> # include <cstring> # include <cctype> # include <algorithm> using namespace std; const int maxn = 10005; const int maxval = 10005; int n, m; // max{a[i], i=0,...,n-1} int r[maxn], x[maxn], y[maxn]; void init(int radix[]) { for (int i = 0; i < n; ++i) radix[i] = i; } int cnt[maxval]; void radix_sort(int arr[], int radix[]) { memset(cnt, 0, sizeof(cnt[0])*(m+1)); for (int i = 0; i < n; ++i) ++cnt[arr[i]]; for (int i = 1; i <= m; ++i) cnt[i] += cnt[i-1]; for (int i = n-1; i >= 0; --i) radix[ --cnt[ arr[i] ] ] = i; } int ls[maxn], rs[maxn]; void cal(int rt) { if (rt==n-1) x[rt] = 0; if (ls[rt] != -1) { x[ls[rt]] = 1+x[rt]; cal(ls[rt]); } if (rs[rt] != -1) { x[rs[rt]] = 1+x[rt]; cal(rs[rt]); } } int t[maxn]; void pre(void) { cal(n-1); memset(t, 0, sizeof(t[0])*(n+1)); for (int i = 0; i < n; ++i) y[i] = t[x[i]]++; m = x[0]; for (int i = 0; i < n; ++i) m = max(m,max(x[i],y[i])); } char s[maxn]; int st[maxn], top; void build_tree(void) { n = strlen(s); memset(ls, -1, sizeof(ls[0])*(n+1)); memset(rs, -1, sizeof(rs[0])*(n+1)); top = 0; for (int i = 0; i < n; ++i) { if (isupper(s[i])) { rs[i] = st[--top]; ls[i] = st[--top]; } st[top++] = i; } } void solve(void) { build_tree(); pre(); init(r); radix_sort(x, r); for (int i = n-1; i >= 0; --i) { printf("%c", s[r[i]]); } printf("\n"); } int main() { int T; scanf("%d", &T); for (int ica = 1; ica <= T; ++ica) { scanf("%s", s); solve(); } return 0; }
UVa 11234 - Expressions,布布扣,bubuko.com
原文：http://www.cnblogs.com/txd0u/p/3667582.html