c++中转后缀表达式

在 C++ 中，后缀表达式（也称为逆波兰表示法，Reverse Polish Notation, RPN）是一种将数学运算转换为计算机处理的简单形式。它将操作数放在操作符之前，避免了括号的需求，通常用于解析算法如 Shunting Yard 算法来计算复杂表达式的值。

Shunting Yard 算法是两个步骤的过程：
1. **扫描输入**：从左到右读取表达式，遇到操作数就直接压入栈；遇到操作符则比较其优先级与栈顶元素，如果栈顶元素优先级低，则将栈顶元素弹出并压入结果，然后继续处理当前操作符；若当前操作符优先级高或相等，则将其压入栈。
2. **计算结果**：当扫描完整个表达式后，栈中剩下的就是完整的操作序列。从栈底开始取出元素，依次作为操作数和操作符进行计算，直到栈为空。

如果你想在 C++ 中实现这个功能，你需要创建一个队列来模拟栈，并编写函数来处理操作符和数字。这是一个简单的例子：

#include <iostream>
#include <stack>
#include <queue>

int precedence(char op) {
    // 定义操作符优先级
    return (op == '+' || op == '-') ? 1 : 2;
}

bool greater_precedence(char a, char b) {
    return precedence(a) > precedence(b);
}

std::string infixToPostfix(const std::string& expression) {
    std::queue<char> output;
    std::stack<std::pair<char, int>> parentheses;

    for (char token : expression) {
        if (isdigit(token)) {
            // 如果是数字，直接添加到输出队列
            while (!output.empty() && isdigit(output.front())) {
                std::cout << output.front();
                output.pop();
            }
            output.push(token);
        } else if (token == '(') {
            parentheses.push({token, 0});
        } else if (token == ')') {
            while (!parentheses.empty() && parentheses.top().first != '(') {
                output.push(parentheses.top().first);
                parentheses.pop();
            }
            if (!parentheses.empty()) parentheses.pop(); // 弹出左括号
        } else {
            while (!parentheses.empty() && greater_precedence(token, parentheses.top().first)) {
                output.push(parentheses.top().first);
                parentheses.pop();
            }
            parentheses.push({token, 0}); // 推入当前操作符
        }
    }

    // 将剩余的操作符推入输出队列
    while (!parentheses.empty()) {
        output.push(parentheses.top().first);
        parentheses.pop();
    }

    // 将所有元素从队列中移除并打印
    while (!output.empty()) {
        std::cout << output.front();
        output.pop();
    }

    return "";
}

int main() {
    std::string expression = "a + b * c / d";
    std::cout << "Postfix form: " << infixToPostfix(expression) << std::endl;
    return 0;
}