逆波兰表达式
先说一下中缀表达式，平时我们使用的运算表达式就是中缀表达式，例如1+3*2，中缀表达式的特点就是：二元运算符总是置于与之相关的两个运算对象之间
人读起来比较好理解，但是计算机处理起来就很麻烦，运算顺序往往因表达式的内容而定，不具规律性。
后缀表达式（又称逆波兰表达式），后缀表达式的特点就是：每一运算符都置于其运算对象之后，以上面的中缀表达式1+2 * 3为例子，转为后缀表达式就是123 * +
下面先分析怎么把中缀表达式转换为后缀表达式，这里我们考虑六种操作符’+‘、’-‘、’*‘、’/‘、’(‘、’)'，完成中缀转后缀我们需要两个数组，都以栈的方式来操作，一个数组用来存放后缀表达式（char num[100]），
一个数组用来临时存放操作数（char opera[100]）（这里说临时存放，是因为最后都要入栈到后缀表达式数组num中，这个数组就相当于一个中转站）
1、从左往右扫描中缀表达式（这里我们以1 * (2+3)为例）
2、如果是数字那么将其直接入栈到数组num中
3、如果是操作数，需要进一步判断
（1）如果是左括号’('直接入栈到数组opera中
（2）如果是运算符（‘+’、‘-’、‘*’、‘/’），先判断数组opera的栈顶的操作数的优先级（如果是空栈那么直接入栈到数组opera），如果是左括号那么直接入栈到数组opera中，如果栈顶是运算符，且栈顶运算符的优先级大于该运算符
那么将栈顶的运算符出栈，并入栈到数组num中，重复步骤3，如果栈顶运算符优先级小于该运算符，那么直接将该运算符入栈到opera中
（3）如果是右括号’)‘，那么说明在opera数组中一定有一个左括号与之对应（在你没输错的情况下），那么将opera中的运算符依次出栈，并入栈到num中，直到遇到左括号’('（注意左括号不用入栈到num）
4、如果中缀表达式扫描完了，那么将opera中的操作数依次出栈，并入栈到num中就可以了，如果没有没有扫描完重复1-3步
上面就是中缀表达式转后缀表达式的步骤了，下面用图来直观的了解一下这个过程
需要注意的是：opera中操作数，越靠近栈顶，优先级越高，下面附上实现代码
#include<iostream>#include<cstring>#include<cstdio>using namespace std;void PushOperation(char *opera, char *ss, int *op, int *s);char num[100] = "0"; /* 存储后缀表达式 */char opera[100] = "0"; /* 存储运算符 */void PexpretoSexpre(char *ss){/*num----jopera----opss----i*/int i, j, op;op = i = j = 0;while (ss[i] != '\0'){if (isdigit(ss[i])) /* 如果是数字 */{num[j] = ss[i]; /* 数字直接入后缀表达式栈 */j++;i++;}else{switch (ss[i]) /* 如果是操作数 */{case '+':{if (op == 0) /* 如果是空栈 */{PushOperation(opera, ss, &op, &i); /* 入运算符栈 */break;}if (opera[op-1] == '+' || opera[op-1] == '-' || opera[op-1] == '*' || opera[op-1] == '/' || opera[op-1] == ')' || opera[op-1] == '('){switch (opera[op-1]){case '+':{PushOperation(opera, ss, &op, &i);break;}case '-':{PushOperation(opera, ss, &op, &i);break;}case '*':{/* 加法优先级低于乘法 */num[j] = opera[op-1]; /* 将操作数出栈 */opera[op-1] = ss[i]; /* 将新的操作数压入栈中 */j++;i++;break;}case '/':{num[j] = opera[op-1];opera[op-1] = ss[i];j++;i++;break;}case '(':{PushOperation(opera, ss, &op, &i);break;}}}break;}case '-':{if (op == 0){PushOperation(opera, ss, &op, &i);break;}if (opera[op-1] == '+' || opera[op-1] == '-' || opera[op-1] == '*' || opera[op-1] == '/' || opera[op-1] == ')' || opera[op-1] == '('){switch (opera[op-1]){case '+':{PushOperation(opera, ss, &op, &i);break;}case '-':{PushOperation(opera, ss, &op, &i);break;}case '*':{num[j] = opera[op-1];opera[op-1] = ss[i];j++;i++;break;}case '/':{num[j] = opera[op-1];opera[op-1] = ss[i];j++;i++;break;}case '(':{PushOperation(opera, ss, &op, &i);break;}}}break;}case '*':{if (op == 0){PushOperation(opera, ss, &op, &i);break;}if (opera[op-1] == '+' || opera[op-1] == '-' || opera[op-1] == '*' || opera[op-1] == '/' || opera[op-1] == ')' || opera[op-1] == '('){switch (opera[op-1]){case '+':{PushOperation(opera, ss, &op, &i);break;}case '-':{PushOperation(opera, ss, &op, &i);break;}case '*':{PushOperation(opera, ss, &op, &i);break;}case '/':{PushOperation(opera, ss, &op, &i);break;}case '(':{PushOperation(opera, ss, &op, &i);break;}}}break;}case '/':{if (op == 0){PushOperation(opera, ss, &op, &i);break;}if (opera[op-1] == '+' || opera[op-1] == '-' || opera[op-1] == '*' || opera[op-1] == '/' || opera[op-1] == ')' || opera[op-1] == '('){switch (opera[op-1]){case '+':{PushOperation(opera, ss, &op, &i);break;}case '-':{PushOperation(opera, ss, &op, &i);break;}case '*':{PushOperation(opera, ss, &op, &i);break;}case '/':{PushOperation(opera, ss, &op, &i);break;}case '(':{PushOperation(opera, ss, &op, &i);break;}}}break;}case '(':{PushOperation(opera, ss, &op, &i);break;}case ')': /* 如果遇到右括号 */{while (opera[op-1] != '('){num[j] = opera[op-1]; /* 将运算符栈中的元素依次入栈到后缀表达式栈中，直到遇到左括号为止 */j++;op--;}op--;i++;break;}default:{printf("传入表达式不符合要求\n");exit(0);}}}}while (op != 0){num[j] = opera[op-1]; /* 将运算符栈中的元素依次入栈到后缀表达式栈中 */j++;op--;}num[j] = '\0';i = 0;while (num[i] != '\0') /* 将后缀表达式存储到传入的形参ss中 */{ss[i] = num[i];i++;}ss[i] = '\0';}/* Function: 入运算符栈*/void PushOperation(char *opera, char *ss, int *op, int *s){opera[*op] = ss[*s];(*op)++;(*s)++;}int main(){char ss[100];gets(ss);PexpretoSexpre(ss);puts(num);}
后缀表达式的计算
完成了中缀表达式转后缀表达式，接下来就是后缀表达式的计算了，后缀表达式的计算比中缀转后缀要稍微简单一点，只需要对我们转换好的后缀表达式从左往右依次扫描，并依次入栈就行了，只需要用一个数组（double num[100]）就OK。
需要考虑的情况如下：
1、如果是数字，那么直接入栈到num中
2、如果是运算符，将栈顶的两个数字出栈（因为我们考虑的运算符加、减、乘、除都是双目运算符，只需要两个操作数），出栈后对两个数字进行相应的运算，并将运算结果入栈
3、直到遇到’\0’。
我们用几张图，来直观了解下这个过程，以上面转换好的后缀表达式"123+*"为例（这里用ss来存储后缀表达式，num来存储计算结果，注意不要与上面图中num搞混淆了）
（注意：这里将计算结果5入栈后，栈顶从之前的[3]变成[2]）
代码：
#include<iostream>#include<string>using namespace std;#define MAX 100double TransformCtoD(char ch); /* 将char类型数组的每一个元素转换为double */void CalculateAndPush(double *num, int *i, int *j, char mm); /* 计算结果并入栈 */int main(){FILE *fp;char ss[MAX]=" 3 3 1 2 + * /"; /* 存储逆波兰表达式 */gets(ss);int i = 0;int j = 0;double num[MAX]; /* 栈 */while (ss[i]!='\0'){if(ss[i]==' ') {i++;continue;}if (ss[i] >= '0' && ss[i] <= '9') /* 如果是数字 */{/* 因为num是char类型的，需要转换为double类型方便计算 */num[j] = TransformCtoD(ss[i]); /* 将数字存储到栈中 */j++;i++;}else if (ss[i] == '+' || ss[i] == '-' || ss[i] == '*' || ss[i] == '/'){CalculateAndPush(num, &i, &j, ss[i]); /* 计算结果并入栈 */}else if (ss[i] =='\0') /* 如果是换行符，结束循环*/{break;}}printf("%lf", num[0]);return 0;}/* Function: 计算结果并入栈 */void CalculateAndPush(double *num, int *i, int *j, char mm){switch (mm){case '+':{num[(*j)-2] = num[(*j)-1] + num[(*j)-2];(*j)--;(*i)++;break;}case '-':{num[(*j)-2] = num[(*j)-1] - num[(*j)-2];(*j)--;(*i)++;break;}case '*':{num[(*j)-2] = num[(*j)-1] * num[(*j)-2];(*j)--;(*i)++;break;}case '/':{num[(*j)-2] = num[(*j)-1] / num[(*j)-2];(*j)--;(*i)++;break;}default:{exit(0);}}}/* Function: 将char类型数组的每一个元素转换为double */double TransformCtoD(char ch){return (double)(ch - '0');}
改进后代码可以算多位数：
代码如下
#include<iostream>#include<string>using namespace std;#define MAX 100double TransformCtoD(char ch); /* 将char类型数组的每一个元素转换为double */void CalculateAndPush(double *num, int *i, int *j, char mm);/* 计算结果并入栈 */int num_ans=0;int b=0;int main(){FILE *fp;char ss[MAX]=" 3 3 1 2 + * /"; /* 存储逆波兰表达式 */gets(ss);int i = 0;int j = 0;double num[MAX]; /* 栈 */while (ss[i]!='\0'){if ((ss[i] >= '0' && ss[i] <= '9')||(ss[i]==' ')) /* 如果是数字 */{/* 因为num是char类型的，需要转换为double类型方便计算 */if(ss[i] >= '0' && ss[i] <= '9'){num_ans=num_ans*10+ss[i]-'0';b=1;}if(ss[i]==' '&&b==1){num[j] = num_ans; /* 将数字存储到栈中 */j++;b=0;num_ans=0;}i++;}else if (ss[i] == '+' || ss[i] == '-' || ss[i] == '*' || ss[i] == '/'){CalculateAndPush(num, &i, &j, ss[i]); /* 计算结果并入栈 */}else if (ss[i] =='\0') /* 如果是换行符，结束循环*/{break;}}printf("%lf", num[0]);return 0;}/* Function: 计算结果并入栈 */void CalculateAndPush(double *num, int *i, int *j, char mm){switch (mm){case '+':{num[(*j)-2] = num[(*j)-1] + num[(*j)-2];(*j)--;(*i)++;break;}case '-':{num[(*j)-2] = num[(*j)-1] - num[(*j)-2];(*j)--;(*i)++;break;}case '*':{num[(*j)-2] = num[(*j)-1] * num[(*j)-2];(*j)--;(*i)++;break;}case '/':{num[(*j)-2] = num[(*j)-1] / num[(*j)-2];(*j)--;(*i)++;break;}default:{exit(0);}}}/* Function: 将char类型数组的每一个元素转换为double */double TransformCtoD(char ch){return (double)(ch - '0');}
前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。比如:- × + 3 4 5 6
它的中缀表达式就是常见的运算表达式，如(3+4)×5-6
最熟悉的中缀表达式画出一棵语法树来直观认识一下前后缀表达式的生成。以A+B*(C-D)-E*F为例：
中缀表达式得名于它是由相应的语法树的中序遍历的结果得到的。上面的二叉树中序遍历的结果就是A+B*(C-D)-E*F。
前缀表达式是由相应的语法树的前序遍历的结果得到的。上图的前缀表达式为- + A * B - C D * E F
后缀表达式又叫做逆波兰式。它是由相应的语法树的后序遍历的结果得到的。上图的后缀表达式为：A B C D - * + E F * -
前缀表达式的计算：
新建一个栈，然后对表达式从右到左进行遍历，如果遇到数字，那么将数字压入栈中，如果遇到的是操作运算符，那么就从栈中跳出两个数字num1,num2，并进行相应的运算，此时需要注意相关的运算法则，比如除法中的除数不可以为0，然后将结果再次压入到栈中。注意如果是 - 号、/ 号 ， % 号，那么必须是num1 - num2,num1 / num2,num1 % num2，而+号，*号就不用区分，因为结果都一样的嘛,为什么会这样子呢？请看图解。
遍历结束之后，栈中只剩下一个元素，那么这个元素就是表达式的值，将其从栈中跳出即可。
#include <iostream>#include <cstring>#define MAXSIZE 256using namespace std;typedef struct stack{int top;char stack[MAXSIZE];}Stack;void initStack(Stack *s){s->top=0;}int getPrefixValue(Stack *s1,char s[]){int i=strlen(s);int temp1,temp2;int sum=0;char d;if(strlen(s)==0){cout<<"中缀式不能为空."<<endl;return -1;}while(i>=0){if(s[i-1]>='0'&&s[i-1]<='9'){s1->top++;s1->stack[s1->top]=s[i-1];}else{temp1=s1->stack[s1->top]-'0';s1->top--;temp2=s1->stack[s1->top]-'0';s1->top--;switch(s[i-1]){case '+':sum=temp1+temp2;break;case '-':sum=temp1-temp2;break;case '*':sum=temp1*temp2;break;case '/':sum=temp1/temp2;break;}s1->top++;s1->stack[s1->top]=sum+'0';}i--;}d=s1->stack[s1->top];sum=d-'0';return sum;}int main(){Stack s1;char s[]="+-+7*345/62";int sum=0;initStack(&s1);cout<<"前缀式为:"<<s<<endl;sum=getPrefixValue(&s1,s);cout<<"结果求和为："<<sum<<endl;return 0;}
