一，逆波兰表达式的定义
什么是逆波兰表达式。可能很多人会有一个疑问，这里举个例子说明一下，对于（1-2）*（4+5）这个表达式的结果，我相信很多人就异口同声地说出来肯定是-9，但是对于机器语言是怎样实现的。这个时候机器语言就需要一定的规则和复杂性来解决这个问题。波兰逻辑学家发明了一种不需要括号的后缀表达式，我们通常称之为逆波兰表达式（RPN）。
对于（1-2）*（4+5）来说，如果用逆波兰表示法，应该是这样：1 2 - 4 5 + * 。逆波兰表示法也成为后缀表达法。
正常的表达式转换为逆波兰表达式举例如下：
a + b ----> a b +
a+(b-c) -----> a b c - +
a+(b-c)*d -----> a b c - d * +
a+d*(b-c) ------> a d b c - * +
二，分析
图1 第一步操作（1-2）的实现
在图1中可以看到，数字1和2进栈，遇到减号运算符则弹出两个元素进行运算并把结果入栈。这个时候如图中右边的那个栈底元素为-1，即完成了这一操作。
图2 第二步（4+5）的操作
在图2中可以看到，数字4和5入栈，遇到加号运算符则弹出两个元素，相加后将结果9入栈，就是图2中右边栈的结果。
图3 第三步-1与9乘积
第三步，乘法运算符，将9和-1弹出栈进行乘法计算，此时栈空并无数据压栈，-9为最终运算结果。
三，代码实现
本代码实现的功能是：1，实现对逆波兰输入的表达式进行计算；2，支持带小数点的数据
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 #define MAXBUFFER 10 typedef double ElemType; typedef struct { ElemType *base; ElemType *top; int stackSize; }sqStack; 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; } 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++; } 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; char c; double d,e; char str[MAXBUFFER]; int i = 0; InitStack( &s ); printf("请按照逆波兰表达式输入待计算数据，数据与运算符之间用空格隔开，以#为结束标志：\n"); scanf("%c", &c); while( c != '#') { while( isdigit(c) || c == '.') //用于过滤数字 { str[i++] = c; str[i] = '\0'; if( i >= 10) { printf("出错：输入的单个数据过大！\n"); return -1; } scanf("%c", &c); if( c == ' ') { d = atof(str); Push(&s, d); i = 0; break; } } switch( c ) { case '+': Pop(&s, &e); Pop(&s, &d); Push(&s, d+e); break; case '-': Pop(&s, &e); Pop(&s, &d); Push(&s, d-e); break; case '*': Pop(&s, &e); Pop(&s, &d); Push(&s, d*e); break; case '/': Pop(&s, &e); Pop(&s, &d); if( e!=0) { Push(&s,d/e); } else { printf("\n出错：除数为零！\n"); return -1; } break; } scanf("%c", &c); } Pop(&s, &d); printf("\n最终的计算结果为： %f\n", d); return 0; }
（1-2）*（4+5） 最后的实现结果为下图：
5-（6+7）*8 +9/4的结果效果图为
