第二十八讲 栈和队列6（视频+课件+源代码）

530876864

强烈支持楼主ing……

demonzjf

激动人心，无法言表！ 跪舔圣天玄武大帝，西风发财红中战神。才华横溢，帅到掉渣的小甲鱼大神。

demonzjf

demonzjf 发表于 2015-3-20 15:44
激动人心，无法言表！ 跪舔圣天玄武大帝，西风发财红中战神。才华横溢，帅到掉渣的小甲鱼大神。

鱼币不够怎么办。

鱼儿爱学习

shi_xin398 发表于 2013-9-16 13:55
小甲鱼 不知道你能不能看到我的回复
你的程序有问题
当输入2*3/4

乘除的优先级是一样的吧

鱼儿爱学习

小甲鱼老师，这个鱼币怎么赚到呀？没有鱼币的童鞋好伤心啊

2413780002

强烈支持楼主ing……

妖龙腾空

真贵，想看和上一章合在一起的代码

18983422070

。。。。。。。。。。。

fzquchs

蜗牛般的速度慢慢前行着，真痛苦！！！

小猪发飙

加油

liyuanjun

小甲鱼，你在这一讲的视频里说会把完整的源代码放在论坛里，可是这个代码还只是你视频里讲的那些啊！ 能不能把中缀表达式变成后缀表达式，然后再计算出来的代码分享一下，我水平比较低，谢谢了

yinjia哈哈

好贵啊

yinjia哈哈

有没有两个程序合并的啊

天下无敌小萨萨

求合并的代码

ai1361720220000

小甲鱼，你程序中当乘除或者左括号直接进栈，那么就会有一个问题，如果栈里面本来就有一个*或者/，不应该也要把之前那个*和/输出吗？比如说，输入2*2*2 你的程序结果就会是2 2 2 * *，但是不应该是2 2 * 2 *吗？
对于2+2+2，结果是2 2 + 2 +，这和程序结果一样，是因为程序中有输出栈里之前优先级高的。我觉得在乘除那边应该也要这么做吧？~

sevennight1989

学习中，我的代码调试老是出问题

WorlD_HellO

哪里有一次下完所有课程视频和代码的压缩包

yzw

不是说有合并之后的代码吗，怎么没有啊！

创建 和 计算 逆波兰式子的函数用到的结构体不一样啊，一个用double型、一个用char型
难道我要定义两个结构体，写两个Pop 两个Push 两个InitStack 两个 StackLen吗？求解答。

今天就是因为一直想不明白这点才决定买VIP下载代码看看的，结果发现没有这个代码

秋名山老司机

这个是头文件的内容：

1. //栈操作基本表达式运算头文件
   
2. //创建人：mingming
   
3. //创建时间：2017.8.4
   
4. //最后修改时间：2017.8.4
   
5. 
   
6. 
   
7. #ifndef CACULATE_H
   
8. #define CACULATE_H
   
9. 
   
10. typedef double ElemType;       //数字栈空间元素类型
    
11. typedef char   ElemType2;      //运算符栈空间元素类型
    
12. #define MAX_INIT_SIZE 20       //初始化的栈空间
    
13. #define NEW_SIZE 10                           //每次新增的栈空间
    
14. #define MAX_BUFFER 10          //数字识别的缓冲区
    
15. 
    
16. //定义一个栈
    
17. typedef struct
    
18. {
    
19.         ElemType *base;
    
20.         ElemType *top;
    
21.         int StackSize;
    
22. } sqStack;
    
23. 
    
24. bool InitStack(sqStack *s)
    
25. {
    
26.         s->base = new ElemType[MAX_INIT_SIZE];
    
27.         if(!s->base)
    
28.                 return false;
    
29.         s->top = s->base;
    
30.         s->StackSize = MAX_INIT_SIZE;
    
31.         return true;
    
32. }
    
33. 
    
34. bool push(sqStack *s , ElemType e)
    
35. {
    
36.         if((s->top - s->base) >= s->StackSize)
    
37.         {
    
38.                 s->base = (ElemType *)realloc(s->base , ( NEW_SIZE + s->StackSize )* sizeof( ElemType ));
    
39.                 if( !s->base )
    
40.                         return false;
    
41.                 s->top = s->base + s->StackSize;
    
42.                 s->StackSize += NEW_SIZE;
    
43.         }
    
44. 
    
45.         *(s->top) = e;
    
46.         s->top++;
    
47.         return true;
    
48. }
    
49. 
    
50. bool pop(sqStack *s ,ElemType *e)
    
51. {
    
52.         if(s->top == s->base)
    
53.                 return false;
    
54.         s->top--;
    
55.         *e = *s->top;
    
56.         return true;
    
57. }
    
58. //求栈当前长度
    
59. int StackLen(sqStack s)
    
60. {
    
61.         return ( s.top - s.base );
    
62. }
    
63. 
    
64. 
    
65. //对上面的各个方法进行重载
    
66. typedef struct
    
67. {
    
68.         ElemType2 *base;
    
69.         ElemType2 *top;
    
70.         int StackSize;
    
71. } midStack;
    
72. 
    
73. bool InitStack(midStack *s)
    
