如何用C++来实现中缀表达式变后缀表达式

在C++中，将中缀表达式转换成后缀（也称为逆波兰表示法，RPN）可以通过递归算法实现。主要步骤包括：

1. 定义两个栈：一个用于存放运算符，另一个用于临时存储操作数。
2. 遍历中缀表达式的每个字符：
- 如果遇到数字，将其压入结果栈。
- 如果遇到左括号，直接入栈。
- 如果遇到运算符：
a. 判断运算符优先级，如果当前运算符优先级高于栈顶运算符，则依次弹出并压入结果栈，直到遇到优先级低于或等于当前运算符的运算符。
b. 将当前运算符压入运算符栈。
- 遇到右括号时，将其从左到右弹出，并压入结果栈，直到遇到左括号为止。
3. 当遍历结束后，运算符栈只剩下一些未匹配的运算符，将它们全部压入结果栈。

以下是简化版的C++代码示例：

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

int precedence(char op) {
    // 根据运算符优先级表来确定
    return (op == '+' || op == '-') ? 1 : 2;
}

bool isOperator(char op) {
    return op == '+' || op == '-' || op == '*' || op == '/';
}

std::string infixToPostfix(const std::string &expr) {
    std::stack<char> opStack;
    std::string postfixExpr;

    for (char c : expr) {
        if (!isOperator(c)) {  // 数字或左括号
            postfixExpr += c;
        } else if (c == '(') {  // 左括号
            opStack.push(c);
        } else if (c == ')') {  // 右括号
            while (!opStack.empty() && opStack.top() != '(') {
                postfixExpr += opStack.pop();
            }
            if (!opStack.empty()) {
                opStack.pop();  // 弹出左括号
            }
        } else {  // 运算符
            while (!opStack.empty() && precedence(opStack.top()) >= precedence(c)) {
                postfixExpr += opStack.pop();
            }
            opStack.push(c);
        }
    }

    // 将剩余的运算符添加到后缀表达式中
    while (!opStack.empty()) {
        postfixExpr += opStack.pop();
    }

    return postfixExpr;
}

int main() {
    std::string expression = "A+B*C-D";
    std::string postfixExpression = infixToPostfix(expression);
    std::cout << "后缀表达式: " << postfixExpression << std::endl;
    return 0;
}