C语言数据结构-algo3-7.c

blake

1. /* algo3-7.c 表达式求值(范围为int类型,输入负数要用(0-正数)表示) */
   
2. typedef int SElemType; /* 栈元素类型为整型,改进算法3.4 */
   
3. #include"c1.h"
   
4. #include"c3-1.h"
   
5. #include"bo3-1.c"
   
6. 
   
7. SElemType Precede(SElemType t1,SElemType t2) /* 同algo3-6.c */
   
8. { /* 根据教科书表3.1，判断两符号的优先关系 */
   
9.    SElemType f;
   
10.    switch(t2)
    
11.    {
    
12.      case '+':
    
13.      case '-':if(t1=='('||t1=='=')
    
14.                 f='<';
    
15.               else
    
16.                 f='>';
    
17.               break;
    
18.      case '*':
    
19.      case '/':if(t1=='*'||t1=='/'||t1==')')
    
20.                 f='>';
    
21.               else
    
22.                 f='<';
    
23.               break;
    
24.      case '(':if(t1==')')
    
25.               {
    
26.                 printf("ERROR1\n");
    
27.                 exit(ERROR);
    
28.               }
    
29.               else
    
30.                 f='<';
    
31.               break;
    
32.      case ')':switch(t1)
    
33.               {
    
34.                 case '(':f='=';
    
35.                          break;
    
36.                 case '=':printf("ERROR2\n");
    
37.                          exit(ERROR);
    
38.                 default: f='>';
    
39.               }
    
40.               break;
    
41.      case '=':switch(t1)
    
42.               {
    
43.                 case '=':f='=';
    
44.                          break;
    
45.                 case '(':printf("ERROR2\n");
    
46.                          exit(ERROR);
    
47.                 default: f='>';
    
48.               }
    
49.    }
    
50.    return f;
    
51. }
    
52. 
    
53. Status In(SElemType c) /* 几乎与algo3-6.c相同 */
    
54. { /* 判断c是否为运算符 */
    
55.    switch(c)
    
56.    {
    
57.      case'+':
    
58.      case'-':
    
59.      case'*':
    
60.      case'/':
    
61.      case'(':
    
62.      case')':
    
63.      case'=':return TRUE; /* 此句不同于algo3-6.c */
    
64.      default:return FALSE;
    
65.    }
    
66. }
    
67. 
    
68. SElemType Operate(SElemType a,SElemType theta,SElemType b) /* 有改动 */
    
69. {
    
70.    SElemType c;
    
71.    switch(theta)
    
72.    {
    
73.      case'+':c=a+b;
    
74.              break;
    
75.      case'-':c=a-b;
    
76.              break;
    
77.      case'*':c=a*b;
    
78.              break;
    
79.      case'/':c=a/b;
    
80.    }
    
81.    return c;
    
82. }
    
83. 
    
84. SElemType EvaluateExpression() /* 有改动 */
    
85. { /* 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈 */
    
86.    SqStack OPTR,OPND;
    
87.    SElemType a,b,d,x,theta;
    
88.    char c; /* 存放由键盘接收的字符串 */
    
89.    char z[6]; /* 存放整数字符串 */
    
90.    int i;
    
91.    InitStack(&OPTR); /* 初始化运算符栈 */
    
92.    Push(&OPTR,'='); /* =是表达式结束标志 */
    
93.    InitStack(&OPND); /* 初始化运算数栈 */
    
94.    c=getchar();
    
95.    GetTop(OPTR,&x);
    
96.    while(c!='='||x!='=')
    
97.    {
    
98.      if(In(c)) /* 是7种运算符之一 */
    
99.        switch(Precede(x,c))
    
100.        {
     
101.          case'<':Push(&OPTR,c); /* 栈顶元素优先权低 */
     
102.                  c=getchar();
     
103.                  break;
     
104.          case'=':Pop(&OPTR,&x); /* 脱括号并接收下一字符 */
     
105.                  c=getchar();
     
106.                  break;
     
107.          case'>':Pop(&OPTR,&theta); /* 退栈并将运算结果入栈 */
     
108.                  Pop(&OPND,&b);
     
109.                  Pop(&OPND,&a);
     
110.                  Push(&OPND,Operate(a,theta,b));
     
111.        }
     
112.      else if(c>='0'&&c<='9') /* c是操作数 */
     
113.      {
     
114.        i=0;
     
115.        do
     
116.        {
     
117.          z[i]=c;
     
118.          i++;
     
119.          c=getchar();
     
120.        }while(c>='0'&&c<='9');
     
121.        z[i]=0;
     
122.        d=atoi(z); /* 将字符串数组转为整型存于d */
     
123.        Push(&OPND,d);
     
124.      }
     
125.      else /* c是非法字符 */
     
126.      {
     
127.        printf("ERROR3\n");
     
128.        exit(ERROR);
     
129.      }
     
130.      GetTop(OPTR,&x);
     
131.    }
     
132.    GetTop(OPND,&x);
     
133.    return x;
     
134. }
     
135. 
     
136. void main() /* 有改动 */
     
137. {
     
138.    printf("请输入算术表达式,负数要用(0-正数)表示,并以=结束\n");
     
139.    printf("%d\n",EvaluateExpression());
     
140. }
     
141. 

复制代码