数据结构与算法——编程作业——第三章 栈与队列

1:中缀表达式的值

总时间限制:

200ms

内存限制:

1024kB

描述

人们熟悉的四则运算表达式称为中缀表达式，例如(23+34*45/(5+6+7))。在程序设计语言中，可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式（又称逆波兰表示法），并最终变为计算机可以直接执行的指令，得到表达式的值。
给定一个中缀表达式，编写程序，利用堆栈的方法，计算表达式的值。

输入

第一行为测试数据的组数N
接下来的N行，每行是一个中缀表达式。表达式中只含数字、四则运算符和圆括号，操作数都是正整数，数和运算符、括号之间没有空格。中缀表达式的字符串长度不超过600。

输出

对每一组测试数据输出一行，为表达式的值

样例输入

3
3+5*8
(3+5)*8
(23+34*45/(5+6+7))

样例输出

43
64
108

提示

注意：运算过程均为整数运算（除法运算'/'即按照C++定义的int除以int的结果，测试数据不会出现除数为0的情况），输出结果也为整数（可能为负）。
中间计算结果可能为负。

这题有点儿变态qaq

解题思路是：中缀表达式-->后缀表达式-->计算后缀表达式

step 1: 中缀表达式-->后缀表达式

中缀表达式a + b*c + (d * e + f) * g，其转换成后缀表达式则为a b c * + d e * f + g * +。

转换过程需要用到栈，具体过程如下：

1）如果遇到操作数，我们就直接将其输出。

2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。

3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。

4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。

5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

step 2:计算后缀表达式

后缀表达式的求值过程为，从左到右扫描后缀表达式：

1）如果遇到操作数，将其压入栈中。

2）如果遇到操作符，则从栈中弹出两个操作数，计算结果，然后把结果入栈。

3）直到遍历完后缀表达式，则计算完成，此时的栈顶元素即为计算结果。

我的代码思路

我在做的时候为了简化代码，直接两大步骤并为一大步骤了，实现思路不变。

具体来说，我用了一个数字栈和一个符号栈来分别储存操作数和操作符；在遇到step1中(3)(4)(5)的“输出/弹出操作符”的情况时，实施类似step2中(2)的做法：从数字栈中弹出两个操作数，从符号栈中弹出一个操作符，计算这三者的运算结果，把结果放回数字栈中；最终，符号栈应该为空，数字栈应该只剩下一个元素，也就是表达式的值，其余情况均为错误输入。

我的代码

