在前一天已经利用栈完成2进制到8进制的转换。但是栈的应用方面还有很多，本次我将讲解如何计算后缀表达式的结果。
后缀表达式（PRN）也叫逆波兰表达式，是在计算机中用于求值的一种方式，其求值过程可以用到栈来辅助存储。
在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示，如1+2。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为后缀表示，如12+。
它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下：
如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。
假定待求值的后缀表达式为：1 2 + 5 3 6 + * + 7 - ，其实际上为1+2+5*(3+6)-7。其求值过程如下：
1、遍历表达式，遇到1和2，压入栈中。此时栈如图所示：
2、接着读到+号，弹出2与1，执行加法运算，得到3，再次入栈。此时栈如图所示：
3、遇到5、3和6，压入栈中。此时栈如图所示：
4、接着读到+号，弹出6与3，执行加法运算，得到9，再次入栈。此时栈如图所示：
5、接着读到*号，弹出9与5，执行加法运算，得到45，再次入栈。此时栈如图所示：
6、接着读到+号，弹出45与3，执行加法运算，得到48，再次入栈。此时栈如图所示：
7、遇到7，压入栈中。此时栈如图所示：
8、接着读到-号，弹出7与48，执行加法运算，得到41，再次入栈。
9、由于表达式已结束，读出栈内的最后一个元素，就是结果41。
#include <stdio.h>
#include <stdlib.h>
#define Maxsize 10
typedef double Ele;
struct stack
{
Ele* top;
Ele* bottom;
int stacksize;
};
typedef struct stack* Stack;
void init(Stack s){ //初始化栈
Ele *p;
p = (Ele*)malloc(Maxsize * sizeof(Ele));
if (p == NULL){
printf("error");
exit(1);
}
s->top = s->bottom = p;
s->stacksize = Maxsize;
}
void PUSH(Stack s, Ele data){ //入栈
int length;
length = s->top - s->bottom;
if (length >= s->stacksize){
s->bottom = (Ele*)realloc(s->bottom,(s->stacksize + Maxsize) * sizeof(Ele));
if (s->bottom == NULL){
printf("内存分配失败\n");
exit(1);
}
s->stacksize = s->stacksize + Maxsize;//更新stacksize的值
s->top = s->bottom + length; //更新top的值
}
*(s->top) = data;
s->top++;
}
Ele POP(Stack s){ //出栈
Ele num;
if (s->top == s->bottom){
printf("栈内没有元素了！\n");
exit(1);
}
s->top--;
num = *(s->top);
return num;
}
int main(){
struct stack s; //定义栈
char c = 0,str[10]; //c用于从键盘获取字符，str用于存储每一轮输入的数字，之后会转化成double类型
Ele a1, a2, num; //a1，a2用于栈的运算
int i = 0; //temp量
init(&s); //初始化栈
printf("请输入一个算式：");
scanf("%c", &c); //输入一个字符
while (c != '#')
{
while ((c <= '9' && c >= '0') || c == '.'){ //该部分用于获取一个double类型的数字
str[i++] = c;
str[i] = '\0';
if (i >= 10){
printf("输入数据过大");
exit(1);
}
scanf("%c", &c);
if (!(c <= '9' && c >= '0') && !(c == '.')){
a1 = atof(str); //该函数用于将字符串转化位double
PUSH(&s, a1);
i = 0;
break;
}
}
switch (c) //判断是否属于加减乘除
{
case '+':
a1 = POP(&s);
a2 = POP(&s);
PUSH(&s, a2 + a1);
break;
case '-':
a1 = POP(&s);
a2 = POP(&s);
PUSH(&s, a2 - a1);
break;
case '*':
a1 = POP(&s);
a2 = POP(&s);
PUSH(&s, a2 * a1);
break;
case '/':
a1 = POP(&s);
a2 = POP(&s);
PUSH(&s, a2 / a1);
break;
case ' ':
break;
case '#':
break;
default:
printf("输入符号错误！\n");
break;
}
scanf("%c", &c);
}
num = POP(&s);
printf("%.3f\n", num);
return 0;
}
https://github.com/bubbliiiing/Data-Structure-and-Algorithm
希望得到朋友们的喜欢。
有问题的朋友可以提问噢。