数据结构专项训练-栈

求前缀表达式的值

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如2+3*(7-4)+8/4的前缀表达式是：+ + 2 * 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。

输入格式:

输入在一行内给出不超过30个字符的前缀表达式，只包含+、-、*、/以及运算数，不同对象（运算数、运算符号）之间以空格分隔。

输出格式:

输出前缀表达式的运算结果，保留小数点后1位，或错误信息"ERROR"。

样例输入与输出：

序号	输入	输出
1	+ + 2 * 3 - 7 4 / 8 4	13.0
2	/ -25 + * - 2 3 4 / 8 4	12.5
3	/ 5 + * - 2 3 4 / 8 2	ERROR
4	+10.23	10.2

这里就不按照惯例给出建议的测试用例了，直接用题目中给的4个就可以了。

下面给出代码:

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 
  5 #define MAXSIZE 30
  6 
  7 typedef double DateType;
  8 
  9 typedef struct
 10 {
 11     DateType date[MAXSIZE];
 12     int top;
 13 }Zhan, *PZ;
 14 
 15 void Push(PZ S, DateType n)
 16 {
 17     S->top++;
 18     S->date[S->top] = n;
 19 }
 20 
 21 DateType Pop(PZ S)
 22 {
 23     DateType m = S->date[S->top];
 24     S->top--;
 25     return m;
 26 }
 27 
 28 int main()
 29 {
 30     Zhan Z;
 31     PZ p = &Z;
 32     p->top = -1;
 33     char str[31];
 34     double num;
 35     gets(str);
 36     int i;
 37     int size = strlen(str);
 38     for (i = size - 1; i >= 0; i--)
 39     {
 40         if (str[i] >= '0'&&str[i] <= '9')
 41         {
 42             num = str[i] - '0';
 43             int k = 10;
 44             for (i = i - 1; i >= 0; i--)
 45             {
 46                 if ((str[i] >= '0'&&str[i] <= '9') || str[i] == '.')
 47                 {
 48                     if (str[i] >= '0'&&str[i] <= '9')
 49                     {
 50                         num = num + (str[i] - '0')*k;
 51                         k = k * 10;
 52                     }
 53                     else
 54                     {
 55                         num /= k;
 56                         k = 1;
 57                     }
 58                 }
 59                 else if (str[i] == '-')
 60                 {
 61                     num = -num;
 62                 }
 63                 else break;
 64             }
 65             Push(p, num);
 66         }
 67         else if (str[i] == ' ')
 68         {
 69             continue;
 70         }
 71         else
 72         {
 73             if (p->top >= 1)
 74             {
 75                 double a, b, s;
 76                 a = Pop(p);
 77                 b = Pop(p);
 78                 if (str[i] == '+')
 79                 {
 80                     s = a + b;
 81                 }
 82                 else if (str[i] == '-')
 83                 {
 84                     s = a - b;
 85                 }
 86                 else if (str[i] == '*')
 87                 {
 88                     s = a * b;
 89                 }
 90                 else
 91                 {
 92                     if (b == 0)
 93                     {
 94                         printf("ERROR
");
 95                         return 0;
 96                     }
 97                     else s = a / b;
 98                 }
 99                 Push(p, s);
100             }
101             else
102             {
103                 printf("ERROR
");
104                 return 0;
105             }
106         }
107     }
108     if (p->top == 0) printf("%.1f
", p->date[p->top]);
109     else printf("ERROR
");
110     system("pause");
111     return 0;
112 }

写的比较好的就是在一个for循环中再嵌套一个for循环，而且变量还是i

Pop Sequence

Given a stack which can keep

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000):

Output Specification:

For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.

Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

YES
NO
NO
YES
NO


说明：该题目就是要求1到N依次入栈，出栈随机，而得到与输入相同的队列，如果能得到，则输出YES，否则输出NO

代码如下：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define MAXSIZE 1000
 4 
 5 typedef int DateType;
 6 typedef struct
 7 {
 8     DateType date[MAXSIZE];
 9     int top;
10 }Zhan,*PZ; 
11 
12 void Push(PZ S,char n)//入栈
13 {
14     S->top++;
15     S->date[S->top] = n;
16 }
17 
18 void Pop(PZ S)//出栈
19 {
20     S->top--;
21 }
22 
23
24 int main()
25 {
26     int m,n,k,i;
27     scanf("%d %d %d",&m, &n, &k); //m为栈的最大值，n为输出的队列长度，k为测试样例个数
28     for (i = 0; i < k; i++)
29     {
30         Zhan Z; 
31         PZ p = &Z;
32         p->top = -1; //对栈定义及初始化
33         int a[1000]; //用来存放每组样例
34         int g;
35         for (g = 0; g < n; g++)   //初始化每个样例
36         {
37             scanf("%d", &a[g]);
38         }
39         int t = 0, num = 1;  //t用来检索数组a当前的数据位置，num为依次入栈的自然数据
40         while (t < n)                   
41         {
42             if (a[t] == num && p->top < m - 1) //如果当前自然数据等于当前检索的样例的a[t]值，且栈未满，即可通过入栈再出栈完成当前自然数字
43             {
44                 t++;
45                 num++;
46             }
47             else if (p->top > -1 && p->top < m - 1 && a[t] == p->date[p->top]) //如果栈顶数字等于检索样例a[t]的值，则可出栈
48             {
49                 Pop(p);
50                 t++;
51             }
52             else if (num != a[t] && p->top < m - 1) //如果当前自然数据不等于当前检索的a[t]，且栈未满,则将该自然数据入栈
53             {
54                 Push(p, num);
55                 num++;
56             }
57             else break; //若上述的情况均不成立，则说明该样例已经不是正确的，可以结束检索，退出循环
58         }
59         if (t < n) printf("NO
");//检索没进行完，循环中途退出，说明样例不正确
60         else printf("YES
");
61     }
62     system("pause");
63     return 0;
64 }