对于用低级编程语言是实现对运算式的处理，后缀式（逆波兰式）最为简便。下面是将中缀式（常见运算式）转换为后缀式的算法：
栈底放‘#’，从左至右逐字读取中缀式：
a.当当前字符为数字时，直接输出；
b.当当前字符为"("时，将其压栈；
c.当当前字符为")"时，则弹出堆栈中最上的"("之前的所有运算符并输出，然后删除堆栈中的"(" ；
d.当当前字符为运算符时，则依次弹出堆栈中优先级大于等于当前运算符的(到"("之前为止)，输出，再将当前运算符压栈；
e.当为"#"时，弹出所有栈中的内容输出
中缀式：a*(b+c)/d+e
后缀式：abc+*d/e+
应用实例：
算术表达式的转换
Time Limit: 1000MS Memory limit: 65536K
题目描述
小明在学习了数据结构之后，突然想起了以前没有解决的算术表达式转化成后缀式的问题，今天他想解决一下。
因为有了数据结构的基础小明很快就解出了这个问题，但是他突然想到怎么求出算术表达式的前缀式和中缀式呢？小明很困惑。聪明的你帮他解决吧。
输入
输入一算术表达式，以\'#\'字符作为结束标志。（数据保证无空格,只有一组输入）
输出
输出该表达式转换所得到的前缀式 中缀式 后缀式。分三行输出，顺序是前缀式 中缀式 后缀式。
示例输入
a*b+(c-d/e)*f#
示例输出
+*ab*-c/def a*b+c-d/e*f ab*cde/-f*+
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 struct node 5 { 6 int data; 7 struct node *l; 8 struct node *r; 9 }; 10 char s[101],q1[101],q2[101]; 11 int sp(char ch) 12 { 13 int x; 14 switch(ch) 15 { 16 case '+':x=1;break; 17 case '-':x=1;break; 18 case '*':x=2;break; 19 case '/':x=2;break; 20 default :x=0; 21 } 22 return x; 23 } 24 int i; 25 void change()//将中缀式化为后缀式函数 26 { 27 28 int x=0,y=0; 29 for(i=0; s[i]!='#'; i++) 30 { 31 if(s[i]>='a'&&s[i]<='z') 32 q1[x++]=s[i]; 33 else if(s[i]=='(') 34 q2[y++]=s[i]; 35 else if(s[i]==')') 36 { 37 while(q2[y-1]!='(') 38 { 39 q1[x]=q2[y-1]; 40 x++; 41 y--; 42 } 43 y--; 44 } 45 else if(sp(s[i])==1) 46 { 47 while(y!=0&&q2[y-1]!='(') 48 { 49 q1[x]=q2[y-1]; 50 x++; 51 y--; 52 } 53 q2[y++]=s[i]; 54 } 55 else if(sp(s[i])==2) 56 { 57 while(y!=0&&sp(q2[y-1])==2) 58 { 59 q1[x]=q2[y-1]; 60 x++; 61 y--; 62 } 63 q2[y++]=s[i]; 64 } 65 66 } 67 while(y!=0) 68 { 69 q1[x]=q2[y-1]; 70 x++; 71 y--; 72 } 73 q1[x]='\0'; 74 75 } 76 void pretree(struct node *p)//前序遍历 77 { 78 if(p != NULL) 79 { 80 printf("%c",p->data); 81 pretree(p->l); 82 pretree(p->r); 83 } 84 } 85 void intree(struct node *p)//中序遍历 86 { 87 if(p != NULL) 88 { 89 intree(p->l); 90 printf("%c",p->data); 91 intree(p->r); 92 93 } 94 } 95 int main() 96 { 97 int top=0,j; 98 gets(s); 99 change(); //将中缀式化为后缀式 100 struct node *tree[101]= {NULL},*pi; //建立表达式树，用链栈 101 for( j = 0; j < i; j++) 102 { 103 if(q1[j] >= 'a' && q1[j] <= 'z') 104 { 105 pi = (struct node *)malloc(sizeof(struct node)); 106 pi->data = q1[j]; 107 pi->l = NULL; 108 pi->r = NULL; 109 tree[top++] = pi; 110 } 111 else 112 { 113 pi = (struct node *)malloc(sizeof(struct node)); 114 pi->data = q1[j]; 115 pi->r = tree[top-1]; 116 top--; 117 pi->l = tree[top-1]; 118 top--; 119 tree[top++] = pi; 120 } 121 } 122 pretree(tree[0]); 123 printf("\n"); 124 intree(tree[0]); 125 printf("\n"); 126 puts(q1); //这里可换为后序遍历 127 return 0; 128 }
代码操作归结为：
将中缀式转化为后缀式；
将后缀式转化为表达式树；
将表达式树先序，中序，后序遍历得前缀式，中缀式，后缀式；
如何根据表达式建立一棵树：
我们知道在表达式树中，只有度为2的树杈结点与度为0的叶子节点，并且树杈节点上都存放运算符，叶子节点都存放操作数。比如由表达式1+2*3创建的树是这样的：
每一个叶子结点有一个确定的值，对于每一个运算符结点，也可以看做它代表一个值，其值为左子树的值与右子树的值按照结点中存储的运算符计算后的结果。如结点’+’的值为“1+右子树的值”，而右子树的值为它的左子树的值乘以它的右子树的值，即”2*3”，所以表达式的值就是根节点的值”1+2*3”。
由上述递归的定义不难看出，建立表达式树就是建立树中的每一个结点，将每一个结点链接起来就是整棵树。而在建立深度低的结点时要将其左右指针指向之前建立的深度比它高一级的结点(如’*’要指向’2’和’3’，而’+’又要指向’*’)。这样我们可以用栈来存放每次建立的结点，按照优先级(表达式为中缀型)或顺序扫描表达式(表达式为波兰式与逆波兰式)建立每一个结点。建立结点的顺序即为表达式求值的顺序。如果扫描到操作数则直接新建一个左右指针为空的结点，并压入结点栈中(存放结点指针)。遇到运算符时首先新建一个结点，然后从栈中依次弹出两个结点，并让新建立的结点的左右指针域指向它们。当所有结点建立完毕时，如果表达式没有错误(这里假设输入表达式正确)，这时栈中应该只剩下一个结点，它就是所建立的表达式的根结点。