carysu@126.com

carysu@126.com
posts - 11, comments - 0, trackbacks - 0, articles - 0

数据结构后缀表达式转换

Posted on 2011-10-30 10:35 susu 阅读(451) 评论(0)  编辑 收藏 引用
  1
  2
  3
  4#include <stdio.h>
  5#define MAX 100
  6char exp[MAX];
  7
  8#if 0
  9void tr ans()
 10{
 11    char stack[MAX];
 12    char str[] = "(56-20)/(4+2)#";
 13    char ch;
 14    int sum, i, j, t, top = 0;
 15    /*
 16    printf("***************************************\n");
 17    printf("* 输入一个求值的表达式,以#结束。只能包含+,-,*,/运算符和正整数 *\n");
 18    printf("***************************************\n");
 19    printf("算术表达式:");
 20    
 21    i = 0;
 22    do
 23    {
 24        //i++;
 25        //scanf("%c ", &str[i]);
 26
 27    }while (0);
 28    //}while (str[i++] != '#' && i != MAX);
 29    sum = i;
 30    t = 1;
 31    i = 1;
 32    ch = str[i];
 33    i++;*/

 34    i = 0;
 35    t = 1
 36    top = 0
 37    while (str[i] != '\0')
 38    {
 39        ch = str[i];
 40        switch (ch)
 41        {
 42        case '(':
 43            top++;
 44            stack[top] = ch;
 45            break;
 46        case ')':
 47            while (stack[top] != '(')
 48            {
 49                exp[t] = stack[top];
 50                top--;
 51                t++;
 52            }

 53            top--;
 54            break;
 55        case '+':
 56        case '-':
 57            while (top != 0 && stack[top] != '(')
 58            {
 59                exp[t] = stack[top];
 60                top--;
 61                t++;
 62            }

 63            top++;
 64            stack[top] = ch;
 65            break;
 66        case '*':
 67        case '/':
 68            while (stack[top] == '*' || stack[top] == '/')
 69            {
 70                exp[t] = stack[top];
 71                top--;
 72                t++;
 73            }

 74            top++;
 75            stack[top] = ch;
 76            break;
 77        case ' ':
 78            break;
 79        default:
 80            while (ch >= '0' && ch <= '9')
 81            {
 82                exp[t] = ch;
 83                t++;
 84                ch = str[i];
 85                i++;
 86
 87            }

 88            i--;
 89            exp[t] = '#';
 90            t++;
 91        }

 92        ch = str[i];
 93        i++;
 94    }

 95    while (top != 0)
 96    {
 97        exp[t] = stack[top];
 98        t++;
 99        top--;
100    }

101    exp[t] = '#';
102    /*
103    printf("\n\t原来表达式:");
104    for (j = 1; j < sum; j++)
105    {
106        printf("%c ", str[j]);
107        
108    }*/

109    for (j = 1; j < t; j++)
110        printf("%c ", exp[j]);
111}

112#endif
113void trans()
114{
115    char stack[MAX];
116    char str[] = "(56-20)/(4+2)";
117    char ch;
118    int  s_i;
119    int  j;
120    int  e_t;
121    int  top;
122    s_i = 0;
123    while (str[s_i] != '\0')
124    {
125        printf("str[%d] = %c\n", s_i, str[s_i]);
126        s_i++;
127    }

128    printf("\n");
129    printf("\n");
130    printf("\n");
131    
132#if 1
133    s_i = 0;
134    e_t = 0;
135    top = -1;
136    ch = str[s_i];
137    while (str[s_i] != '\0')
138    {
139        ch = str[s_i];
140        s_i++;
141#if 1
142        switch (ch)
143        {
144        case '(':
145            top++;
146            stack[top] = ch;
147            break;
148        case ')':
149            while (stack[top] != '(')
150            {
151                exp[e_t] = stack[top];
152                top--;
153                e_t++;
154            }

155            top--;
156            break;
157        case '+':
158        case '-':
159            while (top != 0 && stack[top] != '(')
160            {
161                exp[e_t] = stack[top];
162                top--;
163                e_t++;
164            }

165            top++;
166            stack[top] = ch;
167            break;
168        case '*':
169        case '/':
170            if ((stack[top] == '*'|| (stack[top] == '/'))
171            {
172                exp[e_t] = stack[top];
173                top--;
174                e_t++;
175            }

176            top++;
177            stack[top] = ch;
178            break;
179        case ' ':
180            break;
181        default:
182            while (ch >= '0' && ch <= '9')
183            {
184                exp[e_t] = ch;
185                //printf("exp[%d] = %c\n", e_t, exp[e_t]);
186                e_t++;
187                ch = str[s_i];
188                s_i++;
189            }

190            s_i--;
191            exp[e_t] = '#';
192            e_t++;
193            break;
194        }

195                
196#endif
197    }

198    while (top != -1)
199    {
200        exp[e_t] = stack[top];
201        e_t++;
202        top--;
203    }

204    exp[e_t] = '#';
205    
206    /*
207    printf("\n\t原来表达式:");
208    for (j = 1; j < sum; j++)
209    {
210        printf("%c ", str[j]);
211        
212    }*/

213        printf("\n");
214    for (j = 0; j < e_t; j++)
215    {
216        printf("%c",exp[j]);
217    }

218    printf("\n");
219    //printf("exp[%d] = %c\n ",j, exp[j]);
220#endif
221}

222void compvalue()
223{
224    float stack[MAX];
225    float d;
226    char ch;
227    int t = 1;
228    int top = -1;
229    ch = exp[t];
230    //t++; /* 56#20#-4#2#+/ */
231    d = 0;
232    while (ch != '$')
233    {
234        switch (ch)
235        {
236        case '+':
237            stack[top - 1= stack[top - 1+ stack[top];
238            top--;
239            printf("stack[%d] = %f \n", top, stack[top]);
240            break;
241        case '-':
242            stack[top - 1= stack[top - 1- stack[top];
243            top--;
244            printf("stack[%d] = %f \n", top, stack[top]);
245            break;
246        case '*':
247            stack[top - 1= stack[top - 1* stack[top];
248            top--;
249            printf("stack[%d] = %f \n", top, stack[top]);
250            break;
251        case '/':
252            if (stack[top] != 0)
253            {
254                stack[top - 1= stack[top - 1]/stack[top];
255            }

256            else 
257            {
258                printf("\n\t除0错误!\n");
259                return;
260            }

261            top--;
262            printf("stack[%d] = %f \n", top, stack[top]);
263            break;
264        case '#':
265            top++;
266            stack[top] = d;
267            printf("stack [%d] = %f \n", top, stack[top]);
268            d = 0;
269            break;
270        default:
271            if (ch >= '0' && ch <= '9')
272            {
273                d = 10 * d + ch - '0';  
274                printf("d = %f\n", d);
275            }

276            break;
277        }

278        t++;
279        ch = exp[t];
280    }

281    printf("\n计算结果:stack[%d] = %f\n",top, stack[top]);
282}

283
284void main()
285{
286    //int j;
287    trans();
288    /*
289    exp[1] = '5';
290    exp[2] = '6';
291    exp[3] = '#';
292    exp[4] = '2';
293    exp[5] = '0';
294    exp[6] = '#';
295    exp[7] = '-';
296    exp[8] = '4';
297    exp[9] = '#';
298    exp[10] = '3';
299    exp[11] = '#';
300    exp[12] = '+';
301    exp[13] = '/';
302    exp[14] = '$';
303    printf("\n");
304    for (j = 1; j <15; j++)
305        printf("%c", exp[j]);
306    printf("\n");*/

307    //compvalue();
308}

309





只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理