文章目录
- 一、栈的基础概念与实现
- 1. 栈的基本操作
- 2. 栈(C++)
- 二、经典应用
- 1. 中缀表达式转后缀表达式
- 1.1 中缀与后缀表达式介绍
- 1.2 转换步骤
- 1.3 代码实现(C++)
- 2. 中缀表达式转前缀表达式
- 2.1 前缀表达式介绍
- 2.2 转换步骤
- 2.3 代码实现(C++)
一、栈的基础概念与实现
栈(Stack)是一种后进先出(LIFO, Last In First Out)的数据结构。它只允许在一端(称为栈顶)进行插入和删除操作。
1. 栈的基本操作
- Push: 将元素压入栈顶。
- Pop: 从栈顶弹出元素。
- Peek/Top: 获取栈顶元素但不删除。
2. 栈(C++)
#include <iostream>
#include <stack>
#include <string>int main() {std::stack<int> s;s.push(10);s.push(20);std::cout << "栈顶元素: " << s.top() << std::endl; // 输出 20s.pop();std::cout << "栈顶元素: " << s.top() << std::endl; // 输出 10return 0;
}
二、经典应用
1. 中缀表达式转后缀表达式
1.1 中缀与后缀表达式介绍
- 中缀表达式: 运算符位于两个操作数之间,例如
A + B
。 - 后缀表达式: 运算符位于操作数之后,例如
AB+
。这种表示法也称为逆波兰表示法(RPN, Reverse Polish Notation)。
1.2 转换步骤
- 初始化两个栈: 运算符栈
operatorStack
和输出栈outputStack
。 - 遍历中缀表达式:
- 遇到操作数时,将其直接添加到输出栈中。
- 遇到左括号时,将其压入运算符栈。
- 遇到右括号时,弹出运算符栈中的运算符并添加到输出栈中,直到遇到左括号为止。
- 遇到运算符时,将其与运算符栈顶的运算符进行优先级比较。如果栈顶运算符优先级较高或相同,则将栈顶运算符弹出并添加到输出栈,重复此过程,直到栈为空或栈顶运算符优先级较低为止。然后,将当前运算符压入运算符栈。
- 将剩余的运算符从运算符栈弹出并添加到输出栈。
1.3 代码实现(C++)
#include <iostream>
#include <stack>
#include <string>int precedence(char op) {if (op == '+' || op == '-') return 1;if (op == '*' || op == '/') return 2;return 0;
}std::string infixToPostfix(const std::string &exp) {std::stack<char> operatorStack;std::string output;for (char c : exp) {if (isalnum(c)) {output += c; // 操作数直接添加到输出中} else if (c == '(') {operatorStack.push(c);} else if (c == ')') {while (!operatorStack.empty() && operatorStack.top() != '(') {output += operatorStack.top();operatorStack.pop();}operatorStack.pop(); // 弹出左括号} else {while (!operatorStack.empty() && precedence(operatorStack.top()) >= precedence(c)) {output += operatorStack.top();operatorStack.pop();}operatorStack.push(c);}}while (!operatorStack.empty()) {output += operatorStack.top();operatorStack.pop();}return output;
}int main() {std::string infix = "A+(B*C-(D/E^F)*G)*H";std::string postfix = infixToPostfix(infix);std::cout << "后缀表达式: " << postfix << std::endl; // 输出 ABC*DEF^/G*-H*+return 0;
}
2. 中缀表达式转前缀表达式
2.1 前缀表达式介绍
- 前缀表达式: 运算符位于操作数之前,例如
+AB
。这种表示法也称为波兰表示法(PN, Polish Notation)。
2.2 转换步骤
- 反转中缀表达式: 将中缀表达式中的操作数和运算符顺序反转,同时将左括号变为右括号,右括号变为左括号。
- 将反转后的中缀表达式转换为后缀表达式。
- 反转后缀表达式,得到的即为前缀表达式。
2.3 代码实现(C++)
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>std::string infixToPrefix(const std::string &exp) {std::string reversedExp = exp;std::reverse(reversedExp.begin(), reversedExp.end());for (char &c : reversedExp) {if (c == '(') c = ')';else if (c == ')') c = '(';}std::string reversedPostfix = infixToPostfix(reversedExp);std::reverse(reversedPostfix.begin(), reversedPostfix.end());return reversedPostfix;
}int main() {std::string infix = "A+(B*C-(D/E^F)*G)*H";std::string prefix = infixToPrefix(infix);std::cout << "前缀表达式: " << prefix << std::endl; // 输出 +A-*BC-/^DEF*GHreturn 0;
}