C++利用栈实现中缀表达式转后缀表达式

前言:

中缀表达式是我们平时最常见的数学表达方式，例如：3 + 4 * 2 - 1。而后缀表达式（也称为逆波兰表示法）则是一种更加简洁的表达方式，操作符位于操作数之后，例如：3 4 2 * + 1 -。 在计算机中，处理后缀表达式更加高效，因为不需要依赖于括号进行优先级判断。因此，我们将使用栈来实现中缀表达式转后缀表达式的算法。

算法步骤:

下面是利用栈实现中缀表达式转后缀表达式的算法步骤：

    1. 初始化两个栈：操作符栈和结果栈。
    2. 从左到右遍历中缀表达式的每个字符：
        2.1 如果是操作数，直接将其添加到结果栈。
        2.2 如果是操作符，通过比较操作符栈顶的优先级来确定是否将其弹出并添加到结果栈。
        2.3 如果是左括号'('，直接将其压入操作符栈。
        2.4 如果是右括号')'，则依次弹出操作符栈顶的操作符并添加到结果栈，直到遇到左括号'('。
    3. 如果遍历完中缀表达式后，操作符栈中仍然有操作符，则依次弹出并添加到结果栈。
    4. 返回结果栈中的后缀表达式。

    以下是具体的代码实现：
    

#include 
#include 
#include 

// 函数用于判断操作符的优先级
int getPrecedence(char op) {
    if (op=='*' || op=='/') {
        return 2;
    } else if (op=='+' || op=='-') {
        return 1;
    } else {
        return 0;
    }
}

std::string infixToPostfix(const std::string& infixExpression) {
    std::string postfixExpression;
    std::stack operatorStack;

    for (char c : infixExpression) {
        // 如果是操作数，直接添加到后缀表达式字符串
        if (isalnum(c)) {
            postfixExpression +=c;
        }
        // 如果是操作符
        else if (c=='(') {
            operatorStack.push(c);
        } else if (c==')') {
            // 弹出操作符栈顶的操作符并添加到后缀表达式字符串，直到遇到左括号
            while (!operatorStack.empty() && operatorStack.top() !='(') {
                postfixExpression +=operatorStack.top();
                operatorStack.pop();
            }
            // 弹出左括号
            if (!operatorStack.empty() && operatorStack.top()=='(') {
                operatorStack.pop();
            }
        } else {
            // 比较操作符栈顶的优先级，将其弹出并添加到后缀表达式字符串
            while (!operatorStack.empty() && getPrecedence(operatorStack.top()) >=getPrecedence(c)) {
                postfixExpression +=operatorStack.top();
                operatorStack.pop();
            }
            // 将操作符添加到操作符栈
            operatorStack.push(c);
        }
    }

    // 将剩余的操作符依次添加到后缀表达式字符串
    while (!operatorStack.empty()) {
        postfixExpression +=operatorStack.top();
        operatorStack.pop();
    }

    return postfixExpression;
}

int main() {
    std::string infixExpression="3 + 4 * 2 - 1";
    std::string postfixExpression=infixToPostfix(infixExpression);
    std::cout << "中缀表达式: " << infixExpression << std::endl;
    std::cout << "后缀表达式: " << postfixExpression << std::endl;

    return 0;
}
    

解释和规范:

上述代码实现了利用栈进行中缀表达式转后缀表达式的功能。代码中，getPrecedence函数用于判断操作符的优先级，辅助算法中缀表达式转后缀表达式。 infixToPostfix函数接受一个中缀表达式作为输入，并返回转换后的后缀表达式。 在算法中，我们创建了两个栈：一个操作符栈用于存储操作符，一个结果栈用于存储后缀表达式。通过遍历中缀表达式的每个字符，我们根据不同情况进行处理：

• 如果是操作数，直接将其添加到结果栈。
• 如果是操作符，根据操作符栈顶的优先级决定是否将其弹出，然后添加到结果栈。
• 如果是左括号'('，直接将其压入操作符栈。
• 如果是右括号')'，则依次弹出操作符栈顶的操作符并添加到结果栈，直到遇到左括号'('。

最后，我们将操作符栈中剩余的操作符依次弹出并添加到结果栈，得到最终的后缀表达式。通过上述算法，我们可以将任意中缀表达式转换为后缀表达式。

总结:

本文介绍了利用栈实现中缀表达式转后缀表达式的算法，并提供了对应的代码实现。通过栈的数据结构特性，我们可以有效地处理操作符的优先级和括号的匹配，从而实现表达式的转换。 这种转换方式在编写计算器、编译器等应用程序中十分常见，具有很高的实用性和扩展性。希望本文对您理解中缀表达式和后缀表达式的转换有所帮助。