前几天做的一个数据结构上机实验

/*===========================================================*/
/*                 ** 中缀表达式的求值 **                    */
/*函数个数：4  包含2个自定义头文件(seqstack.h  seqstack1.h)  */
/*作者：踏网无痕                                             */
/*修改时间：31/05/04                                         */
/*在VC++6.0下调试                                            */
/*===========================================================*/

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>

typedef float DataType;        /*运算数的类型定义*/
#include "seqstack.h"

typedef struct                /*运算符的类型定义*/
{
    char op;
    int inputprecedence;    /*读入时的优先级*/
    int stackprecedence;    /*栈内的优先级*/
}DataType1;
#include "seqstack1.h"

DataType1 MathPotr(char);    /*给读入的运算符和左右括号配备优先级*/
void Evaluate(SeqStack *,DataType1);
                            /*执行从运算符栈弹出的运算符号所要求的运算*/
void Infix(char *);            /*将数、符分类压栈*/
int isoptr(char);            /*判断字符是否为运算符或左括号*/

/*
*主函数
*输入：空
*返回：空
*/
void main(void)
{
    char str[50];            /*声明接收表达式的字符串*/
    printf("Please input the expression(use \"=\" to end):");
    gets(str);                /*键盘读入用户的表达式*/
    Infix(str);                /*将表达式进行计算*/
}

/*
*功能：给读入的运算符和左右括号配备优先级
*输入：运算符和左右括号
*返回：运算符
*/
DataType1 MathOptr(char ch)
{
    DataType1 optr;
    optr.op=ch;

    switch(optr.op)
    {
        case '+':
        case '-':
            optr.inputprecedence=1;
            optr.stackprecedence=1;
            break;
        case '*':
        case '/':
            optr.inputprecedence=2;
            optr.stackprecedence=2;
            break;
        case '(':
            optr.inputprecedence=3;
            optr.stackprecedence=-1;
            break;
        case')':
            optr.inputprecedence=0;
            optr.stackprecedence=0;
            break;
    }
    return optr;
}

/*
*功能：执行从运算符栈弹出的运算符号optr所要求的运算
*输入：（运算数栈指针类型）运算数栈，（运算符栈元素类型）
*返回：空
*/
void Evaluate(SeqStack *OpndStack,DataType1 optr)
{
    DataType opnd1,opnd2;        /*声明两个运算数*/
    opnd1=popStack(OpndStack);    /*从数栈中弹出第一个数*/
    opnd2=popStack(OpndStack);    /*从数栈中弹出第二个数*/

    switch(optr.op)                /*由运算符决定运算数的计算规则*/
    {
        case'+':
            pushStack(OpndStack,opnd2+opnd1);
            break;
        case'-':
            pushStack(OpndStack,opnd2-opnd1);
            break;
        case'*':
            pushStack(OpndStack,opnd2*opnd1);
            break;
        case'/':
            pushStack(OpndStack,opnd2/opnd1);
            break;
    }
}

/*
*功能：将数、符分类压栈
*输入：（字符串指针）要分类处理的字符串
*返回：空
*/
void Infix(char *str)
{
    int i;                    /*数字字符串的计数变量*/
    int k;                    /*中缀表达式串的字符计数变量*/
    int n=strlen(str);        /*中缀表达式串的长度*/
    char ch;                /*用件处理的字符*/
    char numstr[10];        /*存储数字字符串*/

    DataType opnd;            /*临时存储一个数字*/
    DataType1 optr;            /*临时存储一个运算符*/

    SeqStack OpndStack;        /*运算数栈*/
    SeqStack1 OptrStack;    /*运算符栈*/

    setStack(&OpndStack,n);    /*初始化运算数栈*/
    setStack1(&OptrStack,n);/*初始化运算符栈*/

    k=0;                    /*标记表达式字符串的下标*/
    ch=str[k];                /*将字符串的第一个赋给ch*/
    while(ch!='=')

        /*如果是数字字符或小数点*/
        if(isdigit(ch)||ch=='.')    
        {
            for(i=0;isdigit(ch)||ch=='.';i++)
            {
                numstr[i]=ch;
                k++;
                ch=str[k];
            }
            numstr[i]='\0';
            opnd=(float)atof(numstr);
                            /*将字符串转化为实数*/
            pushStack(&OpndStack,opnd);
        }
        else
        {
            /*如果是运算符或左括号*/
            if(isoptr(ch))            
            {
                optr=MathOptr(ch);
                while(!isStackEmpty1(&OptrStack)&&getTopData1(&OptrStack).stackprecedence>=optr.inputprecedence)
                /*如果新进栈的算符优先级大的，则弹出数栈中的元素，计算后把结果压入数栈*/    
                    Evaluate(&OpndStack,popStack1(&OptrStack));
                pushStack1(&OptrStack,optr);/*算符入栈*/
                k++;
                ch=str[k];
            }

            /*如果是右括号*/
            else if(ch==')')        
            {
                optr=MathOptr(ch);
                while(!isStackEmpty1(&OptrStack)&&getTopData1(&OptrStack).stackprecedence>=optr.inputprecedence)
                    Evaluate(&OpndStack,popStack1(&OptrStack));
                popStack1(&OptrStack);    /*将栈中的左括号弹出*/
                k++;
                ch=str[k];
            }
        }

    /*如果运算符栈非空*/
    while(!isStackEmpty1(&OptrStack))
        Evaluate(&OpndStack,popStack1(&OptrStack));
    opnd=popStack(&OpndStack);
    printf("%-6.2f\n",opnd);    /*输出计算结果*/
    freeStack(&OpndStack);        /*释放数栈空间*/
    freeStack1(&OptrStack);        /*释放算符栈空间*/
}

