算法流程转载自http://www.cnblogs.com/stay-foolish/archive/2012/04/25/2470590.html
这道题，蛮经典的—— ——
题意：表达式由单字母变量和双目四则运算符及"("和")" 组成，设计算法求表达式的逆波兰式。
逆波兰表达式也称为后缀表达式，它将一个算数表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行，如下图所示：
算法流程：
(1)首先，需要分配2个栈，栈s1用于临时存储运算符（含一个结束符号），此运算符在栈内遵循越往栈顶优先级越高的原则；栈s2用于输入逆波兰式，为方便起见，栈s1需先放入一个优先级最低的运算符，在这里假定为'#'；
(2)从中缀式的左端开始逐个读取字符x，逐序进行如下步骤：
1.若x是操作数，则分析出完整的运算数（在这里为方便，用字母代替数字），将x直接压入栈s2；
2.若x是运算符，则分情况讨论：
若x是'('，则直接压入栈s1；
若x是')'，则将距离栈s1栈顶的最近的'('之间的运算符，逐个出栈，依次压入栈s2，此时抛弃'('；
若x是除'('和')'外的运算符，则再分如下情况讨论：
若当前栈s1的栈顶元素为'('，则将x直接压入栈s1；
若当前栈s1的栈顶元素不为'('，则将x与栈s1的栈顶元素比较，若x的优先级大于栈s1栈顶运算符优先级，则将x直接压入栈s1。否者，将栈s1的栈顶运算符弹出，压入栈s2中，直到栈s1的栈顶运算符优先级别低于（不包括等于）x的优先级，或栈s2的栈顶运算符为'('，此时再则将x压入栈s1;
(3)在进行完(2)后，检查栈s1是否为空，若不为空，则将栈中元素依次弹出并压入栈s2中（不包括'#'）；
(4)完成上述步骤后，栈s2便为逆波兰式输出结果。但是栈s2应做一下逆序处理，因为此时表达式的首字符位于栈底；
代码： #include<stdio.h> #include<stdlib.h> #include<string.h> #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef char SElemType; typedef struct{ SElemType *base; SElemType *top; int stacksize; }sqstack; void InitStack(sqstack &s) { s.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!s.base) exit(0); s.top=s.base; s.stacksize=STACK_INIT_SIZE; } void Push(sqstack &s,SElemType e) { if(s.top-s.base>=s.stacksize) { s.base=(SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(s.base) exit(0); s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; } *s.top++=e; } void Pop(sqstack &s,SElemType &e) { if(s.top==s.base) exit(0); e=*--s.top; } SElemType Top(sqstack &s) { SElemType e; if(s.top==s.base) exit(0); e=*(s.top-1); return e; } int StackEmpty(sqstack &s) { if(s.top==s.base) return 1; else return 0; } char *nbl(char *e) /* 返回表达式e的逆波兰式 */ { //栈s1用于存放运算符，栈s2用于存放逆波兰式 sqstack s1,s2; InitStack(s1); InitStack(s2); //假设字符'#'是运算级别最低的运算符，并压入栈s1中 Push(s1,'#'); //p指针用于遍历传入的字符串，ch用于临时存放字符,length用于计算字符串长度 char *p=e,ch; int length=0; for(;*p!='\0';p++)//逐个字符访问 { switch(*p) { //遇'('则直接入栈s1 case '(': Push(s1,*p); break; //遇')'则将距离栈s1栈顶的最近的'('之间的运算符，逐个出栈，依次送入栈s2,此时抛弃'(' case ')': while(Top(s1)!='(') { Pop(s1,ch); Push(s2,ch); } Pop(s1,ch); break; //遇下列运算符，则分情况讨论： //1.若当前栈s1的栈顶元素是'('，则当前运算符直接压入栈s1； //2.否则，将当前运算符与栈s1的栈顶元素比较，若优先级较栈顶元素大，则直接压入栈s1中, // 否则将s1栈顶元素弹出，并压入栈s2中，直到栈顶运算符的优先级别低于当前运算符，然后再将当前运算符压入栈s1中 case '+': case '-': for(ch=Top(s1);ch!='#';ch=Top(s1)) { if(ch=='(') { break; } else { Pop(s1,ch); Push(s2,ch); } } Push(s1,*p); length++; break; case '*': case '/': for(ch=Top(s1);ch!='#'&&ch!='+'&&ch!='-';ch=Top(s1)) { if(ch=='(') { break; } else { Pop(s1,ch); Push(s2,ch); } } Push(s1,*p); length++; break; //遇操作数则直接压入栈s2中 default: Push(s2,*p); length++; } } //若栈s1非空，则将栈中元素依次弹出并压入栈s2中 while(!StackEmpty(s1)&&Top(s1)!='#') { Pop(s1,ch); Push(s2,ch); } //最后将栈s2输出，逆序排列成字符串; char *result; result=(char *)malloc(sizeof(char)*(length+1)); result+=length; *result='\0'; result--; for(;!StackEmpty(s2);result--) { Pop(s2,ch); *result=ch; } ++result; return result; } int main() { char *sr; printf("请输入你的表达式\n"); scanf("%s",sr); printf("%s\n",nbl(sr)); }