主要内容 #
- 后缀表达式
- 问题分析
- 举例说明
1. 后缀表达式 #
所谓表达式，就是由变量、常量以及运算符组合而成的式子。其中，常用的运算符无非 !(阶乘运算符)、^(指数 运算符)、+、-、*、/ 、( ) 这几种，比如 3!+4*2/(1-5)^2 就是一个表达式。
那么，如何用栈结构求一个表达式的值呢?实际上，已经有前辈设计好了一种完美的解决方案。
1929 年，波兰逻辑学家 J・卢卡西维兹提出了一种全新的表示表达式的方法，称为后缀表达式或者逆波兰表达式。 和普通表达式不同，后缀表达式习惯将运算符写在它的运算项之后，且整个表达式中不用括号 () 表明运算的优先
级关系。
以 3! 为例，! 为运算符，3 为运算项，因此 3! 本身就是一个后缀表达式;再以 4*2 为例，* 为运算符，4 和 2 作为它的运算项，其对应的后缀表达式为 4 2+。
在此基础上，我们试着将 3!+4*2/(1-5)^2 转换成后缀表达式，其过程也就是将表达式中所有运算符放置在它的运 算项之后:
- ! 运算符对应的运算项为 3，转换后得到 3 !;
- + 运算符对应的运算项是 3! 和 4*2/(1-5)^2，转换之后得到:3! 4*2/(1-5)^2 +;
- * 运算符对应的运算项是 4 和 2，转换之后得到 4 2 *;
- / 运算符对应的运算项是 4 2 * 和 (1-5)^2，转换后得到 4 2 * (1-5)^2 /;
- – 运算符对应的运算项是 1 和 5，转换后得到 1 5 -;
- ^ 运算符对应的运算项是 15- 和 2 ，转换后得到15-2^。
整合之后，整个普通表达式就转换成了 3 ! 4 2 * 1 5 – 2 ^ / +，这就是其对应的后缀表达式。
2. 问题分析 #
不难发现，后缀表达式完全舍弃了表达式应有的可读性，但有失必有得，相比于普通的表达式，后缀表达式的值可以轻松借助栈存储结构求得。具体求值过程为：当用户给定一个后缀表达式时，按照从左到右的顺序依次扫描表达式中的各个运算项和运算符，对它们进行如下处理：
- 遇到运算项时直接入栈；
- 遇到运算符时，将位于栈顶的运算项出栈，对于！运算符，取栈顶一个运算项；其他运算符，取栈顶两个运算项，第一个取出的运算项作为该运算符的右运算项，另一个作为左运算项。求此表达式的的值并将其入栈。
经过以上操作，知道栈中仅存在一个运算项为止，此运算项即为整个表达式的值。
3. 举例说明 #
以3！4 2*1 5-2^/+表达式为例，求值过程为：
1) 从3开始，它是运算项，因此直接入栈：
2) !作为运算符，从栈顶取1个运算项（也就是3），求3!的值（3!=3*2*1=6）并将其入栈：
3) 将4和2先后入栈：
4) 对于运算符*取两个运算项（2和4），其中先取出的2作为*的右操作数，4作为左操作数。求4*2的值8，并将其入栈：
5) 将1和5先后入栈：
6) 对于-运算符，取栈顶两个运算项（5和1），计算出1-5的值为-4，将其入栈：
7) 将2入栈：
8) 对于^运算符，取栈顶2个运算项（2和-4），计算出-4^2的值16，将其入栈：
9) 对于/运算符，取栈顶2个运算项（16和8），计算出8/16的值0.5，将其入栈：
10) 对于+运算符，取栈顶2个运算项（0.5和6），计算出6+0.5的值6.5，将其入栈：
由此，整个表达式的求值过程就结束了，最终表达式的值为6.5.如下给出了实现此过程的参考代码：
参考代码
//根据后缀表达式posdtexp，计算它的值
#include <iostream>
using namespace std;
#define MAXSIZE 100
class Stack_num{
public:
double data[MAXSIZE];
int top;
};
void InitSrack_num(Stack_num **s){
*s = (Stack_num *) malloc(sizeof(Stack_num));
(*s) -> top = -1;
}
bool Push_num(Stack_num **s, double e){
if((*s) -> top == MAXSIZE - 1){
return false;
}
(*s) -> top++;
(*s) -> data[(*s) -> top] = e;
return true;
}
bool Pop_num(Stack_num **s, double *e){
if((*s) -> top == -1)
return false;
*e = (*s) -> data[(*s) -> top];
(*s) -> top--;
return true;
}
//计算后缀表达式的值
double compValue(char *postexp){
Stack_num *num;
int i = 1;
double result;
double a, b;
double c;
double d;
InitSrack_num(&num);
//依次扫描整个表达式
while(*postexp != '\0'){
switch (*postexp)
{
case '+':
Pop_num(&num, &a);
Pop_num(&num, &b);
//计算b+a的值
c = b + a;
Push_num(&num, c);
cout << '+' << c << endl;
break;
case '-':
Pop_num(&num, &a);
Pop_num(&num, &b);
//计算b-a的值
c = b - a;
Push_num(&num, c);
cout << '-' << c << endl;
break;
case '*':
Pop_num(&num, &a);
Pop_num(&num, &b);
//计算b*a的值
c = b * a;
Push_num(&num, c);
cout << '*' << c << endl;
break;
case '/':
Pop_num(&num, &a);
Pop_num(&num, &b);
//计算b/a的值
if(a != 0){
c = b / a;
Push_num(&num, c);
}else{
cout << "除零错误！" << endl;
exit(0);
}
cout << '/' << c << endl;
break;
case '^':
Pop_num(&num, &a);
Pop_num(&num, &b);
//计算b^a的值
if (a != 0){
i = 1;
c = 1;
while(i <= a){
c = c * b;
i++;
}
}else if(b != 0){
c = 1;
}else{
c = 0;
}
Push_num(&num, c);
cout << '^' <<c << endl;
break;
case '!':
Pop_num(&num, &a);
//计算a!的值
c = 1;
i = a;
while(i != 0){
c = c * i;
i--;
}
Push_num(&num, c);
cout << '!' << c << endl;
break;
default:
//如果不是运算符，就只能是字符形式的数字，将其转换成对应的整数
d = 0;
while(*postexp >= '0' && *postexp <= '9'){
d = 10 * d + (*postexp - '0');
postexp++;
}
Push_num(&num, c);
}
postexp++; //继续下一个字符
}
Pop_num(&num, &result);
return result;
}
