ysbd.txt

数据结构：栈的应用 数据结构：栈的应用 数据结构：栈的应用 数据结构：栈的应用

#include<stdio.h>
#include<iostream.h>
#include <math.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAXN 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int status;

typedef struct {
    char *base,*top;
    int stacksize;
}sqstack_sign;	//运算符栈的定义

typedef struct{
    float *base,*top;
    int stacksize;
}sqstack_num;	//运算数栈的定义

int isp(char a)
{//栈内优先数
    switch(a)
	{case'*':
	case'/':return(2);
	case'+':
	case'-':return(1);
	case'(':return(0);
	case'#':return(-1);
	}
};

int icp(char a)
{//栈外优先数
    switch(a)
	{case'*':
	case'/':return(2);
	case'+':
	case'-':return(1);
	case'(':return(3);
	}
};

status initstack1(sqstack_sign &s)
{//栈的初始化
    s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));
    if(!s.base)exit(OVERFLOW);
    s.top=s.base;
    s.stacksize=STACK_INIT_SIZE; return OK;
};

status gettop1(sqstack_sign s, char &e)
{//取栈顶元素
    if(s.top==s.base)return ERROR;
    e=*(s.top-1); return OK;
};

status push1(sqstack_sign &s,char e)
{//进栈
    if(s.top-s.base>=s.stacksize)
	{
        s.base=(char*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char));
        if(!s.base)exit(OVERFLOW);
        s.top=s.base+s.stacksize;
        s.stacksize+=STACKINCREMENT;
    }
    *s.top++=e; return OK;
};

status pop1(sqstack_sign &s,char &e)
{//出栈
    if(s.top==s.base)return ERROR;
    e=*--s.top; return OK;
};

status  initstack2(sqstack_num &s)
{//栈的初始化
    s.base=(float*)malloc(STACK_INIT_SIZE*sizeof(float));
    if(!s.base)exit(OVERFLOW);
    s.top=s.base;
    s.stacksize=STACK_INIT_SIZE; return OK;
};

status gettop2(sqstack_num s, float &e)
{//取栈顶元素
    if(s.top==s.base)return ERROR;
    e=*(s.top-1); return OK;
};

float push2(sqstack_num &s,float e)
{//进栈
    if(s.top-s.base>=s.stacksize){
        s.base=(float*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(float));
        if(!s.base)exit(OVERFLOW);
        s.top=s.base+s.stacksize;
        s.stacksize+=STACKINCREMENT;
    }
    *s.top++=e; return OK;
};

float pop2(sqstack_num &s,float &e)
{//出栈
    if(s.top==s.base)return ERROR;
    e=*--s.top; return OK;
};

status mid_to_pos(char mid_e[],char pos_e[])
{//中缀表达式转换后缀表达式
    int i,j,k; 
    char c,ea,eb,ec;
    sqstack_sign optr;
    initstack1(optr);ec='#';
    push1(optr,ec);	//optr栈的初始化，栈底为#
    i=0;j=0;
    c=mid_e[0];
    while(c!='#'&& i<MAXN)
	{//k指示是否是运算数
        if((c>='0'&&c<='9')||c=='.'){pos_e[i++]=c;k=0;}
        else{ 
            if(c==')')
			{//遇")"则一直退到"("
                pos_e[i++]=' '; gettop1(optr,ea);
                while(ea!='(')
				{
                    pop1(optr,eb); pos_e[i++]=eb;pos_e[i++]=' ';k=1;
                    gettop1(optr,ea);
                }
                pop1(optr,eb);
            }//else if
            else{
                if(i>1&&k==0)pos_e[i++]=' ';
                gettop1(optr,ea);
                while(isp(ea)>=icp(c))
				{//比较优先级
                    pop1(optr,eb);gettop1(optr,ea);
                    pos_e[i++]=eb;pos_e[i++]=' ';k=1;
                }
                push1(optr,c);pos_e[i++]=' ';
            }
        }
        c=mid_e[++j];
    }
    gettop1(optr,ea);
    while(ea!='#')
	{//退栈到栈底
        pos_e[i++]=' ';pop1(optr,eb);pos_e[i++]=eb; gettop1(optr,ea);
    }
    if(i==MAXN)return(OVERFLOW);
    else pos_e[i++]=' ';pos_e[i]='#';
    return OK;
}


float evaluate(char pos_e[])
{//后缀表达式求值
    int i,j,k,n,flag;
    float m,e,ta,tb,d,t;float *p;
    char c;
    sqstack_num opnd;
    initstack2(opnd);	//opnd栈的初始化
    i=j=n=0;flag=0;
    c=pos_e[0];
    while(c!='#')
    {
        if(c==' ')
        { 
            if(j>=2)	//把字符转化为实数
            { m=0;k=j;
			while(j>0)
			{
				pop2(opnd,e);
				m+=e*(float)pow(10,k-j);j--;
			}
			m=m/(float)pow(10,n);
			push2(opnd,m);
            }
            else j=0;
			n=0;flag=0;	//flag指示小数点的起始，n指示小数点后的位数
        }
        else{
            if((c>='0'&&c<='9')||c=='.')
				{ if(c=='.')flag=1;
				else 
					{ if(flag==1)n++;
					d=(float)(c-'0');push2(opnd,d);j++;
					}
				}
        else 
			{//遇运算符则取数进行运算
				pop2(opnd,ta);pop2(opnd,tb);
				if(c=='*')t=ta*tb;
				if(c=='/'){if(ta==0)return ERROR;else t=tb/ta;}
				if(c=='+')t=ta+tb;
				if(c=='-')t=tb-ta;
				push2(opnd,t);
            }
        } p=opnd.base;while(p<opnd.top)printf("%f",*p++);printf("\n");
		c=pos_e[++i];
    }
	gettop2(opnd,e);
	return e;
};

void main()
{
	int i,j;
	float m;
	char mid_e[MAXN],pos_e[MAXN],c;
	printf("请输入实数求值表达式，只包含加减乘除运算( 以#为结束标志)：\n");
	for(i=0;;i++)
	{ scanf("%c",&mid_e[i]);
	if(i==MAXN){ printf("表达式太长\n"); exit(OVERFLOW);} 
	if(mid_e[i]=='#')break; 
	}
	printf("你输入的表达式是：");
	j=0;
	while(j<=i)printf("%c",mid_e[j++]);
	printf("\n");
	mid_to_pos(mid_e,pos_e);
	c=pos_e[0];i=0;	//打印后缀表达式
	printf("转化成的后缀表达式是：");
	while(c!='#'){printf("%c",pos_e[i++]);c=pos_e[i];}
	printf("%c\n",pos_e[i]);
	printf("运算数栈的变化过程：");
	m=evaluate(pos_e);  
	printf("运算结果是：%f\n",m);  
}