前缀表达式转中缀表达式求助：代码解析及输出改造指导

兄弟，我太懂你这种对着代码抓耳挠腮的感觉了！你说的前缀转中缀的问题，我先帮你把原前缀求值代码的逻辑拆明白，再一步步教你怎么改造它来输出中缀表达式。

一、先搞懂原前缀表达式求值代码的核心逻辑 #

首先得明确：前缀表达式（波兰表达式）的结构是「运算符 + 左操作数 + 右操作数」，比如* + 3 4 - 5 2对应的中缀是(3+4)*(5-2)。

常规的前缀求值代码（你手里的应该是栈实现版本）逻辑是这样的：

• 从右往左扫描前缀表达式的每个字符
• 遇到操作数（数字），直接压入栈中
• 遇到运算符，弹出栈顶的两个元素：注意！第一个弹出的是右操作数，第二个弹出的是左操作数（因为我们是反向遍历的）
• 用运算符计算这两个操作数的结果，把结果压回栈
• 遍历结束后，栈里剩下的唯一元素就是整个表达式的计算结果

举个例子，拿* + 3 4 - 5 2来说：

1. 从右往左扫：2→压栈；5→压栈；遇到-→弹出5和2，计算5-2=3→压栈
2. 继续扫：4→压栈；3→压栈；遇到+→弹出3和4，计算3+4=7→压栈
3. 最后遇到*→弹出7和3，计算7*3=21→压栈，栈顶就是结果21

二、改造代码实现前缀转中缀的核心思路 #

要改成输出中缀表达式，核心就是把栈里存的「数值」换成「字符串形式的中缀表达式片段」，具体步骤调整为：

• 遇到操作数，把它作为字符串压入栈
• 遇到运算符，弹出两个字符串（右操作数s2、左操作数s1），拼接成(s1 运算符 s2)（加括号是为了保证运算顺序不混乱，避免歧义）
• 把拼接好的新字符串压回栈
• 遍历结束后，栈顶的字符串就是完整的中缀表达式

三、两种常见实现方式的改造示例 #

1. 栈实现版本（对应原代码的栈逻辑） #

#include <iostream>
#include <string>
#include <stack>
#include <cctype>

using namespace std;

string prefixToInfix(string prefix) {
    stack<string> exprStack;
    // 从右往左遍历前缀表达式
    for (int i = prefix.size() - 1; i >= 0; i--) {
        // 跳过空格
        if (prefix[i] == ' ') continue;

        // 处理操作数（支持多位数）
        if (isdigit(prefix[i])) {
            string numStr;
            // 因为反向遍历，要往前找连续的数字拼接成完整数字
            while (i >= 0 && isdigit(prefix[i])) {
                numStr = prefix[i] + numStr;
                i--;
            }
            i++; // 循环多减了一次，回退一位
            exprStack.push(numStr);
        } 
        // 处理运算符
        else {
            string leftExpr = exprStack.top();
            exprStack.pop();
            string rightExpr = exprStack.top();
            exprStack.pop();
            // 拼接成带括号的中缀片段
            string combinedExpr = "(" + leftExpr + " " + prefix[i] + " " + rightExpr + ")";
            exprStack.push(combinedExpr);
        }
    }
    return exprStack.top();
}

int main() {
    string prefixExpr = "* + 3 4 - 5 2";
    cout << "原前缀表达式：" << prefixExpr << endl;
    cout << "转换后的中缀表达式：" << prefixToInfix(prefixExpr) << endl;
    // 输出结果：((3 + 4) * (5 - 2))
    return 0;
}

2. 递归实现版本（如果原代码是递归求值的话） #

如果你的原代码是递归风格的，改造逻辑更直观：前缀表达式的第一个元素是运算符，后面依次是左、右子表达式，递归处理左右子表达式后拼接即可：

#include <iostream>
#include <string>
#include <cctype>

using namespace std;

int currentIndex = 0; // 全局索引，记录当前处理到的位置

string prefixToInfixRecursive(string prefix) {
    // 跳过空格
    while (currentIndex < prefix.size() && prefix[currentIndex] == ' ') {
        currentIndex++;
    }
    if (currentIndex >= prefix.size()) return "";

    char currentChar = prefix[currentIndex];
    currentIndex++;

    // 处理操作数
    if (isdigit(currentChar)) {
        string numStr;
        numStr += currentChar;
        while (currentIndex < prefix.size() && isdigit(prefix[currentIndex])) {
            numStr += prefix[currentIndex];
            currentIndex++;
        }
        return numStr;
    }
    // 处理运算符：递归获取左、右子表达式
    else {
        string leftExpr = prefixToInfixRecursive(prefix);
        string rightExpr = prefixToInfixRecursive(prefix);
        return "(" + leftExpr + " " + currentChar + " " + rightExpr + ")";
    }
}

int main() {
    string prefixExpr = "* + 3 4 - 5 2";
    currentIndex = 0;
    cout << "原前缀表达式：" << prefixExpr << endl;
    cout << "转换后的中缀表达式：" << prefixToInfixRecursive(prefixExpr) << endl;
    return 0;
}

关键注意点 #

• 括号的必要性：如果不加括号，像* + 3 4 5会被转成3+4*5，但原前缀的意思是(3+4)*5，括号能严格保证运算顺序和原前缀一致
• 多位数处理：代码里考虑了多位数的情况，比如+ 123 456会被正确转成(123 + 456)
• 空格处理：前缀表达式里操作数和运算符之间一般用空格分隔，代码里做了跳过空格的逻辑，适配常见的输入格式

内容的提问来源于stack exchange，提问作者Michael