/*
*功能：判断字符是否为运算符或左括号
*输入：字符
*返回：1（是），0（否）
*/
int isoptr(char ch)
{
    return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='(');
}


/*
* @SeqStack11.h    1.0   04/05/21
*
* @Author 踏网无痕
*
* @实现对顺序栈的基本操作，要求用户用已有类型定义DataType11
*/

typedef struct
{
    DataType1 *data;
    int max;
    int top;
}SeqStack1;

/*
*构造函数 建立数组长度为n的空栈
*输入：（栈类型指针）要初始化的栈的地址，（整型）栈长度
*返回：空
*/
void setStack1(SeqStack1 *s,int n)
{
    s->data=(DataType1 *)malloc(n*sizeof(DataType1));
    if(s->data==NULL)
    {
        printf("Overflow!\n");
        exit(1);
    }
    s->max=n;
    s->top=-1;
}

/*
*析构函数 释放数组空间
*输入：（栈类型指针）要释放栈的地址
*返回：空
*/
void freeStack1(SeqStack1 *s)
{
    free(s->data);
}

/*
*获得栈中数据个数
*输入：（栈类型指针）要求数据个数的栈的地址
*返回：（整型）栈中数据的个数
*/
int getStackSize1(SeqStack1 *s)
{
    return(s->top+1);
}

/*
*判断栈是否为空
*输入：（栈类型指针）要判断的栈的地址
*返回：（整型1或整型0）1为空，0不空
*/
int isStackEmpty1(SeqStack1 *s)
{
    return(s->top==-1);
}

/*
*判断栈是否已满
*输入：（栈类型指针）要判断的栈的地址
*返回：（整型1或整型0）1为满，0不满
*/
int isStackFull1(SeqStack1 *s)
{
    return(s->top==s->max-1);
}

/*
*取栈顶元素
*输入：（栈类型指针）要操作的栈的地址
*返回：（用户定义类型）栈顶元素的值
*/
DataType1 getTopData1(SeqStack1 *s)
{
    if(isStackEmpty1(s))
    {
        printf("Stack is empty!\n");
        exit(1);
    }
    return(s->data[s->top]);
}

/*
*元素入栈
*输入：（栈类型指针）要操作的栈的地址，（用户定义类型）要入栈的元素值
*返回：空
*/
void pushStack1(SeqStack1 *s,DataType1 item)
{
    if(isStackFull1(s))
    {
        printf("Stack is full!\n");
        exit(1);
    }
    s->top++;
    s->data[s->top]=item;
}

/*
*元素出栈
*输入：（栈类型指针）要操作的栈的地址
*返回：（用户定义类型）出栈的元素值
*/
DataType1 popStack1(SeqStack1 *s)
{
    if(isStackEmpty1(s))
    {
        printf("Stack is empty!\n");
        exit(1);
    }
    s->top--;
    return(s->data[s->top+1]);
}

/*
*清空栈
*输入：（栈类型指针）要操作的栈的地址
*返回：空
*/
void clearStack1(SeqStack1 *s)
{
    s->top=-1;
}








/*
* @seqstack.h    1.0   04/05/16
*
* @Author 踏网无痕
*
* @实现对顺序栈的基本操作，要求用户用已有类型定义DataType
*/

typedef struct
{
    DataType *data;
    int max;
    int top;
}SeqStack;

/*
*构造函数 建立数组长度为n的空栈
*输入：（栈类型指针）要初始化的栈的地址，（整型）栈长度
*返回：空
*/
void setStack(SeqStack *s,int n)
{
    s->data=(DataType *)malloc(n*sizeof(DataType));
    if(s->data==NULL)
    {
        printf("Overflow!\n");
        exit(1);
    }
    s->max=n;
    s->top=-1;
}

/*
*析构函数 释放数组空间
*输入：（栈类型指针）要释放栈的地址
*返回：空
*/
void freeStack(SeqStack *s)
{
    free(s->data);
}

/*
*获得栈中数据个数
*输入：（栈类型指针）要求数据个数的栈的地址
*返回：（整型）栈中数据的个数
*/
int getStackSize(SeqStack *s)
{
    return(s->top+1);
}

/*
*判断栈是否为空
*输入：（栈类型指针）要判断的栈的地址
*返回：（整型1或整型0）1为空，0不空
*/
int isStackEmpty(SeqStack *s)
{
    return(s->top==-1);
}

/*
*判断栈是否已满
*输入：（栈类型指针）要判断的栈的地址
*返回：（整型1或整型0）1为满，0不满
*/
int isStackFull(SeqStack *s)
{
    return(s->top==s->max-1);
}

/*
*取栈顶元素
*输入：（栈类型指针）要操作的栈的地址
*返回：（用户定义类型）栈顶元素的值
*/
DataType getTopData(SeqStack *s)
{
    if(isStackEmpty(s))
    {
        printf("Stack is empty!\n");
        exit(1);
    }
    return(s->data[s->top]);
}

/*
*元素入栈
*输入：（栈类型指针）要操作的栈的地址，（用户定义类型）要入栈的元素值
*返回：空
*/
void pushStack(SeqStack *s,DataType item)
{
    if(isStackFull(s))
    {
        printf("Stack is full!\n");
        exit(1);
    }
    s->top++;
    s->data[s->top]=item;
}

/*
*元素出栈
*输入：（栈类型指针）要操作的栈的地址
*返回：（用户定义类型）出栈的元素值
*/
DataType popStack(SeqStack *s)
{
    if(isStackEmpty(s))
    {
        printf("Stack is empty!\n");
        exit(1);
    }
    s->top--;
    return(s->data[s->top+1]);
}

/*
*清空栈
*输入：（栈类型指针）要操作的栈的地址
*返回：空
*/
void clearStack(SeqStack *s)
{
    s->top=-1;
}