1 #include <cstdio>
2 #include <stack>
3 #include <cstring>
4 using namespacestd;
5 
6 //判断运算符号优先级是否满足c1>=c2
7 bool prior(const char c1, const charc2){
8     if((c1=='-'||c1=='+') && (c2=='*'||c2=='/'))
9         return false;
10     else
11         return true;
12 }
13 
14 //函数Op2Num(): 操作两个数字的运算;
15 void Op2Num(stack<int> & num, stack<char> &op){
16     int num1, num2;//取数字栈顶的两个操作数
17     num1 =num.top(); num.pop();
18     num2 =num.top(); num.pop();
19     switch(op.top()){//操作数字栈顶两数字并重新入栈
20         case '+': num.push(num2+num1); break;
21         case '-': num.push(num2-num1); break;
22         case '*': num.push(num2*num1); break;
23         case '/': num.push(num2/num1); break;
24         default: printf("something wrong in Op2Num
");
25 }
26     op.pop();//弹出符号栈顶符号
27 }
28 
29 //函数OpeNum():
30 //cur传入字符')','+','-','*','/',表明调用本函数的触发条件
31 void OpeNum(stack<int> & num, stack<char> & op, charcur){
32     while(!op.empty() && op.top()!='(' &&prior(op.top(), cur))
33 Op2Num(num, op);
34     switch(cur){
35         case ')':
36             if(op.top() == '(')
37                 op.pop();//弹左括号
38             break;
39         default:
40             op.push(cur);//当前符号入符号栈
41 }
42     return;
43 }
44 
45 //从字符串中取数字
46 int GetNum(char * str, int &i){
47     int temp = 0;
48     while(str[i]>='0' && str[i]<='9'){
49         temp = temp*10 + str[i] - '0';
50         ++i;
51 }
52     --i;
53     returntemp;
54 }
55 
56 //表达式结束，所有符号弹栈
57 void PopAll(stack<int> & num, stack<char> &op){
58     while(!op.empty())
59 Op2Num(num, op);
60     return;
61 }
62 
63 //中缀表达式运算
64 int CalNifix(char *str){
65     stack<int> num;//数字栈
66     stack<char> op;//符号栈
67     for(int i=0; str[i]; ++i){
68         switch(str[i]){
69             case '(':
70                 op.push('('); break;//左括号入栈
71             case ')':
72             case '+':
73             case '-':
74             case '*':
75             case '/':
76                 OpeNum(num, op, str[i]); break;//操作运算
77             default:
78                 num.push(GetNum(str, i));//取数字入数字栈
79 }
80 }
81     PopAll(num, op);//表达式结束，所有符号弹栈
82     return num.top();//返回运算结果
83 }
84 
85 intmain() {
86     intT;
87     scanf("%d", &T);
88     while(T--){
89         char str[650];//储存中缀表达式
90         scanf("%s", str);
91         printf("%d
", CalNifix(str));
92 }
93     return 0;
94 }

我的代码是按照自己的思路写的，大家当然可以把step1和step2分开做、依次做，我想可能会更容易理解，结构也更清晰。

但是无论如何，请一定一定不要直接copy，一定一定要自己看懂思路后，独立写一遍，这样才能学到东西嘛！加油！

1 #include <cstdio>
2 #include <algorithm>
3 using namespacestd;
4 
5 intmain(){
6     intn, k;
7     int t[1000010];
8     scanf("%d %d", &n, &k);
9     for(int i=0; i<n; ++i)
10         scanf("%d", t+i);
11     for(int i=k; i<=n; ++i)
12         printf("%d ",* min_element(t+i-k, t+i));
13     printf("");
14     for(int i=k; i<=n; ++i)
15         printf("%d ",* max_element(t+i-k, t+i));
16     printf("");
17     return 0;
18 }

1 #include <cstdio>
2 #include <algorithm>
3 using namespacestd;
4 
5 intmain(){
6     intn, k, t_min, t_max;
7     int t[1000010], m[1000010];
8     scanf("%d %d", &n, &k);
9     for(int i=0; i<n; ++i)
10         scanf("%d", t+i);
11     for(int i=k; i<=n; ++i){
12         t_min = t_max = t[i-k];
13         for(int j=i-k+1; j<i; ++j){
14             t_min =min(t_min, t[j]);
15             t_max =max(t_max, t[j]);
16 }
17         m[i] =t_max;
18         printf("%d ", t_min);
19 }
20     printf("");
21     for(int i=k; i<=n; ++i)
22         printf("%d ", m[i]);
23     printf("");
24     return 0;
25 }

1 #include <iostream>
2 using namespacestd;
3 
4 #define N 1000010
5 
6 //输出滑动窗口最小值
7 void PrintMin(int * num, const int n, const intk){
8     //p_min[head...tail]储存当前窗口内的单调序列
9     int p_min[n], head=0, tail=-1;
10     for(int i=0; i<n; ++i){
11         while(head<=tail && num[i]<=num[p_min[tail]])
12             --tail;//队尾大元素元素出队
13         p_min[++tail] = i;//元素i入队尾
14         while(p_min[head]<=i-k)
15             ++head;//队头窗口外元素出队
16         if(i>=k-1)//输出当前窗口最小值
17             cout << num[p_min[head]] << ' ';
18 }
19     cout <<endl;
20 }
21 
22 //输出滑动窗口最大值
23 void PrintMax(int * num, const int n, const intk){
24     int p_max[n], head=0, tail=-1;
25     for(int i=0; i<n; ++i){
26         while(head<=tail && num[i]>=num[p_max[tail]])
27             --tail;
28         p_max[++tail] =i;
29         while(p_max[head]<=i-k)
30             ++head;
31         if(i>=k-1)
32             cout << num[p_max[head]] << ' ';
33 }
34     cout <<endl;
35 }
36 
37 intmain() {
38     intn, k, num[N];
39     cin >> n >>k;
40     for(int i=0; i<n; ++i)
41         cin >>num[i];
42 PrintMin(num, n, k);
43 PrintMax(num, n, k);
44     return 0;
45 }

1 #include <iostream>
2 using namespacestd;
3 
4 #define N 1000010
5 
6 bool MyMin(int a, int b){return a<=b;}
7 bool MyMax(int a, int b){return a>=b;}
8 
9 void Print(int * num, const int n, const int k, bool (*f)(int,int)){
10     //p[head...tail]储存当前窗口内的单调序列
11     int p[n], head=0, tail=-1;
12     for(int i=0; i<n; ++i){
13         while(head<=tail &&f(num[i],num[p[tail]]))
14             --tail;//队尾元素出队
15         p[++tail] = i;//元素i入队尾
16         while(p[head]<=i-k)
17             ++head;//队头窗口外元素出队
18         if(i>=k-1)//输出当前窗口最值
19             cout << num[p[head]] << ' ';
20 }
21     cout <<endl;
22 }
23 
24 intmain() {
25     intn, k, num[N];
26     cin >> n >>k;
27     for(int i=0; i<n; ++i)
28         cin >>num[i];
29 Print(num, n, k, MyMin);
30 Print(num, n, k, MyMax);
31     return 0;
32 }

1 #include <stdio.h>
2 using namespacestd;
3 
4 #define N 1000010
5 
6 bool MyMin(int a, int b){return a<=b;}
7 bool MyMax(int a, int b){return a>=b;}
8 
9 inline void Print(int * num, const int n, const int k, bool (*f)(int,int)){
10     //p[head...tail]储存当前窗口内的单调序列
11     int p[n], head=0, tail=-1;
12     for(int i=0; i<n; ++i){
13         while(head<=tail &&f(num[i],num[p[tail]]))
14             --tail;//队尾元素出队
15         p[++tail] = i;//元素i入队尾
16         while(p[head]<=i-k)
17             ++head;//队头窗口外元素出队
18         if(i>=k-1)//输出当前窗口最值
19             printf("%d ", num[p[head]]);
20 }
21     printf("");
22 }
23 
24 intmain() {
25     intn, k, num[N];
26     scanf("%d %d", &n, &k);
27     for(int i=0; i<n; ++i)
28         scanf("%d", num+i);
29 Print(num, n, k, MyMin);
30 Print(num, n, k, MyMax);
31     return 0;
32 }