在这篇博客中,我们将深入分析一个使用C++编写的栈和表达式计算程序。该程序不仅实现了基本的栈操作,还提供了中缀表达式转后缀表达式和删除堆栈中的元素等实用功能。通过逐一讲解每个函数的功能,我们将更全面地理解这个程序的实现。
资源获取:
-
官方途径:点击博主头像,主页下载资源,需花费积分!
-
个人途径:公众号:每日推荐系列,回复【表达式转换】免费获取!
核心数据结构
1. 栈的实现
struct Node { ... };
struct Stack { ... };
-
Node结构:表示栈的元素,包含一个整数类型的数据和指向下一个结点的指针。
-
Stack结构:自定义栈,包含栈顶指针和栈的大小。提供了基本的入栈、出栈、获取栈顶元素、判断栈是否为空等操作。
详细功能解析
1. 中缀表达式转后缀表达式(主要功能函数 ①)
string zhuanhuan(const string& infix) { //方法都大差不差
string postfix;
Stack operatorStack;
for (char ch : infix) {
if (isdigit(ch)) {
postfix += ch;
}
else if (ch == '(') {
operatorStack.Push(ch);
}
else if (ch == ')') {
while (......略......) {
......略......
}
if (......略......) {
......略......
}
}
else {
while (!operatorStack.IsEmpty() && operatorStack.Top() != '(' &&
......略......
}
operatorStack.Push(ch);
}
}
while (!operatorStack.IsEmpty()) {
......略......
}
return postfix;
}
主要函数过程是遍历中缀表达式,使用栈辅助转换。数字直接输出,左括号入栈,右括号弹出栈元素直到遇到左括号,运算符按照优先级处理。
效果图如下:
2. 删除堆栈中的元素(主要功能函数 ②)
void Delete(int value) { //删除指定元素
......略......
while (!IsEmpty()) {
int topValue = Top();
Pop();
if (topValue == value) {
......略......
}
else {
......略......
}
}
if (!found) {
cerr << "未找到要删除的元素" << endl;
}
else {
......略......
}
while (!reversedValues.empty()) {
......略......
cout << endl;
}
}
};
删除堆栈中的元素,使用临时栈将不需要删除的元素暂存,输出删除的元素,最终恢复原始栈的值。
效果图如下:
3. 表达式计算(非主要功能)
double EvaluatePostfix(const std::string& postfix) {
std::stack<double> operandStack;
for (char ch : postfix) {
if (std::isdigit(ch) || (ch == '.')) {
......略......
}
else if (ch == ' ') {
#####略######
}
else { //俩俩的算,运算之后再次push进去
######略#######
switch (ch) {
case '+':
operandStack.push(a + b);
break;
case '-':
operandStack.push(a - b);
break;
case '*':
operandStack.push(a * b);
break;
case '/':
operandStack.push(a / b);
break;
}
}
}
return operandStack.top();
}
遍历后缀表达式,使用栈存储操作数,遇到运算符则弹出栈顶两个元素进行计算,将结果压入栈中。
4.其他函数:
4.1. Stack Pushand()
Stack Pushand() {
Stack stack;
// ... 省略部分代码 ...
return stack;
}
- 用户输入堆栈数据个数,并逐个输入数字,构建堆栈。
- 输出堆栈中的值,并返回构建好的堆栈。
4.2. void Printf()
和 void Printf_2()
void Printf() {
// ... 省略部分代码 ...
}
void Printf_2() {
// ... 省略部分代码 ...
}
Printf
:打印主菜单,显示功能选项。Printf_2
:打印功能结束提示。
4.3. void choice_1()
和 void choice_2()
void choice_1() {
// ... 省略部分代码 ...
}
void choice_2() {
// ... 省略部分代码 ...
}
choice_1
:执行中缀表达式转后缀表达式的操作,输出后缀表达式和计算结果。choice_2
:执行删除堆栈中元素的操作,输出删除后的堆栈。
主函数如下:
int main() {
int choice;
do {
Printf();
cout << "请输入选择:";
cin >> choice;
switch (choice) {
case 1:
choice_1();
break;
case 2:
choice_2();
break;
case 0:
break;
default:
cout << "无效的选择,请重新输入" << endl;
Printf_2();
}
} while (choice != 0);
return 1111111111111111111;
}
感谢分享这篇有关C/C++数据结构的文章,涵盖了栈的基本操作、中缀表达式转后缀表达式、删除堆栈中的元素以及表达式的计算等方面的内容。如果读者想深入学习相关主题,以下是一些额外的资源和知识点,以及网址链接:
1. 堆栈相关资源:
- C++ 标准模板库 (STL) - stack:C++中标准库提供的堆栈容器的文档。
- C++ 标准模板库 (STL) - vector:与堆栈有关的底层数据结构之一。
- GeeksforGeeks - Stack Data Structure:GeeksforGeeks 上关于堆栈数据结构的详细教程和实现。
2. 中缀表达式转后缀表达式:
- Shunting Yard Algorithm:维基百科上关于Shunting Yard算法的介绍。
- 中缀表达式转后缀表达式算法:GeeksforGeeks 上的中缀到后缀的算法和实现。
3. C++ 表达式计算:
- C++ 中的字符串流 (Stringstream):用于将字符串转换为其他数据类型,对表达式计算很有用。
- C++ 中的 switch 语句:用于处理不同运算符的计算。
4. 其他相关资源:
- C++ Primer (书籍):Stanley B. Lippman等人编写的 C++ 入门经典。
- LeetCode:在线刷题平台,提供丰富的数据结构和算法问题,适合提高编程能力。
5. 相关知识点的网址链接:
- C++ 中文网:提供了丰富的C++学习资源和实例。
- Stack Overflow:程序员问答社区,可以在这里提问和查找与编程相关的问题。
希望这些资源能够帮助读者更深入地学习和理解C/C++数据结构及相关算法。