C++ 中缀表达式转换为后缀表达式：非递归算法实现

本文将介绍如何使用 C++ 编写一段代码将中缀表达式转换为后缀表达式。中缀表达式是运算符位于两个运算对象之间的表达式，例如 'a * b - (c + d) / e'。后缀表达式则是运算符位于两个运算对象之后的表达式，例如 'ab * cd + e / - '。

为了实现这一转换，我们将使用非递归算法，并对输入的表达式进行必要的语法检查。

非递归算法实现

以下 C++ 代码展示了非递归算法实现：

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

// 判断字符是否为运算符
bool isOperator(char c) {
    if (c == '+' || c == '-' || c == '*' || c == '/') {
        return true;
    }
    return false;
}

// 判断字符是否为左括号
bool isLeftParenthesis(char c) {
    if (c == '(') {
        return true;
    }
    return false;
}

// 判断字符是否为右括号
bool isRightParenthesis(char c) {
    if (c == ')') {
        return true;
    }
    return false;
}

// 判断运算符的优先级
int getPriority(char op) {
    if (op == '*' || op == '/') {
        return 2;
    } else if (op == '+' || op == '-') {
        return 1;
    }
    return 0;
}

// 将中缀表达式转换为后缀表达式
std::string infixToPostfix(const std::string& infixExpression) {
    std::stack<char> operatorStack;
    std::string postfixExpression;

    for (int i = 0; i < infixExpression.length(); i++) {
        char c = infixExpression[i];

        if (isOperator(c)) {
            while (!operatorStack.empty() && isOperator(operatorStack.top()) &&
                   getPriority(operatorStack.top()) >= getPriority(c)) {
                postfixExpression += operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.push(c);
        } else if (isLeftParenthesis(c)) {
            operatorStack.push(c);
        } else if (isRightParenthesis(c)) {
            while (!operatorStack.empty() && !isLeftParenthesis(operatorStack.top())) {
                postfixExpression += operatorStack.top();
                operatorStack.pop();
            }
            if (!operatorStack.empty() && isLeftParenthesis(operatorStack.top())) {
                operatorStack.pop();
            } else {
                // 括号不配对，返回空字符串表示出错
                return '';
            }
        } else {
            // 非法字符，返回空字符串表示出错
            return '';
        }
    }

    while (!operatorStack.empty()) {
        if (isLeftParenthesis(operatorStack.top()) || isRightParenthesis(operatorStack.top())) {
            // 括号不配对，返回空字符串表示出错
            return '';
        }
        postfixExpression += operatorStack.top();
        operatorStack.pop();
    }

    return postfixExpression;
}

int main() {
    std::string infixExpression;
    std::cout << '请输入中缀表达式：';
    std::cin >> infixExpression;

    std::string postfixExpression = infixToPostfix(infixExpression);
    if (postfixExpression == '') {
        std::cout << '表达式不合法！' << std::endl;
    } else {
        std::cout << '后缀表达式：' << postfixExpression << std::endl;
    }

    return 0;
}

代码解释

isOperator(char c): 判断字符是否为运算符 (+, -, *, /)。
isLeftParenthesis(char c): 判断字符是否为左括号 (。
isRightParenthesis(char c): 判断字符是否为右括号 )。
getPriority(char op): 获取运算符的优先级。乘除优先级为 2，加减优先级为 1。
infixToPostfix(const std::string& infixExpression): 核心转换函数，使用栈来存储运算符，并根据优先级依次将运算符添加到后缀表达式中。

示例输入输出

输入：

(a*b-(c+d)/e)

输出：

后缀表达式：ab*cd+e/-

代码局限性

语法检查: 当前代码仅检查括号是否配对，以及是否包含非法字符。对于更复杂的语法检查，如变量名是否合法、运算符是否正确、是否存在多余的括号等，需要进一步扩展代码逻辑。
浮点数运算: 代码未考虑浮点数运算、负数运算等情况，需要根据具体需求进行进一步修改。

总结

本文介绍了如何使用 C++ 编写非递归算法，将中缀表达式转换为后缀表达式。代码示例实现了基本的功能，并对代码的局限性进行了讨论。在实际应用中，需要根据具体需求对代码进行扩展和完善。