首页 > 代码库 > 中缀表达式转换为后缀表达式的算法

中缀表达式转换为后缀表达式的算法

1、从左而右对算数表达式进行扫描,每次读入一个字符s1[i];

2、若遇到数字或小数点,则立即写入s2[i],若遇算数运算符,将“ ”(空格)写入s2[i];

3、遇到左括号“(”则压栈;

4、若遇算术运算符,如果它们的优先级比栈顶元素高,则直接进栈,否则弹出栈顶元素输出到s2[i],直到新栈顶元素的优先级比它低,然后将它压栈;

5、若遇到右括号“)”,则将栈顶元素输出到s2[i],直到栈顶元素为“(”,然后相互抵消;当扫描到“#”符号,表明表达式串已全部输入,将栈中的运算符全部输出到s2[i],并删除栈顶元素。  

 1 int is_op(char op)
 2  {
 3    switch(op)
 4   { case +:
 5     case -:
 6     case *:
 7     case /:return 1;
 8     default:return 0;
 9     }
10  }
11 /****************************/
12 /*   判断运算符的优先级     */
13 /****************************/
14 int priority(char op)
15    {
16      switch(op)
17        {
18           case (:return 0;
19           case +:
20           case -:return 1;
21           case *:
22           case /:return 2;
23         default: return -1;
24         }
25   }
26 
27 /*********************************/
28 /*中缀表达式,转换为后缀表达式   */
29 /*********************************/
30 void postfix(char e[],char f[])
31  {seqstack opst;
32   int i,j;
33   initstack(&opst);
34   push(&opst,\0);
35   i=j=0;
36   while (e[i]!=\0)
37    { if ((e[i]>=0 && e[i]<=9) || e[i]==.)
38            f[j++]=e[i];                     /*数字*/
39       else if (e[i]==()                /*左括号*/
40                push(&opst,e[i]);
41            else if (e[i]==))           /*右括号*/
42               { while (stacktop(&opst)!=()
43                         f[j++]=pop(&opst);
44                   pop(&opst);            /*‘(‘出栈*/
45                }
46            else if (is_op(e[i]))         /* ‘+ ,-, *, /‘ */
47                   {f[j++]= ;           /*用空格分开两个操作数*/
48                    while (priority(stacktop(&opst))>=priority(e[i]))
49                        f[j++]=pop(&opst);
50 
51                    push(&opst,e[i]);     /*当前元进栈*/
52                    }
53        i++;  /*处理下一元*/
54     }
55 
56     while (!stackempty(&opst))
57         f[j++]=pop(&opst);
58     f[j]=\0;
59   }

 

中缀表达式转换为后缀表达式的算法