中缀表达式转后缀表达式转后缀表达式C++代码

中缀表达式转后缀表达式，也称为逆波兰表示法（Reverse Polish Notation，RPN），是一种常见的算法练习，通常使用栈数据结构来实现。以下是C++的一个简单示例，使用递归解析中缀表达式：

#include <iostream>
#include <string>
#include <stack>
using namespace std;

// 定义操作符优先级
int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    else if (op == '*' || op == '/') return 2;
    else return 0; // 其他字符默认最低优先级
}

// 判断是否需要立即添加操作数到结果
bool isOperator(char op) {
    return op != '+' && op != '-' && op != '*' && op != '/';
}

// 中缀表达式转后缀表达式的函数
string infixToPostfix(string exp) {
    stack<char> s;
    string postfixExp = "";
    for (char token : exp) {
        if (isdigit(token)) {
            postfixExp += token;
        } else if (isOperator(token)) {
            while (!s.empty() && precedence(s.top()) >= precedence(token)) {
                postfixExp += s.top();
                s.pop();
            }
            s.push(token);
        } else if (token == '(') {
            s.push(token);
        } else if (token == ')') {
            while (s.top() != '(') {
                postfixExp += s.top();
                s.pop();
            }
            s.pop(); // 出栈左括号
        }
    }
    // 将剩余的操作符加到后缀表达式
    while (!s.empty()) {
        postfixExp += s.top();
        s.pop();
    }
    return postfixExp;
}

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