python順序棧實現迴文詩的簡單介紹

本文目錄一覽：

• 1、關於順序棧的實現
• 2、（二）用順序棧實現算術後綴表達式求值
• 3、假設稱正讀和反讀都相同的字元序列為「迴文」，例如，『abba』和『abcba』是迴文，『abcde』和『ababab』
• 4、編寫一個演算法程序實現在一個順序棧中把一個字元串逆置的運算，要求使用入棧和出棧運算來完成。

關於順序棧的實現

#include”stdio.h”

#includeiostream.h

#includemalloc.h

#includestring.h

#define STACK_INIT_SIZE 200

struct Stack{

int *base;

int *top;

}sq;

void InitStack(Stack s){

s.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));

s.top=s.base;

};

void Push(Stack s,int e){

*s.top=e;

s.top++;

};

int Pop(Stack s){//設從鍵盤輸入一整數的序列：a1,a2,a3,……an，

s.top–;

return *s.top;//試編寫演算法實現：用棧結構存儲輸入的整數，

};//當ai≠—1時，將ai進棧，噹噹ai≠—1時，將所有棧元素出

void main()//棧。演算法應對異常情況（如棧滿等）給出相應的信息》

{

Stack S1,S2;

InitStack(S1);

InitStack(S2);

int a[10];

int i=0,b;

while(i10){

cout”請輸入第”i”個元素”endl;

cina[i];

if(a[i]==-1)

break;

Push(S1,a[i]);

i++;}

while(S1.top!=S1.base){

b=Pop(S1);

coutbendl;}

}

上次把類型定義錯了 以前是只能使用小於128的 現在把類型改成int了就使用任何數字了

（二）用順序棧實現算術後綴表達式求值

include malloc.h

#include stdio.h

#include ctype.h//判斷是否為字元的函數的頭文件

#define maxsize 100

typedef int elemtype;

typedef struct sqstack sqstack;//由於sqstack不是一個類型 而struct sqstack才是

char ch[7]=;//把符號轉換成一個字元數組

int f1[7]=;//棧內元素優先順序

int f2[7]=;//棧外的元素優先順序

struct sqstack

{

elemtype stack[maxsize];

int top;

};

void Initstack(sqstack *s)

{

s-top=0;

}

void Push(sqstack *s,elemtype x)

{

if(s-top==maxsize-1)

printf(“Overflow\n”);

else

{

s-top++;

s-stack[s-top]=x;

}

}

void Pop(sqstack *s,elemtype *x)

{

if(s-top==0)

printf(“underflow\n”);

else

{

*x=s-stack[s-top];

s-top–;

}

}

elemtype Gettop(sqstack s)

{

if(s.top==0)

{

printf(“underflow\n”);

return 0;

}

else

return s.stack[s.top];

}

elemtype f(char c)

{

switch(c)

{

case ‘+’:

return 0;

case ‘-‘:

return 1;

case ‘*’:

return 2;

case ‘/’:

return 3;

case ‘(‘:

return 4;

case ‘)’:

return 5;

default:

return 6;

}

}

char precede(char c1,char c2)

{

int i1=f(c1);

int i2=f(c2);//把字元變成數字

if(f1[i1]f2[i2])//通過原來設定找到優先順序

return ”;

else if(f1[i1]f2[i2])

return ”;

else

return ‘=’;

}

int Operate(elemtype a,elemtype theta,elemtype b)

{

int sum;

switch(theta)

{

case 0:

sum=a+b;

break;

case 1:

sum=a-b;

break;

case 2:

sum=a*b;

break;

default:

sum=a/b;

}

return sum;

}

EvaluateExpression()

