ACM刷题之路(十一)堆、栈、队列实现表达式转换

简介: ACM刷题之路(十一)堆、栈、队列实现表达式转换

这是《数据结构》这门课的课后练习题,很典型的一道题,总结记录一下


题目:表达式转换

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:

输入在一行中给出不含空格的中缀表达式,可包含+-*\以及左右括号(),表达式不超过20个字符。

输出格式:

在一行中输出转换后的后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。

输入样例:

2+3*(7-4)+8/4

输出样例:

2 3 7 4 - * + 8 4 / +

比如a+b*c+(d*e+f)*g

string类型读入

如果遇到字母直接入队列

乘法除法优先级比加减法要高

优先级高的入站

优先级相等或者低的,先把高的入队列,再把当前的入栈

如果遇到‘(’直接入栈

如果遇到‘)’ 在堆栈中往头找,直到找到‘(’为止,并且删除堆栈中的‘(’

1. #include<iostream>
2. #include<string>
3. #include<queue>
4. #include<stack>
5. using namespace std;
6. 
7. int main(){
8. 
9.     stack<string> s1;
10.     queue<string> q1;
11. while (!s1.empty())
12.         s1.pop();//初始化堆栈
13. while (!q1.empty())
14.         q1.pop();//初始化队列
15. 
16.     string s;
17. getline(cin, s);//输入
18. int len = s.size(), num = 0, i, j;
19. 
20. for (i = 0; i < len; i++){
21.         string ts = "";
22. char c = s[i], prc = s[i - 1];//c代表当前字符  prc代表前面一个字符
23. if ((c == '+' || c == '-') && (!i || prc == '(') || (c >= '0' && c <= '9'))
24.         {//如果当前字符是数字或者第一个字符或者前面是左括号 直接入队列
25. if (c != '+') ts += c;
26. while (s[i + 1] == '.' || s[i + 1] >= '0' && s[i + 1] <= '9')//数字不一定是个位数
27.                 ts += s[++i];//数字整体写入到ts的string中
28.             q1.push(ts);//进入队列
29.         }
30. else if (c == '+' || c == '-')
31.         {
32. int flag = 1;//flag符号控制输入 避免如(-4)这样的情况出错
33. while (flag)
34.             {
35. if (s1.empty() || s1.top() == "(")//如遇到(-4)这样的情况退出
36.                     s1.push(ts + c), flag = 0;//如果顶部的优先级比当前的小,进入
37. else
38.                 {
39.                     q1.push(s1.top());//在压入加减之前,如果顶部是乘除,需要先拿掉
40.                     s1.pop();
41.                 }
42.             }
43.         }
44. else if (c == '*' || c == '/')
45.         {
46. int flag = 1;
47. while (flag)
48.             {
49. if (s1.empty() || s1.top() == "(" || s1.top() == "+" || s1.top() == "-")
50.                     s1.push(ts + c), flag = 0;//如果顶部优先级比当前的小,就压入
51. else
52.                 {
53.                     q1.push(s1.top());//否则先把优先级高的压入队列
54.                     s1.pop();
55.                 }
56.             }
57.         }
58. else if (c == '(')//左括号直接进入堆栈
59.             s1.push(ts + c);
60. else if (c == ')')//右括号直接循环到遇到左括号为止
61.         {
62. int flag = 1;
63. while (flag)
64.             {
65.                 string tp = s1.top();
66. if (tp == "(") s1.pop(), flag = 0;//遇到左括号直接退出
67. else
68.                 {
69.                     q1.push(s1.top());//没找到继续进入队列
70.                     s1.pop();
71.                 }
72.             }
73.         }
74.     }
75. while (!s1.empty())
76.     {
77.         q1.push(s1.top());//剩余的全部依次压入堆栈
78.         s1.pop();
79.     }
80. if (!q1.empty())
81.     { //c_str()作用是将string转化为C语言的字符串
82. printf("%s", q1.front().c_str()); q1.pop();
83.     }//否则string类型无法用%s这样输出
84. while (!q1.empty())
85.     {
86. printf(" %s", q1.front().c_str()); q1.pop();
87.     }
88. puts("");
89. return 0;
90. }

 


相关文章
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
4天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
3月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
332 9
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
116 21
|
3月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。

热门文章

最新文章