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

前言

中缀表达式是我们常见的数学表达式表示方式，例如：3 + 4 * 2 - 1。而后缀表达式是将运算符放在操作数的后面，例如：3 4 2 * + 1 -。本文将介绍如何使用C++实现中缀表达式转后缀表达式的算法，以及代码的设计和规范。

算法设计

为了实现中缀表达式转后缀表达式的功能，我们可以使用栈（Stack）数据结构来辅助计算。具体的算法设计如下：

1. 创建一个栈stack用来存储运算符。
2. 遍历中缀表达式中的每个字符。
3. 如果当前字符是数字，直接输出到后缀表达式。
4. 如果当前字符是左括号（），入栈。
5. 如果当前字符是右括号），将栈中的运算符依次出栈并输出到后缀表达式，直到遇到左括号（（左括号不输出）。
6. 如果当前字符是运算符，检查栈顶运算符的优先级。
• 如果栈为空或栈顶运算符是左括号（，直接入栈。
• 如果当前运算符的优先级大于栈顶运算符的优先级，直接入栈。
• 否则，将栈顶的运算符出栈并输出到后缀表达式，直到当前运算符的优先级大于栈顶运算符的优先级。
7. 遍历完中缀表达式后，将栈中剩余的运算符依次出栈并输出到后缀表达式。
8. 后缀表达式即为转换结果。

代码实现

#include 
#include 
#include 

bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int getPriority(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    }
    return 0;
}

std::string infixToPostfix(std::string infix) {
    std::stack stack;
    std::string postfix;
    
    for (int i = 0; i < infix.length(); i++) {
        char c = infix[i];
        
        if (std::isdigit(c)) {
            postfix += c;
        } else if (c == '(') {
            stack.push(c);
        } else if (c == ')') {
            while (!stack.empty() && stack.top() != '(') {
                postfix += stack.top();
                stack.pop();
            }
            if (!stack.empty()) {
                stack.pop(); // 弹出左括号
            }
        } else if (isOperator(c)) {
            while (!stack.empty() && getPriority(c) <= getPriority(stack.top())) {
                postfix += stack.top();
                stack.pop();
            }
            stack.push(c);
        }
    }
    
    while (!stack.empty()) {
        postfix += stack.top();
        stack.pop();
    }
    
    return postfix;
}

int main() {
    std::string infixExpression;
    std::cout << "请输入中缀表达式：" << std::endl;
    std::cin >> infixExpression;
    std::string postfixExpression = infixToPostfix(infixExpression);
    std::cout << "后缀表达式为：" << postfixExpression << std::endl;
    
    return 0;
}

代码解释

我们首先定义了一个isOperator函数，用于判断一个字符是否为运算符。然后定义了一个getPriority函数，用于获取运算符的优先级。接着，实现了infixToPostfix函数，该函数接收一个中缀表达式作为输入，返回转换后的后缀表达式。

在主函数中，我们首先从用户输入获取中缀表达式，并调用infixToPostfix函数进行转换。最终将转换后的后缀表达式输出到屏幕上。

总结

本文介绍了如何使用C++实现中缀表达式转后缀表达式的算法，并提供了相应的代码实现。通过栈的辅助，我们可以遍历中缀表达式的每个字符，并根据优先级来判断操作，将转换结果输出为后缀表达式。这样的实现方式可以方便后续的表达式求值计算。