栈！！！！

数据结构实验之栈三：后缀式求值

Time Limit: 1000MS Memory limit: 65536K

题目描述

对于一个基于二元运算符的后缀表示式（基本操作数都是一位正整数），求其代表的算术表达式的值。

输入

输入一个算术表达式的后缀式字符串，以‘#’作为结束标志。

输出

求该后缀式所对应的算术表达式的值，并输出之。

示例输入

59*684/-3*+#

示例输出

提示

基本操作数都是一位正整数!

 1 #include<stdio.h>
 2  #include<string.h>
 3  #include<stdlib.h>
 4  typedef struct Node
 5  {
 6      int data;
 7      struct Node *next;
 8  }node;
 9  node *top;
10  void push(int a)
11  {
12      node *p;
13      p=(node *)malloc(sizeof(node));
14      p->data=a;
15      p->next=top->next;
16      top->next=p;
17  }
18  int pop(node *top)
19  {
20      node *p;
21      p=top->next;
22      top->next=p->next;
23      return p->data;
24  }
25  void js(char s)
26  {
27      int n,m;
28      int k;
29      n=pop(top);
30      m=pop(top);
31      if(s=='+')
32         k=m+n;
33      else if(s=='-')
34         k=m-n;
35      else if(s=='*')
36        k=m*n;
37      else if(s=='/')
38        k=m/n;
39      push(k);
40  }
41  int main()
42  {
43      top=(node *)malloc(sizeof(node));
44      top->next=NULL;
45      char s;
46      int a;
47      while((s=getchar())!='#')
48      {
49          if(s=='+'||s=='-'||s=='*'||s=='/')
50              js(s);
51          else if(s>='0'&&s<='9')
52           {
53               a=s-'0';
54               push(a);
55           }
56      }
57     printf("%d
",top->next->data);
58      return 0;
59  }
60

数据结构实验之栈二：一般算术表达式转换成后缀式

Time Limit: 1000MS Memory limit: 65536K

题目描述

对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。

输入

输入一个算术表达式，以‘#’字符作为结束标志。

输出

输出该表达式转换所得到的后缀式。

示例输入

a*b+(c-d/e)*f#

示例输出

ab*cde/-f*+

  1 #include<stdio.h>
  2  #include<stdlib.h>
  3  #include<string.h>
  4  typedef struct Node
  5  {
  6      char data;
  7      struct Node *next;
  8  } node;
  9  node *top;
 10  int push(char s)
 11  {
 12      node *p;
 13      static int n=1;
 14      p=(node *)malloc(sizeof(node));
 15      if(s=='(') n++;
 16      p->data=s;
 17      p->next=top;
 18      top=p;
 19      return n;
 20  }
 21  void pop(char s,int n)
 22  {
 23      node *p;
 24      p=(node *)malloc(sizeof(node));
 25      if(s==')')
 26      {
 27          if(n==2)
 28          {
 29              while(top->data!='(')
 30              {
 31                  p->data=top->data;
 32                  top=top->next;
 33                  printf("%c",p->data);
 34              }
 35          }
 36          else if(n>2)
 37          {
 38              while(n>2)
 39              {
 40                  if(top->data=='(')
 41                  {
 42                      n--;
 43                      top=top->next;
 44                  }
 45                  else
 46                  {
 47                      p->data=top->data;
 48                      top=top->next;
 49                      printf("%c",p->data);
 50                  }
 51              }
 52          }
 53      }
 54      else
 55      {
 56          p->data=top->data;
 57          top=top->next;
 58          printf("%c",p->data);
 59      }
 60  }
 61  int main()
 62  {
 63      node *p;
 64      p=(node *)malloc(sizeof(node));
 65      top=(node *)malloc(sizeof(node));
 66      top=NULL;
 67      char s;
 68      int l=1,i;
 69      while((s=getchar())!='#')
 70      {
 71          if(s=='+'||s=='-'||s=='*'||s=='/')
 72          {
 73              if(s=='-'||s=='+')
 74              {
 75                  if(top!=NULL&&(top->data=='*'||top->data=='/'))
 76                  {
 77                      pop(top->data,l);
 78                      push(s);
 79                  }
 80                  else push(s);
 81              }
 82              else
 83              {
 84                  push(s);
 85              }
 86          }
 87          else if(s=='(')  i=push(s);
 88          else if(s==')')  pop(s,i);
 89          else  printf("%c",s);
 90      }
 91      while(top!=NULL)
 92      {
 93          if(top->data=='(') top=top->next;
 94          else
 95          {
 96              p->data=top->data;
 97              top=top->next;
 98              printf("%c",p->data);
 99          }
100      }
101      printf("
");
102      return 0;
103  } 
104