栈与队列的应用

实验题目

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.