题意分析

本题要求将给定的后缀表达式转换为一个新的表达式，使得使用队列（FIFO）的求值结果与原始表达式使用栈（LIFO）的求值结果完全相同。关键点在于：

1. 栈求值原理：

   • 遇到操作数入栈
   • 遇到运算符时，弹出栈顶两个元素（先弹出右操作数，后弹出左操作数）
   • 计算 左操作数 运算符 右操作数 并将结果入栈

2. 队列求值原理：

   • 遇到操作数入队尾
   • 遇到运算符时，弹出队首两个元素（先弹出左操作数，后弹出右操作数）
   • 计算 左操作数 运算符 右操作数 并将结果入队尾

3. 核心挑战：

   • 由于栈（LIFO）和队列（FIFO）的特性差异，操作数出容器的顺序不同
   • 在运算符不具有交换律的前提下，必须通过调整表达式的结构（操作符位置）而非简单重排操作数来保证计算结果一致

解题思路

通过观察发现：新表达式本质上是原始表达式树的层序遍历结果的逆序。具体步骤：

1. 构建表达式树：

   • 从后向前处理后缀表达式
   • 运算符为父节点
   • 连续两个操作数（或子表达式）为其左右子节点
   • 递归构建整棵树

2. 层序遍历 + 倒序存储：

   • 对表达式树进行BFS层序遍历（从根节点开始）
   • 按遍历的逆序存储节点值
   • 倒序存储保证了队列求值时：
     • 运算符的弹出顺序对应树中层级关系
     • 操作数在队列中的位置对应树中操作数位置
     • 计算顺序与原始栈求值完全一致

关键步骤图示

以 xyPzwIM 为例：

原始后缀表达式: x y P z w I M

表达式树结构：
      M
     / \
    P   I
   / \ / \
  x  y z  w

层序遍历顺序: M, P, I, x, y, z, w
逆序存储: w, z, y, x, I, P, M
输出: wzyxIPM

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <queue>

using namespace std;

const int N = 10000;
char exp_in[N + 1], ans[N + 1];

struct Tree {
    char node;
    int left = -1, right = -1;
} tree[N];

int tcnt;  // 树节点计数器

// 从位置k向左找到第一个操作数（分隔左右子树）
int find(int k) {
    int depth = 0;  // 模拟栈深度
    while (k >= 0) {
        if (islower(exp_in[k])) {
            if (++depth == 1) break;
        } else {
            depth--;
        }
        k--;
    }
    return k;
}

// 递归构建表达式树
int buildTree(int start, int end) {
    int root = tcnt++;
    tree[root].node = exp_in[end];
    tree[root].left = tree[root].right = -1;

    if (start == end) return root;  // 叶节点（操作数）

    int mid = find(end - 1);  // 寻找子树分界点

    // 递归构建右子树（先处理）
    if (mid < end) 
        tree[root].right = buildTree(mid, end - 1);
    
    // 递归构建左子树（后处理）
    if (mid > start)
        tree[root].left = buildTree(start, mid - 1);

    return root;
}

// BFS倒序存储层序遍历
void reverseLevelOrder(int root, int len) {
    queue<int> q;
    ans[len] = '\0';
    int idx = len - 1;  // 从后往前存储
    
    q.push(root);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        ans[idx--] = tree[cur].node;  // 倒序存储关键点
        
        // 左右节点入队（顺序决定层序结构）
        if (tree[cur].left != -1)
            q.push(tree[cur].left);
        if (tree[cur].right != -1)
            q.push(tree[cur].right);
    }
}

int main() {
    int t;
    scanf("%d", &t);
    getchar();
    while (t--) {
        if (fgets(exp_in, N + 1, stdin) == NULL) break;
        
        // 移除换行符
        size_t len = strlen(exp_in);
        if (len > 0 && exp_in[len - 1] == '\n') 
            exp_in[--len] = '\0';

        tcnt = 0;  // 重置节点计数器
        reverseLevelOrder(buildTree(0, len - 1), len);
        printf("%s\n", ans);
    }
    return 0;
}

算法分析

1. 时间复杂度：O(n)

   • 构建树：每个节点处理一次，O(n)
   • BFS遍历：每个节点访问一次，O(n)
   • 总线性时间复杂度，满足 10000 字符限制

2. 空间复杂度：O(n)

   • 树节点存储：O(n)
   • BFS队列：最坏O(n)