c++用栈输出中缀表达式的前缀和后缀表达式

### C++ 使用栈实现中缀表达式转换为前缀和后缀表达式的算法 #### 一、基本概念 在计算机科学中，表达式可以分为三种形式：中缀表达式、前缀表达式和后缀表达式。其中： - **中缀表达式** 是人们常用的书写方式，操作符位于两个操作数之间。 - **前缀表达式** 的操作符位于其操作数之前。 - **后缀表达式** 的操作符位于其操作数之后。 为了将中缀表达式分别转化为前缀和后缀表达式，通常会借助栈这一数据结构完成运算优先级的处理[^1]。 --- #### 二、中缀到后缀的转化算法 以下是基于栈的数据结构实现中缀表达式转后缀表达式的具体逻辑： 1. 初始化一个空栈用于存储操作符。 2. 遍历输入的中缀表达式字符串中的每一个字符。 3. 如果当前字符是一个操作数，则直接将其加入输出队列。 4. 如果当前字符是左括号 `(` ，则压入栈中。 5. 如果当前字符是右括号 `)` ，则依次弹出栈顶元素直到遇到对应的左括号 `( )` 并丢弃该左括号。 6. 如果当前字符是操作符（如 `+`, `-`, `*`, `/`），则比较它与栈顶操作符的优先级： - 若栈为空或者栈顶操作符优先级低于当前操作符，则将当前操作符压入栈； - 否则，持续弹出栈顶操作符至输出队列，直至满足条件再压入当前操作符。 7. 当遍历完成后，如果栈不为空，则逐一弹出剩余的操作符并加入输出队列。 ```cpp #include <iostream> #include <stack> #include <string> using namespace std; int precedence(char op) { if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; return 0; // For other characters or parentheses. } bool isOperator(char c) { return (c == '+' || c == '-' || c == '*' || c == '/'); } void infixToPostfix(string s, string &result) { stack<char> st; for (char ch : s) { if (ch >= 'a' && ch <= 'z') result += ch; // Operand found else if (ch == '(') st.push(ch); // Push to stack else if (ch == ')') { // Pop until matching ( while (!st.empty() && st.top() != '(') { result += st.top(); st.pop(); } if (!st.empty()) st.pop(); // Remove the '(' from stack } else { // Operator encountered while (!st.empty() && precedence(st.top()) >= precedence(ch)) { result += st.top(); st.pop(); } st.push(ch); } } while (!st.empty()) { // Remaining operators in stack result += st.top(); st.pop(); } } ``` 上述代码实现了从中缀表达式到后缀表达式的转换功能[^2]。 --- #### 三、中缀到前缀的转化算法 对于从前缀表达式的构建，可以通过以下步骤逆向思维解决： 1. 将整个中缀表达式反转。 2. 把所有的左括号替换为右括号，反之亦然。 3. 利用标准的中缀转后缀方法得到结果后再整体翻转即可获得最终的前缀表示。 ```cpp // Helper function to reverse a string string reverseString(const string& str) { string reversedStr = ""; for (auto it = str.rbegin(); it != str.rend(); ++it) { char currentChar = *it; if (currentChar == '(') currentChar = ')'; else if (currentChar == ')') currentChar = '('; reversedStr += currentChar; } return reversedStr; } void infixToPrefix(string s, string &prefixResult) { string reversedInfix = reverseString(s); string postfixReversed; infixToPostfix(reversedInfix, postfixReversed); prefixResult = reverseString(postfixReversed); } ``` 此部分展示了如何通过简单的变换技巧来获取前缀表达式的结果。 --- #### 四、综合示例程序 下面提供了一个完整的C++程序框架，演示了如何利用栈将给定的中缀表达式同时转换成前缀和后缀两种形式。 ```cpp int main() { string infixExpression = "a+b*c+(d*e+f)*g"; string postfixResult = "", prefixResult = ""; infixToPostfix(infixExpression, postfixResult); cout << "Postfix Expression: " << postfixResult << endl; infixToPrefix(infixExpression, prefixResult); cout << "Prefix Expression: " << prefixResult << endl; return 0; } ``` 运行以上代码将会打印出相应的前后缀版本作为验证依据。 ---