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

blake

1. /* algo3-6.c 表达式求值（输入、输出和中间结果均只能是0～9） */
   
2. typedef char SElemType;
   
3. #include"c1.h"
   
4. #include"c3-1.h"
   
5. #include"bo3-1.c"
   
6. 
   
7. SElemType Precede(SElemType t1,SElemType t2)
   
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("ERROR3\n");
    
46.                          exit(ERROR);
    
47.                 default: f='>';
    
48.               }
    
49.    }
    
50.    return f;
    
51. }
    
52. 
    
53. Status In(SElemType c)
    
54. { /* 判断c是否为运算符 */
    
55.    switch(c)
    
56.    {
    
57.      case'+':
    
58.      case'-':
    
59.      case'*':
    
60.      case'/':
    
61.      case'(':
    
62.      case')':
    
63.      case'#':return TRUE;
    
64.      default:return FALSE;
    
65.    }
    
66. }
    
67. 
    
68. SElemType Operate(SElemType a,SElemType theta,SElemType b)
    
69. {
    
70.    SElemType c;
    
71.    a=a-48;
    
72.    b=b-48;
    
73.    switch(theta)
    
74.    {
    
75.      case'+':c=a+b+48;
    
76.              break;
    
77.      case'-':c=a-b+48;
    
78.              break;
    
79.      case'*':c=a*b+48;
    
80.              break;
    
81.      case'/':c=a/b+48;
    
82.    }
    
83.    return c;
    
84. }
    
85. 
    
86. SElemType EvaluateExpression() /* 算法3.4 */
    
87. { /* 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈 */
    
88.    SqStack OPTR,OPND;
    
89.    SElemType a,b,c,x,theta;
    
90.    InitStack(&OPTR);
    
91.    Push(&OPTR,'#');
    
92.    InitStack(&OPND);
    
93.    c=getchar();
    
94.    GetTop(OPTR,&x);
    
95.    while(c!='#'||x!='#')
    
96.    {
    
97.      if(In(c)) /* 是7种运算符之一 */
    
98.        switch(Precede(x,c))
    
99.        {
    
100.          case'<':Push(&OPTR,c); /* 栈顶元素优先权低 */
     
101.                  c=getchar();
     
102.                  break;
     
103.          case'=':Pop(&OPTR,&x); /* 脱括号并接收下一字符 */
     
104.                  c=getchar();
     
105.                  break;
     
106.          case'>':Pop(&OPTR,&theta); /* 退栈并将运算结果入栈 */
     
107.                  Pop(&OPND,&b);
     
108.                  Pop(&OPND,&a);
     
109.                  Push(&OPND,Operate(a,theta,b));
     
110.                  break;
     
111.        }
     
112.      else if(c>='0'&&c<='9') /* c是操作数 */
     
113.      {
     
114.        Push(&OPND,c);
     
115.        c=getchar();
     
116.      }
     
117.      else /* c是非法字符 */
     
118.      {
     
119.        printf("ERROR4\n");
     
120.        exit(ERROR);
     
121.      }
     
122.      GetTop(OPTR,&x);
     
123.    }
     
124.    GetTop(OPND,&x);
     
125.    return x;
     
126. }
     
127. 
     
128. void main()
     
129. {
     
130.    printf("请输入算术表达式（中间值及最终结果要在0～9之间），并以#结束\n");
     
131.    printf("%c\n",EvaluateExpression());
     
132. }
     
133. 

复制代码