中缀转前缀c++代码

中缀表达式（如 "A+B*C-D/E"）转换为前缀表达式（也称作逆波兰表示法或后缀表达式，如 "AB*+CD-*/"），可以通过栈数据结构来实现。这里是一个简单的 C++ 示例，使用了两个栈：

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

// 帮助函数，用于计算操作数
int calculate(std::stack<int>& ops) {
    int op2 = ops.top(); ops.pop();
    int op1 = ops.top(); ops.pop();
    switch (ops.top()) {
        case '+': return op1 + op2;
        case '-': return op1 - op2;
        case '*': return op1 * op2;
        case '/': return op1 / op2; // 注意处理除数为0的情况
    }
}

std::string infixToPrefix(const std::string& expression) {
    std::stack<std::pair<char, int>> ops; // 右括号优先栈
    std::stack<char> output; // 输出栈

    for (char c : expression) {
        if (isdigit(c)) { // 如果是数字，直接压入输出栈
            output.push(c);
        } else if (c == '(') { // 开始新的运算符序列，推到运算符栈
            ops.push({c, 0});
        } else if (c == ')') { // 结束运算符序列，处理直至找到左括号
            while (!ops.empty() && ops.top().first != '(') {
                output.push(ops.top().second);
                ops.pop();
            }
            if (ops.top().first != '(') throw std::runtime_error("Invalid expression");
            ops.pop(); // 移除左括号
        } else { // 运算符
            while (!ops.empty() && precedence(c) <= precedence(ops.top().first)) {
                output.push(ops.top().second);
                ops.pop();
            }
            ops.push({c, 1}); // 用1表示当前是运算符
        }
    }

    // 处理剩余的运算符
    while (!ops.empty()) {
        output.push(ops.top().second);
        ops.pop();
    }

    // 把所有元素压回字符串并返回
    std::ostringstream ss;
    for (char c : output) {
        ss << c;
    }
    return ss.str();
}

int precedence(char op) {
    // 这里只是一个简单的例子，实际应用中可能需要根据运算符优先级来定义precendence
    switch (op) {
        case '+':
        case '-': return 1;
        case '*':
        case '/': return 2;
        default: return 0; // 不合法的运算符
    }
}

int main() {
    std::string expression = "(A+B)*(C-D)/E";
    try {
        std::cout << "Infix: " << expression << "\n";
        std::cout << "Prefix: " << infixToPrefix(expression) << "\n";
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << '\n';
    }
    return 0;
}

这个示例实现了基本的中缀到前缀转换，但它没有处理除数为0的情况，也没有复杂优先级规则。在实际应用中，可能需要更完整的解析器。