{

char c;

int i=0,sum=0;

int k=1,j=1;//設置了開關變數

elemtype x,theta,a,b;

sqstack OPTR,OPND;

Initstack(OPTR);

Push(OPTR,f(‘#’));//0壓入棧

Initstack(OPND);

c=getchar();

if(c==ch[2]||c==ch[3]||c==ch[5]||c==ch[6])//先對＋和-的情況忽略和左括弧的情況

{

printf(“錯誤1 \n”);

k=0;

return 0;

}

if(c==ch[0])

c=getchar();//如果是＋，把它覆蓋

if(c==ch[1])

{

j=0;

c=getchar();//也把－號覆蓋

}

while(c!=’#’||ch[Gettop(OPTR)]!=’#’)

{

if(isdigit(c))

{

sum=0;

while(isdigit(c))

{

if(!j)

{

sum=sum*10-(c-‘0’);//實現了數字串前面有負號（之前是：sum=-(sum*10)-(c-‘0’)結果是－12＋13＝21）

}

else

sum=sum*10+(c-‘0’);

c=getchar();

}

Push(OPND,sum);//如果還是數字先不壓棧，把數字串轉化成十進位數字再壓棧

j=1;

}

else

if(k)

{

switch(precede(ch[Gettop(OPTR)],c))

{

case”: Push(OPTR,f(c));//把它們整型化

c=getchar();

if(c==ch[0]||c==ch[1]||c==ch[2]||c==ch[3]||c==ch[5]||c==’\n’)//要除去下個是『（』的情況 也把以運算符歸到這裡來

{

printf(“出錯2\n”);

k=0;

return 0;//加了開關變數和返回0的值使程序更以操作

}

break;

case’=’: Pop(OPTR,x);

c=getchar();

if(c==ch[0]||c==ch[1]||c==ch[2]||c==ch[3]||c==ch[5]||c==’\n’)//把ch[6]的情況也忽略了但此時並沒有注意到右括弧後面右運算符的情況

{

printf(“出錯2\n”);

k=0;

return 0;

}

break;

case”: Pop(OPTR,theta);

Pop(OPND,b);

Pop(OPND,a);//注意這裡是誰先出棧

Push(OPND,Operate(a,theta,b));

break;

}

}

}//在這裡判斷是否以運算符結束是不對的

return(Gettop(OPND));

}

main()

{

int result;

printf(“輸入你的算術表達式：\n”);

result=EvaluateExpression();

printf(“結果是 :%d\n”,result);

return 0;

}

:

本計算器利用堆棧來實現。

1、定義後綴式計算器的堆棧結構

因為需要存儲的單元不多，這裡使用順序棧，即用一維數組來模擬堆棧：

#define MAX 100

int stack[MAX];

int top=0;

因此程序中定義了長度為MAX的一維數組，這裡MAX用宏定義為常數100，我們可以修改宏定義而重新定義堆棧的大小。

整型數據top為棧頂指示，由於程序開始時堆棧中並無任何數據元素，因此top被初始化為0。

2、存儲後綴式計算器的運算數

我們定義了堆棧stack[MAX]後，就可以利用入棧操作存儲先後輸入的兩個運算數。

下面看一下是如何實現的：

int push(int i) /*存儲運算數，入棧操作*/

{

if(topMAX)

{

stack[++top]=i; /*堆棧仍有空間，棧頂指示上移一個位置*/

return 0;

}

else /*堆棧已滿，給出錯誤信息，返回出錯指示*/

{

printf(“The stack is full”);

return ERR;

}

}

我們在調用函數push時，如果它的返回值為0，說明入棧操作成功；否則，若返回值為ERR(在程序中說明為-1)，說明入棧操作失敗。

3、從堆棧中取出運算數

當程序中讀完了四則運算符後，我們就可以從堆棧中取出已經存入的兩個運算數，構成表達式，計算出結果。取出運算數的函數採用的正是出棧演算法。在本例中，實現該演算法的函數 為pop():

int pop(); /*取出運算數，出棧操作*/

{

int var; /*定義待返回的棧頂元素*/

if(top!=NULL) /*堆棧中仍有數據元素*/

{

var=stack[top–]; /*堆棧指示下移一個位置*/

return var;

}

else /*堆棧為空，給出錯誤信息，並返回出錯返回值*/

printf(“The stack is cmpty!\n”);

return ERR;

}

同樣，如果堆棧不為空，pop()函數返回堆棧頂端的數據元素，否則，給出棧空提示，並返回錯誤返回值ERR。

4、設計完整的後綴式計算器

有了堆棧存儲運算數，後綴式計算器的設計就很簡單了。程序首先提示用戶輸入第一個運算數，調用push()函數存入堆棧中；而後提示用戶輸入第二個運算數，同樣調用push()函數存入堆棧中。接下來，程序提示用戶輸入+,-,*,/四種運算符的一種，程序通過switch_case結構判斷輸入運算符的種類，轉而執行不同的處理代碼。以除法為例，說明程序的執行流程：

case ‘/’:

b=pop();

a=pop();

c=a/b;

printf(“\n\nThe result is %d\n”,c);

printf(“\n”);

break;

程序判斷用戶輸入的是除號後，就執行上述代碼。首先接連兩次調用pop()函數從堆棧中讀出先前輸入的運算數，存入整型數a和b中；然後執行除法運算，結果存入單元c中。這時需要考慮究竟誰是被除數，誰是除數。由於開始我們先將被除數入棧，根據堆棧「先進後出」的原則，被除數應該是第二次調用pop()函數得到的返回值。而除數則是第一次調用pop()函數得到的返回值。

最後程序列印出運算結果，並示提示用戶是否繼續運行程序：

printf(“\t Continue?(y/n):”);

l=getche();

if(l==’n’)

exit(0);

如果用戶回答是”n”，那麼結束程序，否則繼續循環。

完整的程序代碼如下：

#includestdio.h

#includeconio.h

#includestdlib.h

#define ERR -1

#define MAX 100 /*定義堆棧的大小*/

int stack[MAX]; /*用一維數組定義堆棧*/

int top=0; /*定義堆棧指示*/

int push(int i) /*存儲運算數,入棧操作*/

{

if(topMAX)

{

stack[++top]=i; /*堆棧仍有空間，棧頂指示上移一個位置*/

return 0;

}

else

{

printf(“The stack is full”);

return ERR;

}

}

int pop() /*取出運算數，出棧操作*/

{

int var; /*定義待返回的棧頂元素*/

if(top!=NULL) /*堆棧中仍有元素*/

{

var=stack[top–]; /*堆棧指示下移一個位置*/

return var; /*返回棧頂元素*/

}

else

printf(“The stack is empty!\n”);

return ERR;

}

void main()

{

int m,n;

char l;

int a,b,c;

int k;

do{

printf(“\tAriothmatic Operate simulator\n”); /*給出提示信息*/

printf(“\n\tPlease input first number:”); /*輸入第一個運算數*/

scanf(“%d”,m);

push(m); /*第一個運算數入棧*/

printf(“\n\tPlease input second number:”); /*輸入第二個運算數*/

scanf(“%d”,n);

push(n); /*第二個運算數入棧*/

printf(“\n\tChoose operator(+/-/*//):”);

l=getche(); /*輸入運算符*/

switch(l) /*判斷運算符，轉而執行相應代碼*/

{

case ‘+’:

b=pop();

a=pop();

c=a+b;

printf(“\n\n\tThe result is %d\n”,c);

printf(“\n”);

break;

case ‘-‘:

b=pop();

a=pop();

c=a-b;

printf(“\n\n\tThe result is %d\n”,c);

printf(“\n”);

break;

case ‘*’:

b=pop();

a=pop();

c=a*b;

printf(“\n\n\tThe result is %d\n”,c);

printf(“\n”);

break;

case ‘/’:

b=pop();

a=pop();

c=a/b;

printf(“\n\n\tThe result is %d\n”,c);

printf(“\n”);

break;

}

printf(“\tContinue?(y/n):”); /*提示用戶是否結束程序*/

l=getche();

if(l==’n’)

exit(0);

}while(1);

}

:

#include stdio.h

#include conio.h

#include malloc.h

#include stdlib.h

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int Status;

#define STACK_INIT_SIZE 100 //初始分配量

#define STACKINCREMENT 10 //存儲空間的分配增量

typedef char ElemType;

typedef ElemType OperandType; //操作數

typedef char OperatorType;

typedef struct

{

ElemType *base;

ElemType *top;

int stacksize;

}SqStack;

Status InitStack(SqStack S)

{

//構造一個空棧S

S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));

if(!S.base) exit (OVERFLOW);

S.top = S.base;

S.stacksize = STACK_INIT_SIZE;

return OK;

}

Status GetTop(SqStack S){

ElemType e;

if (S.top == S.base) return ERROR;

e = *(S.top-1);

return e;

}

Status Push (SqStack S,ElemType e)

{

//插入元素e為新的棧頂元素

if (S.top – S.base = S.stacksize){

S.base = (ElemType *) realloc ( S.base,

(S.stacksize + STACKINCREMENT) * sizeof(ElemType));

if(!S.base) exit (OVERFLOW);

S.top = S.base + S.stacksize;

S.stacksize += STACKINCREMENT;

}

*S.top++ = e;

return OK;

}

Status Pop (SqStack S,ElemType e){

//若棧不空，則刪除S的棧頂元素，用e返回其值，並返回OK；否則返回ERROR

if(S.top == S.base) return ERROR;

e = * –S.top;

return OK;

}

char In(char c,char OP[])

{

if(c=35 c=47)

return 1;

else return 0;

}

char OP[8]=;

int m[7][7]={1,1,2,2,2,1,1,

1,1,2,2,2,1,1,

1,1,1,1,2,1,1,

1,1,1,1,2,1,1,

2,2,2,2,2,0,-1,

1,1,1,1,-1,1,1,

2,2,2,2,2,-1,0};//1 2 0 = -1 不存在

char Precede(char i,char j)

{

int a,b; char *p;

for(p=OP,a=0;*p!=’\0′;p++,a++)

if(*p==i) break;

for(p=OP,b=0;*p!=’\0′;p++,b++)

if(*p==j) break;

if(m[a][b]==1) return ”;

else if(m[a][b]==2) return ”;

else if(m[a][b]==0) return ‘=’;

else return ‘O’;

}

char Operate(char a,char theta,char b)

{

if(a47) a=atoi(a);

if(b47) b=atoi(b);

switch(theta)

{

case ‘+’: return a+b;

break;

case ‘-‘: return a-b;

break;

case ‘*’: return a*b;

break;

case ‘/’: return a/b;

break;

}

}

OperandType EvaluateExpression()

{

SqStack OPTR,OPND;

OperandType a,b,c; OperatorType theta;

InitStack(OPTR); Push(OPTR,’#’);

InitStack(OPND); c=getchar();

while (c!=’#’ || GetTop(OPTR)!=’#’)

{

if (!In(c,OP))

else

switch(Precede(GetTop(OPTR),c))

{

case ” :

Push(OPTR,c); c = getchar();

break;

case ‘=’ :

Pop(OPTR,c); c = getchar();

break;

case ” :

Pop(OPTR,theta);

Pop(OPND,b); Pop(OPND,a);

Push(OPND,Operate(a,theta,b));

break;

}

}

return GetTop(OPND);

}

void main()

{

printf(“(以#為結束符)\n”);

printf(“請輸入：\n”);

int a;

a=(int)EvaluateExpression();

printf(“%d”,a);

getch();

}

:

ls都正確

:

C++ In Action這本書裡面有表達式求值的詳細項目分析.

:

數據結構的書裡面都有的,仔細看一下

:

studyall123的只能對0到9的數字運算才有效,對於10以上的數字就不行!不知道有沒有更好的方法!

:

現在的人，連google一下都懶啊

:

實際上是按照逆波蘭式的順序讓輸入的表達式入棧，再根據運算符優先順序來計算。

:

lenrning!

假設稱正讀和反讀都相同的字元序列為「迴文」，例如，『abba』和『abcba』是迴文，『abcde』和『ababab』

以前寫的，用循環隊列和順序棧實現的

也可以用指針實現

分別有兩個指針，一個指向開始，一個指向結尾，各取一個字元比較，相等的話，前邊的向後移動一個，後邊的向前移動一個，直到兩個指針指向同一個位置，則為迴文，中途要是不相等或者最後沒有指向同一個位置，則不是迴文

//**********題目****************//

//判斷用戶輸入的字元串是否為迴文

//迴文是指順讀和反讀都一樣的串

//例:abccba為迴文，abcdab不是迴文

//*****************************//

//數據結構:循環隊列和順序棧

//演算法思想:

//1.將字元串按照用戶輸入的順序分別入棧和隊列

//2.分別從隊列和棧中取出首個字元

//3.比較取出的字元，若相等，繼續分別從隊列和棧中取首個字元；否則跳出循環，並設置標誌flag=0;

//4.若隊列和棧中的字元取完，則結束，設置標誌flag=1;

//5.flag=1,表示字元從前往後和從後往前的序列完全匹配，該字元串屬於迴文

//6.flag=0,表示字元從前往後和從後往前的序列不完全匹配，該字元串不屬於迴文

#include stdio.h

#includestdlib.h

#define m 100

typedef struct

{

char stack[m];

int top;

}stackstru; // 定義棧

typedef struct {

char queue[m];

int front;

int rear;

}queuestru; //定義隊列

void main()

{

//函數聲明

int stinit(stackstru *s); //初始化順序棧

int stempty(stackstru *s); //判斷棧是否為空

int stpush(stackstru *s,char x); //入棧

char stpop(stackstru *s); //出棧

int quinit(queuestru *q); //初始化循環隊列

int quempty(queuestru *q); //判斷隊列是否為空

int enqueue(queuestru *q,char e); //入隊

char dequeue(queuestru *q); //出隊

//

char c;

int flag=0;

stackstru *s=(stackstru *)malloc(sizeof(stackstru)); //為順序棧申請空間

queuestru *q=(queuestru *)malloc(sizeof(queuestru)); //為隊列申請空間

stinit(s); //初始化棧

quinit(q); //初始化隊列

printf(“Input a string:\n”);//輸入字元串，輸入@標示輸入結束。

while((c=getchar())!=’@’) //將輸入的字元串入棧和隊列

{

putchar(c); //輸出輸入的字元

stpush(s,c); //字元進棧

enqueue(q,c); //字元進隊列

}

printf(“\n”);

printf(“End input!\n”); //提示信息

while(stempty(s)) //棧中還有元素

{

if(stpop(s)==dequeue(q)) //出棧的字元與出隊列的字元匹配

{

flag=1; //將標誌設置為1

continue; //繼續從棧和隊列中區字元

}

else //字元不匹配

{

flag=0;

break; //跳出循環，將標誌設置為0

}

}

if(flag==1)

printf(“This string is palindrome!\n”); //標誌位為1，完全匹配，是迴文

else

printf(“This string isn’t palindrome!\n”);//標誌位為0，不完全匹配，不是迴文

}

int stinit(stackstru *s)

{

s-top=0;

return 1;

} //初始化棧

int stempty(stackstru *s)

{

if(s-top==0) //棧頂為空

{

return 0;

}

else

{

return 1;

}

} //判斷棧是否空

int stpush(stackstru *s,char x)

{

if(s-top==m) //棧滿

{

printf(“The stack is overflow!\n”); //輸出提示信息

return 0;

}

else //棧未滿

{

s-top=s-top+1; //棧頂後移

s-stack[s-top]=x; //字元入棧

return 1;

}

} //入棧操作

char stpop(stackstru *s)

{

char y;

if(s-top==0) //棧為空

{

printf(“The stack is empty!\n”); //輸出提示信息

return ‘ ‘; //返回空格

}

else //棧不為空

{

y=s-stack[s-top]; //取出棧頂元素

s-top=s-top-1; //棧頂指示移動

return y;

}

} //出棧操作

int quinit(queuestru *q)

{

q-front=0;

q-rear=0;

return 1;

} //初始化為一個空的循環隊列

int quempty(queuestru *q)

{

if(q-front==q-rear) //隊頭和隊尾相等

{

return 0;

}

else

{

return 1;

}

} //判斷隊列是否為空

int enqueue(queuestru *q,char e)

{

if((q-rear+1)%m==q-front) //隊列已滿

{

printf(“The queue is overflow!\n”); //提示信息

return 0;

}

else

{

q-queue[q-rear]=e; //入隊

q-rear=(q-rear+1)%m; //移動隊尾指針

return 1;

}

} //入隊操作

char dequeue(queuestru *q)

{

char f;

if(q-front==q-rear) //隊列為空

{

printf(“The queue is empty!\n”); //提示信息

return 0;

}

else

{

f=q-queue[q-front]; //取出隊首元素

q-front=(q-front+1)%m; //移動對頭指針

return f;

}

} //出隊操作

編寫一個演算法程序實現在一個順序棧中把一個字元串逆置的運算，要求使用入棧和出棧運算來完成。

void ReverseString(char *a,int lenth) //逆轉函數

{

int i;

char c;

initstack(s);

for(i=0;ilenth;i++) Push(s,a[i]);

for(i=0;ilenth;i++) {Pop(s,c);a[i]=c;}

}

———————————————————————

typedef struct //循環隊列定義

{

int data[4];

int front;

int rear;

}SeqQueue;

void InitQueue(SeqQueue *Q) //初始化函數

{

Q-front=Q-rear=0;

}

int EnterQueue(SeqQueue *Q,int x) //入隊函數

{

if((Q-rear+1)%4==Q-front) return 0;

Q-data[Q-rear]=x;

Q-rear=(Q-rear+1)%4

return 1;

}

寫個main函數調用兩次入隊即可！