您的位置:

python顺序栈实现回文诗的简单介绍

本文目录一览:

关于顺序栈的实现

#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函数调用两次入队即可!