一，在上篇博文中讨论了逆波兰表达式的计算问题，在这里讨论一下中缀表达式如何转换为后缀表达式
问题示例：如何将1+(2-3)*4+10/5 转换为后缀表达式 1 2 3 - 4 * + 10 5 / +这样的输出
问题分析：
第一步，首先遇到第一个输入是数字1，数字在后缀表达式中都是直接输出，接着是符号“+”入栈
第二步，第三个字符是“（”，依然是符号，这个时候将此符号入栈，接着是数字2，直接输出，然后是符号“-”，这个时候符号仍然入栈
第三步，接下来是数字3，输出，紧跟着是“）”，此时，我们需要匹配栈里的“（”，然后再匹配前将栈顶数据依次出栈：
第四步，紧接着是符号“*”，直接入栈：
第五步，遇到数字4，直接输出，之后是符号“+”，此时栈顶元素是符号“*”，按照先乘除后加减原理，此时栈顶的乘号优先级比即将入栈的加号要大，所以出栈。而栈中的第二个元素是加号，按照先到先后的原则，这个时候“+”也要出栈。
第六步，紧接着是数字10，直接输出，最后是符号“/”，进栈：
第七步，最后一个数字5，这个时候直接输出5，但是栈里仍然有数据，此时可以将栈中符号依次出栈。
二，代码分析：
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 #define MAXBUFFER 10 typedef char ElemType; typedef struct { ElemType *base; ElemType *top; int stackSize; }sqStack; void InitStack(sqStack *s) { s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if( !s->base ) exit(0); s->top = s->base; s->stackSize = STACK_INIT_SIZE; } void Push(sqStack *s, ElemType e) { //如果栈满一定要增加空间，所以在之前要做一个判断 if( s->top - s->base >= s->stackSize) { s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT)* sizeof(ElemType)); if(!s->base) exit(0); s->top = s->base + s->stackSize; s->stackSize = s->stackSize + STACKINCREMENT; } *(s->top) = e; s->top++; } void Pop(sqStack *s, ElemType *e) { if( s->top == s->base) return; *e = *--(s->top); //将栈顶元素弹出并修改栈顶指针 } int StackLen(sqStack s) { return (s.top - s.base); } int main() { sqStack s; ElemType c,e; InitStack( &s ); printf("请输入中缀表达式，以#为结束标志："); scanf("%c", &c); while( c != '#') { if( c >= '0' && c <= '9') { printf("%c", c); } else if( ')' == c ) { Pop(&s, &e); while('(' != e) { printf("%c", e); Pop(&s, &e); } } else if( '+' == c || '-' == c) { if( !StackLen(s) ) { Push(&s, c); } else { do { Pop(&s, &e); if( '(' == e) { Push(&s, e); } else { printf("%c", e); } }while( StackLen(s) && '(' != e); Push(&s, c); } } else if( '*' == c || '/' == c || '(' == c) { Push(&s, c); } else { printf("输入错误，请重新输入!\n"); return -1; } scanf("%c", &c); } while( StackLen(s)) { Pop( &s, &e); printf("%c", e); } return 0; }
最后的结果
大家可以看到这样的结果直接连在一起了，很难分辨出来是123还是1 2 3，这个时候就要在输出做一个改动，将printf("%c"改为printf("%c "，加了一个空格，但是出现了这样的结果：
这样可以看到10被拆分成了1 0，显然这样是不合理的。此时再修改程序，将主函数main修改如下：
int main() { sqStack s; ElemType c,e; InitStack( &s ); printf("请输入中缀表达式，以#为结束标志："); scanf("%c", &c); while( c != '#') { while( c >= '0' && c <= '9') { printf("%c", c); scanf("%c",&c); if( c<'0' || c>'9') { printf(" "); } } if( ')' == c ) { Pop(&s, &e); while('(' != e) { printf("%c ", e); Pop(&s, &e); } } else if( '+' == c || '-' == c) { if( !StackLen(s) ) { Push(&s, c); } else { do { Pop(&s, &e); if( '(' == e) { Push(&s, e); } else { printf("%c ", e); } }while( StackLen(s) && '(' != e); Push(&s, c); } } else if( '*' == c || '/' == c || '(' == c) { Push(&s, c); } else if( '#' == c) { break; } else { printf("输入错误，请重新输入!\n"); return -1; } scanf("%c", &c); } while( StackLen(s)) { Pop( &s, &e); printf("%c ", e); } return 0; }
最终得出想要的满意结果：
