求表达式（1 - 2） * (4 + 5)的值
- 人类早就熟悉这种中缀表达式的计算公式，随便拉一个小朋友过来，他就直到这个结果是等于-9的，因为括号里面的要先进行计算。
- 但计算机不喜欢了，因为我们有小括号中括号大括号，还允许一个嵌套一个，这样子计算机就要进行很多次if判断才能决定那里先计算。
逆波兰表达式（后缀表达式）
波兰逻辑学家Jan.Lukasiewicz，发明了一种不需要括号的后缀表达式，我们通常把它称为波兰表达式（RPN）。
- 上面表达式（1 - 2） * (4 + 5) 的波兰表达式是这样的： 1 2 - 4 5 + *
- 这种表达式人类是不太好接受的，不过对计算机来说，利用栈的特点，就可以将这种后缀表达式的性能发挥到极致。
用栈来求解表达式（1 - 2） * (4 + 5)的值
- 数字1和2进栈，遇到减号运算符这弹出两个元素进行运算并把结果入栈。
图片.png
- 4和5入栈，遇到加号运算符，4和5弹出栈，相加后将结果9入栈。
图片.png
- 然后又遇到乘法运算符，将9和-1弹出栈进行乘法计算，此时栈空并无数据压栈，-9为最终运算结果。
图片.png
- 正常的表达式 --->逆波兰表达式
a + b ---> a b +
a + (b - c) ---> a b v - +
a + (b - c) * d ---> a b c - d * +
*代码实现（c语言）
#include<stdafx.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.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;
void 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;
}
//入栈操作要在栈顶进行，每次向栈中压入一个数据，top指针就要+1,直到栈满为止
void 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) = e;
s->top++;
}
//出栈操作就是在栈顶取出数据，栈顶指针随之下移操作，每当从栈内弹出一个数据，栈的当前容量就-1
void Pop(sqStack *s, ElemType *e) {
if (s->top == s->base)
{
return;
}
*e = *--(s->top);
}
//求栈的长度
int StackLen(sqStack s) {
return s.top - s.base;
}
//清空栈， 将栈中的元素全部作废，但栈本身物理空间并不发生改变（不是销毁）
void ClearStack(sqStack *s) {
s->top = s->base;
}
//销毁一个栈， 释放掉该栈所占据的物理内存空间
void DestoryStack(sqStack *s) {
int i, len;
len = s->stackSize;
for (i = 0; i < len; i++)
{
free(s->base);
s->base;
}
s->base = s->top = NULL;
s->stackSize = 0;
}
int main() {
sqStack s;
char c;
double d, e;
char str[MAXBUFFER];
int i = 0;
InitStack(&s);
printf("请按逆波兰表达式输入待计算的数据，数据与运算符之间用空格隔开，以#作为结束标志：");
scanf_s("%c", &c);
while (c != '#')
{
while (isdigit(c) || c == '.')
{
str[i++] = c;
str[i] = '\0';
if (i >= 10)
{
printf("出错，输入的单个数据过大!\n");
return -1;
}
scanf_s("%c", &c);
if (c == ' ')
{
d = atof(str);
Push(&s, d);
i = 0;
break;
}
}
switch (c)
{
case '+':
Pop(&s, &e);
Pop(&s, &d);
printf("****%f***%f\n", e, 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出错：除数为0!\n");
}
break;
default:
break;
}
scanf_s("%c", &c);
}
Pop(&s, &d);
printf("最终的计算结果是：%f", d);
getchar();
getchar();
getchar();
return 0;
}
中缀表达式转换成逆波兰表达式
人类喜欢这样的表达式：（1-2）*（4+5）
而不是这样的：1 2 - 4 5 + *
- 下面我们来动手写一个中缀表达式转换成后缀表达式的计算器：
转换规则： 从左到右遍历中缀表达式的每个数字和符号，若是数字则直接输出，若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出，直到遇到左括号或栈空才将其入栈。 - 代码实现
int main() {
sqStack s;
char c, e;
InitStack(&s);
printf("请输入中缀表达式，以#作为结束标志：");
scanf_s("%c", &c);
while (c != '#')
{
while (c >= '0' && c < '9')
{
printf("%c", c);
scanf_s("%c", &c);
if (c < '0' || c > '9')
{
printf(" ");
}
}
if(')' == c)
{
Pop(&s, &e);
while ('(' != e)
{
printf("%c", e);
Pop(&s, &e);
}
}
else if('+' == c || '-' == c)
{
if (!StackLen(s))
{
Push(&s, c);
}
else
{
do
{
Pop(&s, &e);
if ('(' == e)
{
Push(&s, e);
}
else
{
printf("%c", e);
}
} while (StackLen(s) && '(' != e);
Push(&s, c);
}
}
else if('*' == c || '/' == c || '(' == c)
{
Push(&s, c);
}
else if('#' == c)
{
break;
}
else
{
printf("\n出错，输入格式错误！\n");
return -1;
}
scanf_s("%c", &c);
}
while (StackLen(s))
{
Pop(&s, &e);
printf("%c", e);
}
getchar();
getchar();
getchar();
return 0;
}
