首页 > 代码库 > 利用逆波兰(Reverse Polish Notation, RPN)的后缀表达法计算四则运算表达式
利用逆波兰(Reverse Polish Notation, RPN)的后缀表达法计算四则运算表达式
如果是单纯的加减运算表达式，非常简单，依次处理表达式的头字符就可以了。
但是对于四则运算来说，有括号，又有先乘除，后加减使得表达式处理变得负责。
20世纪50年代，波兰逻辑学家Jan Lukasiewicz发明了不需要括号的后缀表达式，精妙地解决的这个问题。
比如说
char sInput[]="9+(3-1)*3+8/2"; //output 931-3*+82/+
经过转换成 931-3×+82/+，然后从头开始遍历每个字符，当遇到运算符的时候，就把该运算符的前两个数进行操作，比如说遇到第一个“-”，然后做“3-1=2”，然后把运算结果放回去，变成了“923X+82/+”,接着遇到"X"的时候，在运算"2×3=6",把6放回去变成“96+82/+”，如此类推。
之所以叫后缀表达式，就是因为运算符都是出现在数字之后的。如果用stack数据结构，那就很容易算出最后结果。
另外一个问题就是如何把我们熟悉的“中缀表达式”变换成“后缀表达式”
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于找顶符号（乘除优先加减）则栈顶元素依次出找并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
具体实现思路可以参考 这里
下面是用C语言实现的一个思路，因为我也是临时学了2小时C语言（大学里面学的谭XX课本，早就忘记了！！），里面写的并不严谨，只是给C语言学习者提供一个参考。
说句题外话，用别的胶水语言实现起来会非常容易，但是我觉得用C语言对内存进行微操编程，利用各种巧妙算法，才是最带感的，大多数代码种植农民，包括我，其实也就是一个需求实现业务员而已，根本不能称为代码手工艺者！
stack数据结构的代码是参考别人的，网上虽然有很多，但是简明够用就行。
test.h 定义stack的数据结构和操作函数 （不关心栈的实现方法的童鞋，可以直接略过test.h，跳转到这里）
#include "stdio.h"#include "stdlib.h"#include "math.h"#include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status; typedef char SElemType; /* SElemType类型根据实际情况而定，这里假设为int *//* 顺序栈结构 */typedef struct{ SElemType data[MAXSIZE]; int top; /* 用于栈顶指针 */}SqStack;Status visit(SElemType c){ printf("%d ",c); return OK;}/* 构造一个空栈S */Status InitStack(SqStack *S){ /* S.data=http://www.mamicode.com/(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */ S->top=-1; return OK;}/* 把S置为空栈 */Status ClearStack(SqStack *S){ S->top=-1; return OK;}/* 若栈S为空栈，则返回TRUE，否则返回FALSE */Status StackEmpty(SqStack S){ if (S.top==-1) return TRUE; else return FALSE;}/* 返回S的元素个数，即栈的长度 */int StackLength(SqStack S){ return S.top+1;}/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */Status GetTop(SqStack S,SElemType *e){ if (S.top==-1) return ERROR; else *e=S.data[S.top]; return OK;}/* 插入元素e为新的栈顶元素 */Status Push(SqStack *S,SElemType e){ if(S->top == MAXSIZE -1) /* 栈满 */ { return ERROR; } S->top++; /* 栈顶指针增加一 */ S->data[S->top]=e; /* 将新插入元素赋值给栈顶空间 */ return OK;}/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */Status Pop(SqStack *S,SElemType *e){ if(S->top==-1) return ERROR; *e=S->data[S->top]; /* 将要删除的栈顶元素赋值给e */ S->top--; /* 栈顶指针减一 */ return OK;}/* 从栈底到栈顶依次对栈中每个元素显示 */Status StackTraverse(SqStack S){ int i; i=0; while(i<=S.top) { visit(S.data[i++]); } printf("\n"); return OK;}Status StackOut(SqStack S){ int i; i=S.top; while(i >-1) { printf("%c\n",S.data[i--]); } printf("\n"); return OK;}
test.c，中缀表达式转后缀表达式的实现代码
#include"test.h"/* is number ? */int isNumber (char i){ if(i<58 && i>47){ return 1; }else{ return 0; }}/* is logic operator ? */int isLogic (char i){ if(i == 42 || i == 43 || i == 45 || i == 47) { return 1; }else{ return 0; }}/* get logic symbol prior*/int prior (char i){ switch(i) { case ‘-‘: return 1; case ‘+‘: return 1; case ‘/‘: return 2; case ‘*‘: return 2; }}int main(){ char sInput[]="9+(3-1)*3+8/2"; //output 931-3*+82/+int i = 0; SqStack myStack; InitStack(&myStack); printf("start\n"); //todo: other way to loop char array while(sInput[i] != ‘\0‘){ char cCur = sInput[i]; if(isNumber(cCur)){ printf("%c\n",cCur); }else{ if(cCur == 41) // 41 is ‘)‘ { char cB; cB = ‘1‘; while(cB != 40) // 40 is ‘(‘ { if(cB != ‘1‘){ printf("%c\n",cB); } Pop(&myStack,&cB); } }else{ //none num and not ‘)‘ if(isLogic(cCur) && isLogic(myStack.data[myStack.top])) { if(prior(cCur) <= prior(myStack.data[myStack.top])) { while(myStack.top > -1) { char cE; Pop(&myStack,&cE); printf("%c\n",cE); } Push(&myStack,cCur); }else{ Push(&myStack,cCur); } }else{ //printf("%c\n",cCur); Push(&myStack,cCur); } } } i++; } //printf("top:%i\n", myStack.top); StackOut(myStack); printf("\nend\n"); return 0;}
实现逻辑就是，如果遇到数字，就直接输出，也就是while的前半部分。
如果遇到非数字，那么就有2种情况：
1. 是‘)’，那么就去stack依次弹栈并输出，直到找到‘(‘ (这个左括号就不用输出了)。
2. 如果是操作符(+-*/)，那么就去看栈顶是什么
a. 如果是数字，那么就把这个操作符压栈。
b. 如果也是操作符，那么就比较一下当前操作符和栈顶操作符的优先级(*/ 的优先级大于 +-)，如果当前操作符的优先级大，那么把这个操作符直接压栈，如果小于等于，那么stack里的元素全部弹栈输出(反正也不会有比+-更低的操作符了)，然后把当前这个操作符压栈。
3. 如果整个表达式遍历完毕了呢？那当然就是把栈里的东西，全部都吐出来啦！！
代码在ubuntu14 的 gcc 4.8.2 顺利编译通过，最终输出结果
start931-3*+82/+end
转换成中缀表达式后，可以继续用stack的方法，进行最终结果的运算。
哈哈，是不是觉得四则运算在c语言底层的实现非常有意思呢？？？？？
啥，代码太撮了？ 对不起，其实我是写PHP的：）
利用逆波兰(Reverse Polish Notation, RPN)的后缀表达法计算四则运算表达式