实验题目
1：依据顺序栈存储结构的定义如下：（利用以下的常用操作设计算法并实现完成 2、3 题）
#define MAXSIZE 100
typedef char SElemType;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
//调试并测试常用操作如下：
int InitStack( SqStack &S )
int StackEmpty( SqStack S )
int StackLength( SqStack S )
int Push( SqStack &S, SElemType e)
int Pop( SqStack &S, SElemType &e)
2：设单链表中存放 n 个字符，试设计一个算法，判断该字符串是否中心对称。
3：利用栈来实现算术表达式求值的算法。程序运行时，输入合法的算术表达式（中间值及最终结果要在 0 ～ 9 之间，可以包括加减乘除和括号），便可输出相应的计算结果。
头文件
#ifndef _STACK_H_
#define _STACK_H_
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef char SElemType;
using namespace std;
typedef struct//栈结构体
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
typedef struct LNode//单链表结构体
{
SElemType data;
struct LNode *next;
}LNode,*LinkList;
//初始化栈
Status InitStack(SqStack &S){
S.base = new SElemType [MAXSIZE];
if (!S.base)
exit(OVERFLOW);
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
//判断栈满栈空
Status StackEmpty(SqStack S){
if(S.top - S.base == S.stacksize)
return ERROR;
else return OK;
}
//求栈长
int StackLength(SqStack S){
return (S.top - S.base);
}
//入栈函数
Status Push(SqStack &S,SElemType e){
if(StackEmpty(S)){
*S.top++ = e;
return OK;
}
else return ERROR;
}
//出栈函数
Status Pop(SqStack &S,SElemType &e){
if(S.top == S.base)
return ERROR;
e = *--S.top;
return OK;
}
//取栈顶元素
SElemType GetTop(SqStack S){
if(S.top != S.base){
return *(S.top-1);
}
else return ERROR;
}
//创建单链表
void CreateList_L(LinkList &L,int n){
L=new LNode;
L->next=NULL; //先建立一个带头结点的单链表
LinkList p;
// InitList_L(L);
for(int i=n;i>0;--i){
p=new LNode; //生成新结点
cin>>p->data; //输入元素值
p->next=L->next;L->next=p; //插入到表头
}
}
//打印单链表
void PrintList_L(LinkList &L){
LinkList p=L->next;
while(p) {
cout<<p->data<<endl;
p=p->next;
}
}
//单链表删除元素
Status ListDelete(LinkList &L,int i){
LinkList p=L,q;
int j=0;
while((p->next) && (j<i-1)){
p=p->next;
++j;
}
if(!(p->next) || (j>i-1))
return ERROR;
q=p->next;
p->next=q->next;
delete q;
return OK;
}
//获取单链表元素值
Status GetElem(LinkList L,int i,SElemType &e){
LinkList p=L->next;
int j=1;
while (p && j<i){
p=p->next;
++j;
}
if(!p || j>i)
return ERROR;
e=p->data;
return OK;
}
#endif // _STACK_H_
main.cpp
#include "stack.h"
Status TestStack(SqStack &S,SElemType &e);
int Center(LinkList &L,SqStack &S);
char EvaluateExpression ();
SElemType Precede(SElemType t1,SElemType t2);
Status In(SElemType c);
SElemType Operate(SElemType a,SElemType theta,SElemType b);
int main()
{
LinkList L;
SqStack S;
SElemType e;
//SqStack *p = &S;
printf("第1题\n");
TestStack(S,e);
//cout << "" << endl;
printf("第2题\n");
printf("请输入要判断中心对称的字符串，长度为5\n");
CreateList_L(L,5);
ListDelete(L,3);
//PrintList_L(L);
if(Center(L,S))
printf("该字符串不是中心对称的字符串\n");
else
printf("该字符串是中心对称的字符串\n");
printf("第3题\n");
cout<<"请输入算术表达式,并以#结束."<<endl;
cout<<EvaluateExpression()<<endl;
return 0;
}
//栈基础测试函数
Status TestStack(SqStack &S,SElemType &e){
InitStack(S);
cout << "当前栈的长度为：" ;
cout << StackLength(S) << endl;
cout << "请输入将要入栈的元素：" << endl;
cin >> e;
Push(S,e);
cout << "当前栈的长度为：" ;
cout << StackLength(S) << endl;
Pop(S,e);
cout << "出栈：" ;
cout << e <<endl;
cout << "当前栈的长度为：" ;
cout << StackLength(S) << endl;
return OK;
}
//判断是否中心对称
int Center(LinkList &L,SqStack &S){
int i;
SElemType e;
for(i=1;i<=4;i++){
GetElem(L,i,e);
if(e == GetTop(S)){
Pop(S,e);
}else{
Push(S,e);
}
}
if(StackLength(S))
return 1;
return 0;
//GetElem(LinkList L,int i,SElemType &e)
}
char EvaluateExpression() {//算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和操作数栈
SqStack OPTR, OPND;
char ch, theta, a, b, x;
InitStack(OPND); //初始化OPND操作数栈
InitStack(OPTR); //初始化OPTR运算符栈
Push(OPTR, '#'); //将表达式起始符“#”压入OPTR栈
scanf("%c",&ch);
while (ch != '#' || (GetTop(OPTR) != '#')) //表达式没有扫描完毕或OPTR的栈顶元素不为“#”
{
if (!In(ch)) {
Push(OPND, ch);
scanf("%c",&ch);
} //ch不是运算符则进OPND栈
else
switch (Precede(GetTop(OPTR), ch)) //比较OPTR的栈顶元素和ch的优先级
{
case '<': //栈顶元素优先级低
Push(OPTR, ch);
scanf("%c",&ch); //当前字符ch压入OPTR栈，读入下一字符ch
break;
case '>':
Pop(OPTR, theta); //弹出OPTR栈顶的运算符
Pop(OPND, b);
Pop(OPND, a); //弹出OPND栈顶的两个运算数
Push(OPND, Operate(a, theta, b)); //将运算结果压入OPND栈
break;
case '=': //OPTR的栈顶元素是“(”且ch是“)”
Pop(OPTR, x);
scanf("%c",&ch); //弹出OPTR栈顶的“(”，读入下一字符ch
break;
} //switch
} //while
return GetTop(OPND); //OPND栈顶元素即为表达式求值结果
}
Status In(SElemType c)// 应在前面有定义typedef char SElemType;
{ // 判断c是否为运算符
switch(c)
{
case '+':return true;break;
case '-':return true;break;
case '*':return true;break;
case '/':return true;break;
case '(':return true;break;
case ')':return true;break;
case '#':return OVERFLOW;break;
default:return false;
}
}
SElemType Precede(SElemType t1,SElemType t2)
{ //根据教材表3.1，判断两个运算符的优先关系
SElemType f;
switch(t2)
{
case '+':
if(t1=='('||t1=='#')
f='<';
else
f='>';
break;
case '-':
if(t1=='('||t1=='#')
f='<';
else
f='>';
break;//……//补充完整
case '*':
if(t1=='*' || t1=='/' || t1==')')
f='>';
else
f='<';
break;
case '/':
if(t1=='*' || t1=='/' || t1==')')
f='>';
else
f='<';
break;
case '(':
f='<';
break;
case ')':
if(t1=='(')
f='=';
else
f='>';
break;
case '#':
if(t1=='#')
f='=';
else
f='>';
break;
}
return f;
}
SElemType Operate(SElemType a,SElemType theta,SElemType b)
{
SElemType c;
a=a-48;
b=b-48;
switch(theta)
{
case'+':c=a+b+48;
break;//……//补充完整
case'-':c=a-b+48;
break;
case'*':c=a*b+48;
break;
case'/':c=a/b+48;
break;
}
return c;
}
实验运行结果
第1题
当前栈的长度为：0
请输入将要入栈的元素：
1
当前栈的长度为：1
出栈：1
当前栈的长度为：0
第2题
请输入要判断中心对称的字符串，长度为5
1
2
3
4
5
该字符串不是中心对称的字符串
第3题
请输入算术表达式,并以#结束.
1+3/3+(2*3)-2#
6
Process returned 0 (0x0) execution time : 37.894 s
Press any key to continue.
第1题
当前栈的长度为：0
请输入将要入栈的元素：
1
当前栈的长度为：1
出栈：1
当前栈的长度为：0
第2题
请输入要判断中心对称的字符串，长度为5
1
2
3
2
1
该字符串是中心对称的字符串
第3题
请输入算术表达式,并以#结束.
1+3*2-3/3#
6
Process returned 0 (0x0) execution time : 28.153 s
Press any key to continue.