引言
上篇文章中，我們把棧的概念，棧的兩種實(shí)現(xiàn)方式：順序棧、鏈棧做了一個(gè)介紹，相信大家對(duì)棧這個(gè)概念有了初步的認(rèn)識(shí)了吧，今天給大家?guī)淼氖恰笚５膽?yīng)用」這篇內(nèi)容，我們做android必然非常熟悉activity棧，不過這個(gè)棧其實(shí)還算簡(jiǎn)單，今天不做介紹，如果有需要可以給大家單獨(dú)介紹。
棧是一種常用的數(shù)據(jù)結(jié)構(gòu)，基本上稍微復(fù)雜一點(diǎn)的程序都會(huì)用到：
遍歷一個(gè)圖時(shí)，會(huì)用到棧；
搜索一個(gè)解時(shí)，也會(huì)用到棧。
即使程序代碼中沒有明確用棧，在程序執(zhí)行過程中也會(huì)用到棧，因?yàn)槌绦蚍祷睾秃瘮?shù)調(diào)用以及其他遵循?！赶冗M(jìn)先出」原則的地方，系統(tǒng)都會(huì)用棧來存儲(chǔ)數(shù)據(jù)。
而這篇文章則主要提一下其中一個(gè)比較典型和常用的應(yīng)用：「用棧實(shí)現(xiàn)四則運(yùn)算」
用棧實(shí)現(xiàn)四則運(yùn)算
我們都知道，計(jì)算機(jī)的基本功能大多基于對(duì)數(shù)據(jù)的操作，給出一個(gè)運(yùn)算式，計(jì)算機(jī)能夠迅速的計(jì)算出其結(jié)果，若運(yùn)算式有錯(cuò)誤，如"1+3*(2+5" 這個(gè)運(yùn)算式右邊少寫了一個(gè)")"，編譯器會(huì)立即檢查出錯(cuò)誤并報(bào)告，那么計(jì)算機(jī)是如何做到的呢？
其實(shí)計(jì)算機(jī)在進(jìn)行運(yùn)算時(shí)，將運(yùn)算表達(dá)式轉(zhuǎn)換成了「逆波蘭表達(dá)式」，這是一種不需要括號(hào)的后綴表達(dá)方式，例如"1+2"經(jīng)轉(zhuǎn)變變?yōu)椤? 2 +”，然后再進(jìn)行運(yùn)算，而在轉(zhuǎn)化的過程中，這些數(shù)據(jù)就保存在棧中。 需要計(jì)算的時(shí)候，利用棧"后進(jìn)先出"的原則，來進(jìn)行字符的匹配檢查，直到完成轉(zhuǎn)換后，再對(duì)后綴表達(dá)式（「逆波蘭表達(dá)式」）計(jì)算結(jié)果。
計(jì)算機(jī)在這個(gè)過程中，執(zhí)行了兩步操作：
（1）將中綴表達(dá)式轉(zhuǎn)換成為了后綴表達(dá)式
（2）對(duì)后綴表達(dá)式進(jìn)行計(jì)算
而這兩步操作都用到了棧，下面先來學(xué)習(xí)執(zhí)行這兩步操作的基本原理。
中綴轉(zhuǎn)后綴
將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的過程中，數(shù)據(jù)是用棧來存儲(chǔ)的，在遍歷中綴表達(dá)式時(shí)，遵循以下規(guī)則：
* 對(duì)于數(shù)字：直接輸出
* 對(duì)于符號(hào)：
左括號(hào)：進(jìn)棧，不管棧中是否有元素
運(yùn)算符：
-若此時(shí)棧為空，直接進(jìn)棧
-若此時(shí)棧中有元素，則與棧頂符號(hào)進(jìn)行優(yōu)先級(jí)比較：
若新符號(hào)優(yōu)先級(jí)較高，則新符號(hào)進(jìn)棧
-（默認(rèn)左括號(hào)優(yōu)先級(jí)最低，直接入棧);
-若新符號(hào)優(yōu)先級(jí)低，則將棧頂符號(hào)彈出并且輸出，之后讓新符號(hào)進(jìn)棧。
右括號(hào)：不斷將棧頂符號(hào)彈出并輸出，直到匹配到左括號(hào)，再接著讀取下一個(gè)符號(hào)。
-（注意：左右括號(hào)匹配完成即可，不需要將其輸出）
* 遍歷結(jié)束時(shí)，將棧中所有符號(hào)彈出并輸出。
額，不知道大家有沒有懵逼，不過懵逼是正常的。。。
下面就用「實(shí)際案例+圖形展示」讓大家認(rèn)識(shí)下「中綴表達(dá)式」 轉(zhuǎn) 「后綴表達(dá)式」 的步驟。
在大家看例子的過程中，不妨根據(jù)上邊的規(guī)則對(duì)照一下，加強(qiáng)記憶
舉個(gè)栗子
下面，以"1 + 2 * ( 6 + 8 )"這個(gè)普通的四則運(yùn)算表達(dá)式（當(dāng)然這個(gè)就是中綴表達(dá)式）轉(zhuǎn)換成后綴表達(dá)式為例，大家一起圍觀一下
OK,通過上面的24個(gè)步驟（寫的啰嗦了，其實(shí)如果我們自己去算的話，不需要這么多步），我們就得到了傳說中的「后綴表達(dá)式」了。
即
「中綴表達(dá)式」1+2*（6+8）
轉(zhuǎn)成
「后綴表達(dá)式」1 2 6 8 + * +
就轉(zhuǎn)換成功了！
在這個(gè)轉(zhuǎn)換匹配的過程中，如果有錯(cuò)誤，比如如果運(yùn)算式少寫一個(gè)左括號(hào)，則直到彈出棧中的所有元素也匹配不到左括號(hào)，那么編譯器就會(huì)報(bào)錯(cuò)，原理其實(shí)就在此。
代碼來了
下面我們通過代碼來演示一遍「中綴表達(dá)式」轉(zhuǎn)「后綴表達(dá)式」的過程
（注意，在遍歷運(yùn)算式時(shí)是以字符串的形式進(jìn)行的）
linkstack.h 頭文件
#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_
typedef struct Node * pNode;
typedef struct Stack * LinkStack;
struct Node{//數(shù)據(jù)結(jié)點(diǎn)
char data;//數(shù)據(jù)
pNode next;//指針
};
struct Stack{//此結(jié)構(gòu)記錄棧的大小和棧頂元素指針
pNode top;//棧頂元素指針
int size;//棧大小
};
LinkStack Create();//創(chuàng)建棧
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 操作函數(shù)實(shí)現(xiàn)文件
#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;
}
//如果棧不為空，需要把棧中的結(jié)點(diǎn)都釋放
do{
pNode pTmp;
pTmp=Pop(lstack);
free(pTmp);
}
while(lstack->size>0);
printf("棧銷毀成功\n");
}
main.c(測(cè)試文件)
#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include "linkstack.h"
char buffer[256]={0};//臨時(shí)緩沖區(qū)，從棧中彈出的元素可以先存放到這里
void put(char val){
static int index=0;
buffer[index++]=val;//將字符存入，然后索引index后移
}
//優(yōu)先級(jí)比較函數(shù)
int priority(char ch){
int ret=0;
switch(ch){
case '+':
case '-':
ret=1;
break;
case '*':
case '/':
ret=2;
break;
default:
break;
}
return ret;
}
//判斷字符是否是數(shù)字
int inNumber(char ch){
return (ch>='0' &&ch <='9');//是數(shù)字返回1，否則返回0
}
//判斷字符是否是運(yùn)算符
int isOperator(char ch){
return(ch=='+'||ch=='-'||ch=='*'||ch=='/');
}
//判斷字符是否是左括號(hào)
int isLeft(char ch){
return(ch=='(');
}
//判斷字符是否是右括號(hào)
int isRight(char ch){
return(ch==')');
}
//函數(shù)功能：中綴轉(zhuǎn)后綴表達(dá)式
//函數(shù)返回值：正確返回0，錯(cuò)誤返回-1
int Transform(const char * str){
//在轉(zhuǎn)換字符串時(shí)，先常見一個(gè)棧
LinkStack lstack=Create();//創(chuàng)建棧
//創(chuàng)建完成之后，就遍歷字符串中的字符，數(shù)字輸出，運(yùn)算符入棧...
int i=0;
while(str[i]!='\0'){
//判斷是否是數(shù)字
if(isNumber(str[i])){//如果是數(shù)字，就直接輸出
Put(str[i]);//存入到buffer中
}
//判斷是否是運(yùn)算符
else if(isOperator(str[i])){
//如果是運(yùn)算符，則先判斷棧是否為空
if(!IsEmpty(lstack)){//如果棧不為空
//要比較此符號(hào)和棧頂符號(hào)的優(yōu)先級(jí)
while(!IsEmpty(lstack)&&
Priority(*(char*)getTop(lstack)))>=Priority(str[i]))
{
//如果棧頂符號(hào)優(yōu)先級(jí)高，就將棧頂符號(hào)彈出并輸出
//直到棧頂符號(hào)的優(yōu)先級(jí)小于此符號(hào)
//或者棧已彈空
Put(Pop(lstack)->data);//將彈出的棧頂符號(hào)存入buffer
}
}
Push(lstack,str[i]);//如果棧為空，符號(hào)直接入棧
}
//如果是做符號(hào)，直接入棧
else if(isLeft(str[i])){
Push(lstack,str[i]);
}
else if(isRight(str[i])){
//判斷棧頂是不是左括號(hào)，如果不是就彈出，直到匹配到左括號(hào)
while(!isLeft(*((char*)getTop(lstack)))){
//彈出棧頂符號(hào)并存入到buffer中
Put(Pop(lstack)->data);
if(IsEmpty(lstack)){
//彈出元素后，棧已經(jīng)空了，就匹配錯(cuò)誤
printf("沒有匹配到左括號(hào)！\n");
return -1;//棧以為空，結(jié)束程序
}
}
Pop(lstack);//while循環(huán)結(jié)束，匹配到了左括號(hào)，將左括號(hào)彈出，不保存
}
else{
printf("有不能識(shí)別的字符！\n");
return -1;
}
i++;
}
//遍歷結(jié)束
if(str[0]==‘\0’){
//遍歷結(jié)束后，將棧中所有符號(hào)依次彈出
while(!IsEmpty(lstack)){
if(getTop(lstack)->data=='('){
//如果棧中還有‘(’說明缺少右括號(hào)
printf("有沒有匹配的‘(’,缺少右括號(hào)！\n");
return -1;
}
put(Pop(lstack)->data);
}
}
else{
printf("遍歷沒有完成！\n");
}
return 1;
}
int main(){
char str[1024]=(0);
printf("請(qǐng)輸入四則運(yùn)算表達(dá)式：\n");
scanf("%s",str);
if(Transform(str)==-1){
printf("遍歷中出現(xiàn)錯(cuò)誤，無法完成轉(zhuǎn)換！\n");
}
else{
printf("轉(zhuǎn)換后的表達(dá)式是：%s\n",buffer);
}
system("pause");
return 0;
}
上面的實(shí)例代碼只能處理簡(jiǎn)單的一位數(shù)字的運(yùn)算，如果是兩位或者多位數(shù)字，它并不能識(shí)別。
總結(jié)
ok,本篇文章就到這里吧，下篇文章我們?cè)倭摹负缶Y表達(dá)式」運(yùn)算哦，學(xué)完本篇文章，你就會(huì)大概知道計(jì)算機(jī)是如何處理四則運(yùn)算了，是不是很興奮~~~~
不早了，睡吧~
