中缀表达式转后缀表达式 c++实现

中缀表达式（Infix Notation）转换为后缀表达式（Postfix Notation），也称为逆波兰表示法（Reverse Polish Notation, RPN），是一个常见的算法练习。在C++中，你可以使用栈的数据结构来实现这个过程。以下是一个简单的步骤描述：

1. 创建一个空栈和一个空数组（或后缀表达式的输出列表）。
2. 遍历中缀表达式的每个字符：
a. 如果字符是数字，就直接添加到输出数组。
b. 如果遇到运算符，按照操作符优先级处理：
i. 如果栈顶元素的优先级小于或等于当前运算符，将栈顶元素压入输出数组，然后将当前运算符压入栈。
ii. 否则，直接将当前运算符压入栈。
c. 遇到左括号时，压入栈。
d. 遇到右括号时，直到遇到左括号才开始弹出栈并添加到输出数组，同时更新当前操作数。
3. 遍历结束后，栈中剩余的操作符应逐个弹出并添加到输出数组。
4. 输出数组中的内容就是后缀表达式。

这是一个基础的算法，你可以在C++中用`std::stack`和`std::vector`（或手动维护一个堆栈）来实现。下面是伪代码示例：

std::stack<int> operatorStack;
std::vector<char> postfixExpression;

for (char token : infixExpression) {
    if (isdigit(token)) {
        postfixExpression.push_back(token);
    } else if (isOperator(token)) {
        while (!operatorStack.empty() && isHigherPriority(operatorStack.top(), token)) {
            postfixExpression.push_back(operatorStack.top());
            operatorStack.pop();
        }
        operatorStack.push(token);
    } else if (token == '(') {
        operatorStack.push(token);
    } else if (token == ')') {
        while (operatorStack.top() != '(') {
            postfixExpression.push_back(operatorStack.top());
            operatorStack.pop();
        }
        operatorStack.pop(); // pop the left parenthesis
    }
}

while (!operatorStack.empty()) {
    postfixExpression.push_back(operatorStack.top());
    operatorStack.pop();
}

// Now, postfixExpression contains the result.