数据结构实验三 栈的应用(算术表达式求值)

一、实验目的

1.掌握栈和队列的两种存储结构；

2.掌握栈和队列的实现；

3.掌握栈和队列的应用。

二、实验相关知识

1.复习C语言文件读写的相关知识

2.复习课本中第3章关于栈和队列的相关知识点；

三、实验内容与要求

1.编程实现对算术表达式的求值。

【设计要求】输入包含+-*/四种运算，以及包含()括号的合法算术表达式，并计算其值，表达式以#开始，并以#结束。

【测试用例】

#(3)#   

#3+4#

#3+4*2#

#(3+4)*2#

#(2*(3+4)-2)+(3-1)#

#(11+12)*16#

【栈应用分析】以测试用例：#16 * (11+12) #  为例，分析栈操作的过程，详细见“算术表达式计算的栈操作过程.ppt”文件。

四、程序代码及运行结果

【程序代码】

#include 

using namespace std;

#define TRUE 1

#define FALSE 0

#define Stack_Size 50

/*int栈*/

typedef struct

{

    int elem[Stack_Size]; /*用来存放栈中元素的一维数组*/

    int top;                  /*用来存放栈顶元素的下标，top为-1表示空栈*/

}IntStack;

/*char栈*/

typedef struct

{

    char elem[Stack_Size]; /*用来存放栈中元素的一维数组*/

    int top;                  /*用来存放栈顶元素的下标，top为-1表示空栈*/

}CharStack;

/*初始化int栈*/

void InitStack(IntStack *&S)

{

    S = (IntStack *)malloc(sizeof(IntStack));

    S->top = -1;

}

/*初始化char栈*/

void InitStack(CharStack *&S)

{

    S = (CharStack *)malloc(sizeof(CharStack));

    S->top = -1;

}

/*判栈空*/

int IsEmpty(IntStack *S) /*判断栈S为空栈时返回值为真，反之为假*/

{

    return(S->top == -1 ? TRUE : FALSE);

}

/*判栈空*/

int IsEmpty(CharStack *S) /*判断栈S为空栈时返回值为真，反之为假*/

{

    return(S->top == -1 ? TRUE : FALSE);

}

/*判栈满*/

int IsFull(IntStack *S)    /*判断栈S为满栈时返回值为真，反之为假*/

{

    return(S->top == Stack_Size - 1 ? TRUE : FALSE);

}

/*判栈满*/

int IsFull(CharStack *S)    /*判断栈S为满栈时返回值为真，反之为假*/

{

    return(S->top == Stack_Size - 1 ? TRUE : FALSE);

}

/*进栈*/

int Push(CharStack *&S, char x)

{

    if (S->top == Stack_Size - 1)

        return(FALSE);  /*栈已满*/

    S->top++;

    S->elem[S->top] = x;

    return(TRUE);

}

/*进栈*/

int Push(IntStack *&S, int x)

{

    if (S->top == Stack_Size - 1)

        return(FALSE);  /*栈已满*/

    S->top++;

    S->elem[S->top] = x;

    return(TRUE);

}

/*出栈*/

int Pop(IntStack *&S, int &x)

{

    /* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */

    if (S->top == -1) /*栈为空*/

        return(FALSE);

    else

    {

        x = S->elem[S->top];

        S->top--; /* 修改栈顶指针 */

        return(TRUE);

    }

}

/*出栈*/

int Pop(CharStack *S, char &x)

{

    /* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */

    if (S->top == -1) /*栈为空*/

        return(FALSE);

    else

    {

        x = S->elem[S->top];

        S->top--; /* 修改栈顶指针 */

        return(TRUE);

    }

}

/*取栈顶元素。*/

int GetTop(IntStack *S, int &x)

{

    /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */

    if (S->top == -1) /*栈为空*/

        return(FALSE);

    else

    {

        x = S->elem[S->top];

        return(TRUE);

    }

}

/*取栈顶元素。*/

int GetTop(CharStack *S, char &x)

{

    /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */

    if (S->top == -1) /*栈为空*/

        return(FALSE);

    else

    {

        x = S->elem[S->top];

        return(TRUE);

    }

}

void trans(char *exp, char postexp[])