74. {
    
75.         s->base = new ElemType2[MAX_INIT_SIZE];
    
76.         if(!s->base)
    
77.                 return false;
    
78.         s->top = s->base;
    
79.         s->StackSize = MAX_INIT_SIZE;
    
80.         return true;
    
81. }
    
82. 
    
83. bool push(midStack *s , ElemType2 e)
    
84. {
    
85.         if((s->top - s->base) >= s->StackSize)
    
86.         {
    
87.                 s->base = (ElemType2 *)realloc(s->base , ( NEW_SIZE + s->StackSize )* sizeof( ElemType2 ));
    
88.                 if( !s->base )
    
89.                         return false;
    
90.                 s->top = s->base + s->StackSize;
    
91.                 s->StackSize += NEW_SIZE;
    
92.         }
    
93. 
    
94.         *(s->top) = e;
    
95.         s->top++;
    
96.         return true;
    
97. }
    
98. 
    
99. bool pop(midStack *s ,ElemType2 *e)
    
100. {
     
101.         if(s->top == s->base)
     
102.                 return false;
     
103.         s->top--;
     
104.         *e = *s->top;
     
105.         return true;
     
106. }
     
107. //求栈当前长度
     
108. int StackLen(midStack s)
     
109. {
     
110.         return ( s.top - s.base );
     
111. }
     
112. 
     
113. #endif

复制代码

这个是cpp文件的内容，用的时候要包含上面头文件

1. #include<iostream>
   
2. #include<ctype.h>
   
3. #include"Caculate.h"
   
4. 
   
5. #define MAXBUFFER 50  //存放后缀表达式的最大缓冲区长度
   
6. 
   
7. 
   
8. //中缀表达式转换为后缀表达式
   
9. void MidtoLast(char *lastbuf)
   
10. {
    
11.         std::cout << "请输入表达式！以#作为结束标志\n";
    
12.         midStack stack;
    
13.         InitStack(&stack);     //操作符的栈初始化
    
14. 
    
15.         int i=0;
    
16.         char c;
    
17.         char temp;
    
18.         std::cin.get(c);
    
19.         while( '#' != c )       //输入以#作为结束符
    
20.         {
    
21.                 if( isdigit(c) || c=='.' )         //对读取到的数字处理，使得数字放在一起，并且一个数字后面有一个空格
    
22.                 {
    
23.                         while(isdigit(c) || c=='.')
    
24.                         {
    
25.                                 lastbuf[i++] = c;
    
26.                                 lastbuf[i] = ' ';
    
27.                                 std::cin.get(c);   
    
28.                         }
    
29.                                 i++;                         //保护一个数字完了之后的空格不变
    
30.                 }
    
31.                
    
32.                 switch( c )
    
33.                 {
    
34.                         case '+':                        // + 只要前面有非括号运算符，就应该先出栈
    
35.                                 if(stack.top == stack.base)
    
36.                                 {
    
37.                                         push( &stack , c );
    
38.                                 }
    
39.                                 else
    
40.                                 {
    
41.                                         do
    
42.                                         {
    
43.                                                 pop( &stack , &temp );
    
44.                                                 if( '(' == temp )
    
45.                                                 {
    
46.                                                         push( &stack , temp );
    
47.                                                 }
    
48.                                                 else
    
49.                                                 {
    
50.                                                         lastbuf[i++] = temp;
    
51.                                                         lastbuf[i++] = ' ';
    
52.                                                 }
    
53.                                         }while( '(' != temp && StackLen(stack));
    
54.                                         push( &stack , c );
    
55.                                 }
    
56.                                 break;
    
57.                         case '-':                       //  - 只要前面有非括号运算符，就应该先出栈
    
58.                                 if(stack.top == stack.base)
    
59.                                 {
    
60.                                         push( &stack , c );
    
61.                                 }
    
62.                                 else
    
63.                                 {
    
64.                                         do
    
65.                                         {
    
66.                                                 pop( &stack , &temp );
    
67.                                                 if( '(' == temp )
    
68.                                                 {
    
69.                                                         push( &stack , temp );
    
70.                                                 }
    
71.                                                 else
    
72.                                                 {
    
73.                                                         lastbuf[i++] = temp;
    
74.                                                         lastbuf[i++] = ' ';
    
75.                                                 }
    
76.                                         }while( '(' != temp && StackLen(stack));
    
77.                                         push( &stack , c );
    
78.                                 }
    
79.                                 break;
    
80.                         case '*':                           //   * / 需要那顺序计算，谁在先，先算谁
    
81.                                 if(stack.top == stack.base)
    
82.                                 {
    
83.                                         push( &stack , c );
    
84.                                 }
    
85.                                 else
    
86.                                 {
    
87.                                         pop( &stack , &temp );
    
88.                                         if( '*'==temp || '/'==temp  )
    
89.                                         {
    
90.                                                 lastbuf[i++] = temp;
    
91.                                                 lastbuf[i++] = ' ';
    
92.                                         }
    
93.                                         else
    
94.                                         {
    
95.                                                 push( &stack , temp );
    
96.                                         }
    
97.                                                 push( &stack , c );
    
98.                                 }
    
99.                                 break;
    
100.                         case '/':                    //   * / 需要那顺序计算，谁在先，先算谁
     
101.                                 if(stack.top == stack.base)
     
102.                                 {
     
103.                                         push( &stack , c );
     
104.                                 }
     
105.                                 else
     
106.                                 {
     
107.                                         pop( &stack , &temp );
     
108.                                         if( '*'==temp || '/'==temp  )
     
109.                                         {
     
110.                                                 lastbuf[i++] = temp;
     
111.                                                 lastbuf[i++] = ' ';
     
112.                                         }
     
113.                                         else
     
114.                                         {
     
115.                                                 push( &stack , temp );
     
116.                                         }
     
117.                                                 push( &stack , c );
     
118.                                 }
     
119.                                 break;
     
120.                         case '(':
     
121.                                 push(&stack , c);
     
122.                                 break;
     
123.                         case ')':       //括号配对，知道碰见左括号
     
124.                                 pop( &stack , &temp );
     
125.                                 while( '(' != temp )
     
126.                                 {
     
127.                                         lastbuf[i++] = temp;
     
128.                                         lastbuf[i++] = ' ';
     
129.                                         pop( &stack , &temp );
     
130.                                 }
     
131.                                 break;
     
132.                 }
     
133.                 if( '#' != c)     // 如果前面数字处理时已经读到了#，就不需要再读了
     
134.                 {
     
135.                         std::cin.get(c);
     
136.                 }
     
137.                
     
138.         }
     
139.         while( stack.top != stack.base )    //把栈里面没有用到的符号全部弹出来
     
140.         {
     
141.                 pop( &stack , &lastbuf[i++] );
     
142.                 lastbuf[i++] = ' ';
     
143.         }
     
144.         lastbuf[i] = '\0';       //数组最后的结束符，防止内存泄漏
     
145. }
     
