数据结构和算法-逆波兰表达式

荆轲

//逆波兰表达式

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



#define STACK_INIT_SIZE 20 //栈的初始化空间大小
#define STACKINCREMENT        10 //每次增加的栈空间大小
#define MAXBUFFER                10 //缓冲区大小

typedef double ElemType;

typedef struct
{
        int stackSize;
        ElemType *base;//指向栈底的指针
        ElemType *top;//指向栈顶的指针

}sqStack;

void initStack(sqStack *s)
{
        s->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
        if(!s->base)
        {
                exit(0);
        }
        s->top=s->base;
        s->stackSize=STACK_INIT_SIZE;
}

void Push(sqStack *s,ElemType e)//进栈
{
        if(s->top - s->base >= s->stackSize)
        {
                s->base=(ElemType *)realloc(s->base,(s->stackSize+STACKINCREMENT)*sizeof(ElemType));
                if(!s->base)
                {
                        exit(0);
                }

                s->top=s->base+s->stackSize;
                s->stackSize=s->stackSize+STACK_INIT_SIZE;//大小要更新，不然会误认为容量不够又继续申请内存
        }

        *(s->top)=e;//把e对应的元素压入栈顶
        s->top++;//栈顶上移
}

void Pop(sqStack *s,ElemType *e)//出栈
{
        if(s->top==s->base)//判断栈是不是空
        {
                return;
        }       
        *e=*--(s->top);
}


int stackLen(sqStack s)//计算栈的当前容量，s.stackSize
{
        return (s.top-s.base);
}


int main()
{
        char c;
        sqStack s;
        int i=0;
        double d,e;//临时变量
        char str[MAXBUFFER];//存放输入的数字

        initStack(&s);

        printf("请输入逆波兰表达式，数据与运算符之间用空格隔开，按#键结束!\n");
        scanf("%c",&c);

        while(c!='#')
        {
                while( isdigit(c)||c=='.')//判断c是数字，头文件ctype.h，过滤数字和点以外的数据
                {
                        str[i++]=c;
                        str[i]='\0';//给不知道下一个是否还要字符的位置赋结束符，以免不知道多长
                        if(i>=MAXBUFFER)//字符串溢出
                        {
                                printf("\n出错：输入的单个数据过长!\n");
                                return -1;
                        }
                        scanf("%c",&c);//继续输入数据
                        if(c==' ')//输入空格，代表单个数据输入结束
                        {
                                d=atof(str);//把字符串str转化为浮点数
                                Push(&s,d);
                                i=0;//i初始化，进入下一个循环
                                break;
                        }

                }

                switch(c)
                {
                        case '+'://两个出栈，并相加
                                Pop(&s,&e);//出栈第一个数，给e
                                Pop(&s,&d);//出栈第二个数，给d
                                Push(&s,d+e);
                                break;

                                case '-'://两个出栈，并相减
                                Pop(&s,&e);//出栈第一个数，给e
                                Pop(&s,&d);//出栈第二个数，给d
                                Push(&s,d-e);
                                break;

                                case '*'://两个出栈，并相乘
                                Pop(&s,&e);//出栈第一个数，给e
                                Pop(&s,&d);//出栈第二个数，给d
                                Push(&s,d*e);
                                break;

                                case '/'://两个出栈，并相除
                                Pop(&s,&e);//出栈第一个数，给e
                                Pop(&s,&d);//出栈第二个数，给d
                                if(e !=0)
                                {
                                        Push(&s,d+e);                                       
                                }
                                else
                                {
                                        printf("\n错误：除数为零!\n");
                                        return -1;
                                }
                                break;
                }

                scanf("%c",&c);
        }
       

        Pop(&s,&d);//最终的结算结果放在d里
        printf("计算结果为：%f\n",d);
        return 0;
}

hornwong