{

    char e;

    CharStack *Optr;

    InitStack(Optr);

    int i = 0;

    while (*exp != '\\0')

    {

        switch (*exp)

        {

        case'(':

            Push(Optr, '(');

            exp++;

            break;

        case')':

            Pop(Optr, e);

            while (e != '(')

            {

                postexp[i++] = e;

                Pop(Optr, e);

            }

            exp++;

            break;

        case'+':

        case'-':

            while (!IsEmpty(Optr))

            {

                GetTop(Optr, e);

                if (e != '(')

                {

                    postexp[i++] = e;

                    Pop(Optr, e);

                }

                else break;

            }

            Push(Optr, *exp);

            exp++;

            break;

        case'*':

        case'/':

            while (!IsEmpty(Optr))

            {

                GetTop(Optr, e);

                if (e == '*' || e == '/')

                {

                    postexp[i++] = e;

                    Pop(Optr, e);

                }

                else break;

            }

            Push(Optr, *exp);

            exp++;

            break;

        default:

            while (*exp >= '0'&&*exp <= '9')

            {

                postexp[i++] = *exp;

                exp++;

            }

            postexp[i++] = '#';

        }

    }

    while (!IsEmpty(Optr))

    {

        Pop(Optr, e);

        postexp[i++] = e;

    }

    postexp[i] = '\\0';

    /*DestroyStack(Optr);*/

}

double compvalue(char *postexp)

{

    int d = 0, a = 0, b = 0, c = 0, e = 0;

    IntStack *Opnd;//定义操作数栈

    InitStack(Opnd);            //初始化操作数栈

    while (*postexp != '\\0')        //postexp字符串未扫描完时循环

    {

        switch (*postexp)

        {

        case '+':            //判定为'+'号

            Pop(Opnd, a);        //出栈元素a

            Pop(Opnd, b);        //出栈元素b

            c = b + a;            //计算c

            Push(Opnd, c);        //将计算结果c进栈

            break;

        case '-':                //判定为'-'号

            Pop(Opnd, a);        //出栈元素a

            Pop(Opnd, b);        //出栈元素b

            c = b - a;            //计算c

            Push(Opnd, c);        //将计算结果c进栈

            break;

        case '*':                //判定为'*'号

            Pop(Opnd, a);        //出栈元素a

            Pop(Opnd, b);        //出栈元素b

            c = b*a;            //计算c

            Push(Opnd, c);        //将计算结果c进栈

            break;

        case '/':                //判定为'/'号

            Pop(Opnd, a);        //出栈元素a

            Pop(Opnd, b);        //出栈元素b

            if (a != 0)

            {

                c = b / a;            //计算c

                Push(Opnd, c);        //将计算结果c进栈

                break;

            }

            else

            {

                printf("\\n\除零错误!\\n");

                exit(0);            //异常退出

            }

            break;

        default:            //处理数字字符

            d = 0;        //转换成对应的数值存放到d中

            while (*postexp >= '0' && *postexp <= '9')

            {

                d = 10 * d + *postexp - '0';

                postexp++;

            }

            Push(Opnd, d);    //将数值d进栈

            break;

        }

        postexp++;        //继续处理其他字符

    }

    GetTop(Opnd, e);        //取栈顶元素e

    return e;            //返回e

}

int main(int heng, char * heng1[])

{

    char exp[Stack_Size];

    int i = 0;

    gets_s(exp);

    char postexp[Stack_Size];

    trans(exp, postexp);

    printf("中缀表达式:%s\\n", exp);

    printf("后缀表达式:%s\\n", postexp);

    printf("表达式的值:%g\\n", compvalue(postexp));

    return 0;

}

【运行结果】

【算法描述】

（1）将算术表达式转换成后缀表达式

    exp => postexp

    扫描exp的所有字符：

        数字字符直接放在postexp中

        运算符通过一个栈来处理优先级

            情况1（没有括号）

                先进栈的先退栈即先执行：

                只有大于栈顶优先级才能直接进栈

                exp扫描完毕，所有运算符退栈

            情况2（带有括号）

                开始时，任何运算符都进栈

                (：一个子表达式开始，进栈

                栈顶为(：任何运算符进栈

                )：退栈到（

                只有大于栈顶的优先级，才进栈；否则退栈

（2）后缀表达式求值

    postexp => 值

    扫描postexp的所有字符：

        数字字符：转换为数值并进栈

        运算符：退栈两个操作数，计算，将结果进栈

五、实验心得体会

通过这次试验，我对栈有了新的理解和认识。