本文目录一览：
- 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函数调用两次入队即可！
