棧的入棧、出棧、獲取棧頂?shù)腸語言算法

1、#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <string.h>#define MAX 100char stockMAX;int top=-1;char aMAX,bMAX;char exp100;int operand1=0; / 定義操作數(shù)int operand2=0; / 定義操作數(shù)int result=0; / 定義操作結(jié)果變量 int pos=0; / 目前表達(dá)式位置 / 定義一個節(jié)點的結(jié)構(gòu)typedef struct nodeint member;

2、/數(shù)據(jù)域struct node * pNext;/指針域Node,*pNode;/ 定義一個棧結(jié)構(gòu)typedef struct stackpNode Top; /棧頂pNode Bottom; /棧底Stack,* pStack;void InitStack(pStack ); / 初始化棧的函數(shù)bool Push(pStack ,char); / 進(jìn)行入棧操作的函數(shù) void TraverseStack(pStack ); / 遍歷棧函數(shù)bool Empty(pStack ); / 判斷棧是否為空的函數(shù) int Pop(pStack ); / 進(jìn)行出棧操作的函數(shù)void Clear(pSta

3、ck ); / 清空棧的函數(shù)void caidan(); /顯示菜單void fun( char a,char b); /中序轉(zhuǎn)后序函數(shù)int main(void)Stack s; / 定義一個棧char c;int i;int num;char data; / 臨時保存用戶輸入的數(shù)據(jù) char re_num; / 保存Pop函數(shù)的返回值printf("*n");printf("* 1初始化棧 *n");printf("* 2入棧 *n");printf("* 3出棧 *n");printf("* 4遍歷

4、棧中元素并顯示棧頂元素*n");printf("* 5清空棧 *n");printf("* 6棧的中序轉(zhuǎn)后序 *n");printf("* 7棧后序表達(dá)式的計算 *n");printf("* 8退出程序 *n");printf("* 9顯示菜單 *n");printf("*n");while(1)printf("請選擇你要進(jìn)行的操作:");int k;scanf("%d",&k);switch(k)case 1:Ini

5、tStack(&s);break;case 2:printf("請輸入你準(zhǔn)備輸入數(shù)據(jù)的個數(shù):");scanf("%d",&num);for (i = 0;i < num;i+)printf("第 %d 個字符：",i+1);getchar(c);scanf("%c",&data);if (Push(&s,data) / 調(diào)用Push函數(shù) continue;elseprintf("進(jìn)行進(jìn)棧操作失??！n");exit(-1);break;case 3:print

6、f("請輸入你準(zhǔn)備出出棧的字符個數(shù): ");scanf("%d",&data);if (Empty(&s) /判斷棧是否為空，為空就不能進(jìn)行出棧操作printf("棧已為空!n");elseprintf("你去掉的數(shù)字是：");for (i = 0; i < data;i+)re_num = Pop(&s); / 調(diào)用Pop函數(shù)，并把返回值賦給re_num;printf("%c ",re_num);printf("n");break;case 4

7、:TraverseStack(&s);break;case 5:Clear(&s);break;case 6:printf("請輸入一個字符串：");scanf("%s",a);void fun( char a,char b);fun(a,b);printf(" n");break;case 7:printf("tn 請輸入后綴表達(dá)式：");gets(exp); /cin.getline(exp,81) / 讀取后綴表達(dá)式printf("tnn 后綴表達(dá)式%s的結(jié)果是：",exp

8、);while (exppos !='0' && exppos !='n') / 分析表達(dá)式字符串 if (isoperator(exppos) / 是運(yùn)算符，取兩個操作數(shù)pop(&operand2);pop(&operand1);push(getvalue(exppos,operand1,operand2); elsepush(exppos-48); / 是操作數(shù)，壓入操作數(shù)棧 pos+; / 移到下一個字符串位置pop(&result); / 彈出結(jié)果printf("%dn",result); /

9、輸出;case 8:caidan();break;case 9:printf("程序結(jié)束!");break;printf("n"); return 0; / 進(jìn)行棧的初始化的函數(shù) void InitStack(pStack ps) ps->Top = (pNode)malloc(sizeof(Node); / 分配內(nèi)存空間給棧頂 if (NULL = ps->Top) printf("動態(tài)分配內(nèi)存失敗n"); exit(-1); else ps->Bottom = ps->Top; ps->Top->

10、;pNext = NULL; printf("棧已經(jīng)進(jìn)行了初始化!"); printf("n"); return ; / 進(jìn)行入棧操作的函數(shù) bool Push(pStack ps,char data) pNode pNew = (pNode)malloc(sizeof(Node); 間if (NULL = pNew) return false; pNew->member = data; member成員pNew->pNext = ps->Top; ps->Top = pNew; printf("n"); re

11、turn true; / 遍歷棧的函數(shù)void TraverseStack(pStack ps) pNode pNew = ps->Top;/ 使棧底也指向棧頂空間 / 棧頂指針置為NULL； / 定義一個新節(jié)點，并分配內(nèi)存空 / 把要進(jìn)棧的數(shù)據(jù)賦給新節(jié)點的 / 使新節(jié)點的指針指向棧頂 / 把新節(jié)點作為新棧頂if (Empty(ps) /判斷棧是否為空，為空就不能進(jìn)行出棧操作 printf("棧已為空!n");elseprintf("棧頂元素為:");printf("%cn",pNew->member);printf(&q

12、uot;棧內(nèi)的元素有:");while(pNew!= ps->Bottom) / 只要棧頂不等于棧底，循環(huán) printf("%c ",pNew->member); / 打印棧頂?shù)某蓡Tmember pNew = pNew->pNext; / 棧頂指針向下移動一次 printf("n");return ;/ 判斷棧是否為空bool Empty(pStack ps)if(ps->Top = ps->Bottom) / 棧頂?shù)扔跅５祝痪褪菞Ｖ袥]數(shù)據(jù)么 return true;elsereturn false;printf

13、("n");/ 進(jìn)行出棧操作函數(shù)int Pop(pStack ps)pNode pSwap = NULL;int return_val;if (Empty(ps) /判斷棧是否為空，為空就不能進(jìn)行出棧操作 printf("n棧中數(shù)據(jù)不足無法完整出棧!n");elsereturn_val = ps->Top->member; / 把棧頂?shù)某蓡Tmember的值賦給return_val做為函數(shù)返回值pSwap = ps->Top; / 使pSwap指向棧頂ps->Top = ps->Top->pNext; / 使棧頂指向棧頂

14、下一個節(jié)點free(pSwap); / 釋放以前的棧頂空間return return_val;printf("n");/ 清空棧的函數(shù)void Clear(pStack ps)pNode pNew = NULL;while (ps->Top != ps->Bottom) / 棧頂和棧底不等，循環(huán)pNew = ps->Top; / 使一個新節(jié)點和棧頂指向同一空間 ps->Top = ps->Top->pNext; / 使棧頂指向棧頂?shù)南乱粋€節(jié)點 free(pNew); / 釋放掉以前的棧頂空間printf("棧已清空!n"

15、;);return ;/顯示菜單函數(shù)void caidan()printf("*n");printf("* 1初始化棧 *n");printf("* 2入棧 *n");printf("* 3出棧 *n");printf("* 4遍歷棧中元素并顯示棧頂元素*n");printf("* 5清空棧 *n");printf("* 6棧的中序轉(zhuǎn)后序 *n");printf("* 7棧后序表達(dá)式的計算 *n");printf("* 8退出

16、程序 *n");printf("* 9顯示菜單 *n");printf("*n");/中序轉(zhuǎn)后序函數(shù)void fun( char a,char b) int i,len,j;len=strlen(a);j=-1;for(i=0;i<len;i+)switch(ai)case '(':stock+top='('break;case '-':case '+':while(top>=0&&stocktop!='(') b+j=stocktop-

17、;stock+top=' 'stock+top=ai;break;case '*':case '/':while(top>=0&&stocktop!='('&&stocktop!='+'&&stocktop!='-') b+j=stocktop-;stock+top=' 'stock+top=ai;break;case')':while(stocktop!='(')b+j=stocktop-;top-;break;default:b+j=ai;if(i=len-1)b+j=' 'break;elseif(ai+1<='0'|ai+1>='9')b+j=' 'while(top>=0)b+j=stocktop-;b+j='0'for(i=0;i<=j;i+)printf("%c",bi);int getvalue(int op,int operand1,int operand2) / 計算表達(dá)式值 char exp100; int