引言
上篇文章中，我们把栈的概念，栈的两种实现方式：顺序栈、链栈做了一个介绍，相信大家对栈这个概念有了初步的认识了吧，今天给大家带来的是「栈的应用」这篇内容，我们做android必然非常熟悉activity栈，不过这个栈其实还算简单，今天不做介绍，如果有需要可以给大家单独介绍。
栈是一种常用的数据结构，基本上稍微复杂一点的程序都会用到：
遍历一个图时，会用到栈；
搜索一个解时，也会用到栈。
即使程序代码中没有明确用栈，在程序执行过程中也会用到栈，因为程序返回和函数调用以及其他遵循栈「先进先出」原则的地方，系统都会用栈来存储数据。
而这篇文章则主要提一下其中一个比较典型和常用的应用：「用栈实现四则运算」
用栈实现四则运算
我们都知道，计算机的基本功能大多基于对数据的操作，给出一个运算式，计算机能够迅速的计算出其结果，若运算式有错误，如"1+3*(2+5" 这个运算式右边少写了一个")"，编译器会立即检查出错误并报告，那么计算机是如何做到的呢？
其实计算机在进行运算时，将运算表达式转换成了「逆波兰表达式」，这是一种不需要括号的后缀表达方式，例如"1+2"经转变变为“1 2 +”，然后再进行运算，而在转化的过程中，这些数据就保存在栈中。 需要计算的时候，利用栈"后进先出"的原则，来进行字符的匹配检查，直到完成转换后，再对后缀表达式（「逆波兰表达式」）计算结果。
计算机在这个过程中，执行了两步操作：
（1）将中缀表达式转换成为了后缀表达式
（2）对后缀表达式进行计算
而这两步操作都用到了栈，下面先来学习执行这两步操作的基本原理。
中缀转后缀
将中缀表达式转换为后缀表达式的过程中，数据是用栈来存储的，在遍历中缀表达式时，遵循以下规则：
* 对于数字：直接输出
* 对于符号：
左括号：进栈，不管栈中是否有元素
运算符：
-若此时栈为空，直接进栈
-若此时栈中有元素，则与栈顶符号进行优先级比较：
若新符号优先级较高，则新符号进栈
-（默认左括号优先级最低，直接入栈);
-若新符号优先级低，则将栈顶符号弹出并且输出，之后让新符号进栈。
右括号：不断将栈顶符号弹出并输出，直到匹配到左括号，再接着读取下一个符号。
-（注意：左右括号匹配完成即可，不需要将其输出）
* 遍历结束时，将栈中所有符号弹出并输出。
额，不知道大家有没有懵逼，不过懵逼是正常的。。。
下面就用「实际案例+图形展示」让大家认识下「中缀表达式」 转 「后缀表达式」 的步骤。
在大家看例子的过程中，不妨根据上边的规则对照一下，加强记忆
举个栗子
下面，以"1 + 2 * ( 6 + 8 )"这个普通的四则运算表达式（当然这个就是中缀表达式）转换成后缀表达式为例，大家一起围观一下
OK,通过上面的24个步骤（写的啰嗦了，其实如果我们自己去算的话，不需要这么多步），我们就得到了传说中的「后缀表达式」了。
即
「中缀表达式」1+2*（6+8）
转成
「后缀表达式」1 2 6 8 + * +
就转换成功了！
在这个转换匹配的过程中，如果有错误，比如如果运算式少写一个左括号，则直到弹出栈中的所有元素也匹配不到左括号，那么编译器就会报错，原理其实就在此。
代码来了
下面我们通过代码来演示一遍「中缀表达式」转「后缀表达式」的过程
（注意，在遍历运算式时是以字符串的形式进行的）
linkstack.h 头文件
#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_
typedef struct Node * pNode;
typedef struct Stack * LinkStack;
struct Node{//数据结点
char data;//数据
pNode next;//指针
};
struct Stack{//此结构记录栈的大小和栈顶元素指针
pNode top;//栈顶元素指针
int size;//栈大小
};
LinkStack Create();//创建栈
int IsEmpty(LinkStack lstack);//判断栈是否为空
int getSize(LinkStack lstack);//获取栈的大小
int Push(LinkStack lstack,int val);//元素入栈
pNode getTop(LinkStack lstack);//获取栈顶元素
pNode Pop(LinkStack lstack);//弹出栈顶元素
void Destory(LinkStack lstack);//销毁栈
#endif
linkstack.c 操作函数实现文件
#include <stdio.h>
#include <stdlib.h>
#include "linkstack.h"
LinkStack Create(){
LinkStack lstack=(LinkStack)malloc(sizeof(struct Stack));
if(lstack!=null){
lstack->top=NULL;
lstack->size=0;
}
return lstack;
}
int IsEmpty(LinkStack stack){
if(stack->top==NULL||stack->size==0){
return 1;
}
return 0;
}
int getSize(LinkStack stack){
if(!IsEmpty(stack)){
return(stack->size);
}
return 0;
}
int Push(LinkStack stack,char val){
pNode node=(pNode)malloc(sizeof(struct Node));
if(node!=null){
node->data=val;
node->next=getTop(lstack);
lstack->top=node;
lstack->size++;
}
return 1;
}
pNode getTop(LinkStack lstack){
if(!IsEmpty(lstack)){
return lstack->top;
}
return NULL;
}
pNode Pop(LinkStack lstack){
if(IsEmpty(lstack)){
return NULL;
}
pNode node=lstack->top;
lstack->top=lstack->top->next;
lstack->size--;
return node;
}
void Destory(LinkStack lstack){
if(IsEmpty(lstack)){
free(lstack);
printf("栈以为空，无需清理\n");
return;
}
//如果栈不为空，需要把栈中的结点都释放
do{
pNode pTmp;
pTmp=Pop(lstack);
free(pTmp);
}
while(lstack->size>0);
printf("栈销毁成功\n");
}
main.c(测试文件)
#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include "linkstack.h"
char buffer[256]={0};//临时缓冲区，从栈中弹出的元素可以先存放到这里
void put(char val){
static int index=0;
buffer[index++]=val;//将字符存入，然后索引index后移
}
//优先级比较函数
int priority(char ch){
int ret=0;
switch(ch){
case '+':
case '-':
ret=1;
break;
case '*':
case '/':
ret=2;
break;
default:
break;
}
return ret;
}
//判断字符是否是数字
int inNumber(char ch){
return (ch>='0' &&ch <='9');//是数字返回1，否则返回0
}
//判断字符是否是运算符
int isOperator(char ch){
return(ch=='+'||ch=='-'||ch=='*'||ch=='/');
}
//判断字符是否是左括号
int isLeft(char ch){
return(ch=='(');
}
//判断字符是否是右括号
int isRight(char ch){
return(ch==')');
}
//函数功能：中缀转后缀表达式
//函数返回值：正确返回0，错误返回-1
int Transform(const char * str){
//在转换字符串时，先常见一个栈
LinkStack lstack=Create();//创建栈
//创建完成之后，就遍历字符串中的字符，数字输出，运算符入栈...
int i=0;
while(str[i]!='\0'){
//判断是否是数字
if(isNumber(str[i])){//如果是数字，就直接输出
Put(str[i]);//存入到buffer中
}
//判断是否是运算符
else if(isOperator(str[i])){
//如果是运算符，则先判断栈是否为空
if(!IsEmpty(lstack)){//如果栈不为空
//要比较此符号和栈顶符号的优先级
while(!IsEmpty(lstack)&&
Priority(*(char*)getTop(lstack)))>=Priority(str[i]))
{
//如果栈顶符号优先级高，就将栈顶符号弹出并输出
//直到栈顶符号的优先级小于此符号
//或者栈已弹空
Put(Pop(lstack)->data);//将弹出的栈顶符号存入buffer
}
}
Push(lstack,str[i]);//如果栈为空，符号直接入栈
}
//如果是做符号，直接入栈
else if(isLeft(str[i])){
Push(lstack,str[i]);
}
else if(isRight(str[i])){
//判断栈顶是不是左括号，如果不是就弹出，直到匹配到左括号
while(!isLeft(*((char*)getTop(lstack)))){
//弹出栈顶符号并存入到buffer中
Put(Pop(lstack)->data);
if(IsEmpty(lstack)){
//弹出元素后，栈已经空了，就匹配错误
printf("没有匹配到左括号！\n");
return -1;//栈以为空，结束程序
}
}
Pop(lstack);//while循环结束，匹配到了左括号，将左括号弹出，不保存
}
else{
printf("有不能识别的字符！\n");
return -1;
}
i++;
}
//遍历结束
if(str[0]==‘\0’){
//遍历结束后，将栈中所有符号依次弹出
while(!IsEmpty(lstack)){
if(getTop(lstack)->data=='('){
//如果栈中还有‘(’说明缺少右括号
printf("有没有匹配的‘(’,缺少右括号！\n");
return -1;
}
put(Pop(lstack)->data);
}
}
else{
printf("遍历没有完成！\n");
}
return 1;
}
int main(){
char str[1024]=(0);
printf("请输入四则运算表达式：\n");
scanf("%s",str);
if(Transform(str)==-1){
printf("遍历中出现错误，无法完成转换！\n");
}
else{
printf("转换后的表达式是：%s\n",buffer);
}
system("pause");
return 0;
}
上面的实例代码只能处理简单的一位数字的运算，如果是两位或者多位数字，它并不能识别。
总结
ok,本篇文章就到这里吧，下篇文章我们再聊「后缀表达式」运算哦，学完本篇文章，你就会大概知道计算机是如何处理四则运算了，是不是很兴奋~~~~
不早了，睡吧~
