C++实现infix to postfix中缀转后缀表达式输出错误排查

你的代码存在两处核心逻辑错误，直接导致后缀表达式生成结果不符合预期：

• 运算符处理逻辑错误：完成栈中高优先级运算符弹出操作后，你没有将当前运算符压入栈，而是直接加入了后缀表达式数组，直接打乱了运算符的优先级和入栈顺序。
• 栈残留运算符未处理：遍历完全部中缀表达式元素后，没有将栈中剩余的运算符依次弹出加入后缀表达式，会导致栈中残留的运算符丢失。

1. 修改运算符分支的代码，将直接写入后缀表达式的逻辑改为压入栈：
   把原来运算符分支末尾的postfix.push_back(expr[i]);替换为st.push(expr[i]);
2. 在infix_to_postfix函数的return语句之前，添加代码弹出栈中所有残留运算符加入后缀表达式：

while (!st.empty()) {
    postfix.push_back(st.pop());
}

另外你的Stack类中定义的string stack[100][1]是冗余的二维数组，修改为string stack[100];即可，不影响当前功能属于可优化项。 #

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <iomanip>
using namespace std;

class Stack {
public:
    string stack[100]; // 优化为一维数组即可
    int size;

    Stack() { size = 0; }
    ~Stack() {};

    void push(string data) {
        stack[size] = data;
        size += 1;
    }

    bool empty() {
        return size == 0;
    }

    string pop() {
        size -= 1;
        return stack[size];
    }

    string top() {
        if (empty())
            cout << "Stack is empty";
        return stack[size - 1];
    }
};

int pre(char op)
{
    switch (op)
    {
    case '(': case ')': return 0;
    case '+': case '-': return 1;
    case '*': case '/': return 2;
    }
    return -1;
}

vector<string> infix_to_postfix(const vector<string>& expr) {
    vector<string> postfix;
    string op;
    Stack st;

    for (int i = 0; i < expr.size(); i++) {
        if (expr[i][0] == '+' || expr[i][0] == '-' || expr[i][0] == '*' || expr[i][0] == '/') {
            while (!st.empty()) {
                op = st.top();
                if (pre(expr[i][0]) <= pre(op[0]))
                    postfix.push_back(st.pop());
                else break;
            }
            st.push(expr[i]); // 运算符压栈，而非直接加入后缀
        }
        else if (expr[i][0] == '(') {
            st.push(expr[i]);
        }
        else if (expr[i][0] == ')') {
            while (!st.empty()) {
                op = st.pop();
                if (op[0] == '(') break;
                else {
                    postfix.push_back(op);
                }
            }
        }
        else {
            postfix.push_back(expr[i]);
        }
    }
    // 弹出栈中剩余所有运算符
    while (!st.empty()) {
        postfix.push_back(st.pop());
    }
    return postfix;
}

int main() {
    auto expr = infix_to_postfix({ "(", "2", "+", "3", ")", "*", "7" });
    for (auto& elem : expr)
    {
        std::cout << elem << ", ";
    }
    std::cout << "\n";

    return 0;
}

运行修复后的代码，输出为2, 3, +, 7, *, ，和预期结果一致。

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