C++ 中缀表达式转后缀表达式（逆波兰表达式）算法及代码示例

简介

在计算机科学中，中缀表达式是一种常见的数学表达式表示方法，运算符位于操作数之间。然而，对于计算机来说，处理后缀表达式（也称为逆波兰表达式）更为方便，因为后缀表达式不需要括号，并且可以使用栈来进行求值。

本文将介绍如何使用 C++ 将中缀表达式转换为后缀表达式，并提供完整的代码示例和详细的代码解释，帮助你理解算法的实现过程。

算法步骤

将中缀表达式转换为后缀表达式的算法步骤如下：

从左到右扫描中缀表达式。2. 如果遇到操作数，则直接将其添加到后缀表达式中。3. 如果遇到左括号 (，则将其压入栈中。4. 如果遇到右括号 )，则将栈中的运算符弹出并添加到后缀表达式中，直到遇到左括号为止，并将左括号弹出但不添加到后缀表达式中。5. 如果遇到运算符，则将其与栈顶运算符进行优先级比较： - 如果栈为空或者栈顶运算符为左括号，则直接将该运算符压入栈中。 - 如果该运算符的优先级高于栈顶运算符，则将其压入栈中。 - 如果该运算符的优先级低于或等于栈顶运算符，则将栈中的运算符弹出并添加到后缀表达式中，直到遇到优先级更低的运算符或左括号为止，然后将该运算符压入栈中。6. 扫描完整个中缀表达式后，将栈中剩余的运算符依次弹出并添加到后缀表达式中。

C++ 代码示例cpp#include #include #include #include <unordered_map>

using namespace std;

// 定义运算符优先级映射表unordered_map<char, int> precedence = { {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'(', 0}};

// 将中缀表达式转换为后缀表达式string infixToPostfix(string expression) { stack stackOperator; string postfix = '';

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

    // 如果是字母或数字，直接输出        if (isalnum(c)) {            postfix += c;        } else if (c == '(') {            stackOperator.push(c);        } else if (c == ')') {            // 遇到右括号，将栈中的运算符弹出直到遇到左括号            while (!stackOperator.empty() && stackOperator.top() != '(') {                postfix += stackOperator.top();                stackOperator.pop();            }            stackOperator.pop(); // 弹出左括号        } else {            // 遇到运算符，比较栈顶运算符的优先级            while (!stackOperator.empty() && precedence[stackOperator.top()] >= precedence[c]) {                postfix += stackOperator.top();                stackOperator.pop();            }            stackOperator.push(c);        }    }

// 将栈中剩余的运算符弹出    while (!stackOperator.empty()) {        postfix += stackOperator.top();        stackOperator.pop();    }

return postfix;}

int main() { string expression1 = 'a+b*(c+d/e)'; string expression2 = '-a+b*(-c+d)';

cout << 'Infix expression: ' << expression1 << endl;    string postfix1 = infixToPostfix(expression1);    cout << 'Postfix expression: ' << postfix1 << endl;

cout << 'Infix expression: ' << expression2 << endl;    string postfix2 = infixToPostfix(expression2);    cout << 'Postfix expression: ' << postfix2 << endl;

return 0;}

代码解释

precedence 是一个 unordered_map，用于存储运算符的优先级。- infixToPostfix 函数接受一个字符串类型的参数 expression，表示中缀表达式，并返回一个字符串类型的结果，表示后缀表达式。- 在 infixToPostfix 函数中，使用一个 stack 来存储运算符，使用一个字符串 postfix 来存储后缀表达式。- 遍历中缀表达式，根据不同的字符类型进行处理，并根据算法步骤进行栈操作和字符串拼接。- 最后，将栈中剩余的运算符弹出并添加到后缀表达式中。

总结

本文介绍了如何使用 C++ 将中缀表达式转换为后缀表达式，并提供了完整的代码示例和详细的代码解释。希望本文能够帮助你理解算法的实现过程，并在实际应用中使用该算法解决问题。