中缀双目表达式叫做波兰式，后缀双目表达式叫做逆波兰式。

波兰式 逆波兰式

2+3 2 3 +

2+3*5 2 3 5 * +

2*3+5 2 3 * 5 +

2+3*5-6 2 3 5 * + 6 -

2*(3+5) 2 3 5 + *

逆波兰式的作用：计算机在计算一个表达式的时候就没有了优先级的概念，计算的过程简化为从左往右依次从逆波兰式中读取，读取到一个运算符则从其前面取出两个数字做这个运算符的运算，运算结果放置到当前位置，然后在从左至右开始第二次运算，直到算出结果。

比如2+3*5-6-->读取到第一个*则取出3和5做3*5=15，并将15放置到2后面，现在逆波兰式变为2 15 + 6 -，下一次读取到+取出2和15做2+15=17，并将17存放到6前面，逆波兰式又变为17 6 -，读取到-，则取出17和6做减法17-6=11，并将其放置到以前的序列中，计算结束。

给定一个波兰式，将逆波兰式(各个符号之间用空格隔开)输出，假设波兰式在数组a中，逆波兰式最后在数组b中。

思路：从逆波兰式和波兰式对比来看，数字的相对位置总是一致的，然而运算符的位置却不是一致的。运算符的位置满足碰到高优先级的入栈(栈是另外新建的一个数据结构，不是a也不是b)，碰到低优先级的出栈（出栈后就放到b中）。比如读取2+3*5这个波兰式，读取到2直接存放如b中，然后读取+，这个先放入栈中，然后读取3又放入b中，接着读取到*，*的优先级比+高，所以*又在+之后入栈，最后读取5，直接存放如b中，表达式读取完毕，需要将栈中的所有运算符出栈到b中，就得到了：2 3 5 * +的顺序。

要完成这个功能，需要一个栈，而且栈的第一个单元必须放置一个默认的优先级最低的运算符，以保证第一个运算符能够入栈。

关于括号的处理：左括号if语句直接入栈，括号后的表达式按上面的顺序依次入栈或者出栈；碰到右括号则从栈中出栈直到碰到第一个左括号，将左括号从栈中取出这一级括号则处理完毕。

#include 
  
   
#include 
   
     typedef struct st { int maxsize; int top; int *pstack; }stack; void create_stack(stack *s, int ms); void push(stack *s, int x); int pop(stack *s); void clear_stack(stack *s); char read_stack(stack *s); int priority(char ch); void transform(char a[], char b[]); int main() { char a[80], b[200]; printf("Please input expression:"); gets(a); transform(a, b); puts(b); return 0; } void create_stack(stack *s, int ms) { s->maxsize = ms; s->top = -1; s->pstack = (int *)malloc(ms*sizeof(int)); s->pstack[++s->top] = '@'; //这里@被假定为优先级最低的运算符 } void push(stack *s, int x) { if(s->top < s->maxsize-1) s->pstack[++s->top] = x; } int pop(stack *s) { if(s->top != -1) return s->pstack[s->top--]; } char read_stack(stack *s) { return (s->pstack[s->top]); } int priority(char ch) { int flag = 0; switch(ch) { case '+': case '-': flag = 1; break; case '*': case '/': flag = 2; break; default: flag = 0; //@的优先级设置为最低：0 break; } return flag; } void transform(char a[], char b[]) { stack s; int i = 0, j = 0; create_stack(&s, 20); while(a[i]) { if(a[i] >= '0' && a[i] <= '9') { b[j++] = a[i]; } else if(a[i] == '(') push(&s, a[i]); else if(a[i] == ')') { b[j++] = ' '; while(read_stack(&s) != '(') { b[j++] = pop(&s); b[j++] = ' '; } } else { b[j++] = ' '; while(priority(a[i]) <= priority(read_stack(&s))) { b[j++] = pop(&s); b[j++] = ' '; } push(&s, a[i]); } i ++; } while(s.top != 0) //如果判断a[]结束栈中还有运算符则出栈到b[]中 { b[j++] = ' '; b[j++] = pop(&s); } b[j++] = '\0'; //将b转换为字符换 } void clear_stack(stack *s) { s->maxsize = 0; s->top = -1; free(s->pstack); s->pstack = 0; }