146. 
     
147. ElemType caculate(char *lastbuf)
     
148. {
     
149.         sqStack s;
     
150.         InitStack( &s );
     
151.         int i = 0,bufcount=0;
     
152.         double d,e;
     
153. 
     
154.        
     
155.         char c , str[MAX_BUFFER];
     
156.         c = lastbuf[bufcount++];
     
157. 
     
158.         while(c != '\0')
     
159.         {
     
160.                 while( isdigit(c) || c=='.')          //数字处理，把连续的数字转换为一个double型
     
161.                 {
     
162.                         str[i++] = c;
     
163.                         str[i] = '\0';
     
164.                         if( i>=10 )
     
165.                         {
     
166.                                 std::cout << "输入的数字位数过多！\n";
     
167.                         }
     
168.                         c = lastbuf[bufcount++];
     
169.                         if(  ' '== c )           // 碰见空格说明一个数字完了
     
170.                         {
     
171.                                 d = atof(str);
     
172.                                 push( &s , d );
     
173.                                 i = 0;
     
174.                                 break;
     
175.                         }
     
176.                 }
     
177. 
     
178.                 switch( c )
     
179.                 {
     
180.                         case '+':
     
181.                                 pop( &s , &e );
     
182.                                 pop( &s , &d);
     
183.                                 push(&s , d+e);
     
184.                                 break;
     
185.                         case '-':
     
186.                                 pop( &s , &e );
     
187.                                 pop( &s , &d );
     
188.                                 push(&s , d-e);
     
189.                                 break;
     
190.                         case '*':
     
191.                                 pop( &s , &e );
     
192.                                 pop( &s , &d );
     
193.                                 push(&s , d*e);
     
194.                                 break;
     
195.                         case '/':
     
196.                                 pop( &s , &e );
     
197.                                 pop( &s , &d );
     
198.                                 if( e != 0 )
     
199.                                 {
     
200.                                         push(&s , d/e);
     
201.                                 }
     
202.                                 else
     
203.                                 {
     
204.                                         std::cout << "除数为0，错误！\n";
     
205.                                         return -1;
     
206.                                 }
     
207.                                 break;
     
208.                 }
     
209.                 c = lastbuf[bufcount++];  
     
210.         }
     
211.         pop(&s , &d);      //最终计算结果弹出到 d 中   
     
212.         return d;
     
213. }
     
214. 
     
215. 
     
216. int main()
     
217. {
     
218.         char lastbuf[MAXBUFFER]; //后缀表达式缓冲区
     
219. 
     
220.         MidtoLast(lastbuf);     //中缀转后缀
     
221.        
     
222.         std::cout << "运算结果为" << caculate(lastbuf) << std::endl;
     
223. 
     
224.         return 0;
     
225. }

复制代码

还有注意一下，甲鱼老师的中缀转换后缀有些问题，加减法 或者 乘除法 需要按照顺序求，就是说需要先判断站定是否有相同优先级或高优先级的运算符，如果有，就要先出栈，然后再进行压栈操作！

秋名山老司机

yzw 发表于 2017-5-27 20:16
不是说有合并之后的代码吗，怎么没有啊！

创建 和 计算 逆波兰式子的函数用到的结构体不一样啊，一个用d ...

对的，需要两个栈，可以看我在下面发的代码 ！