逆波兰算法源码

以你之姓@ 2022-08-08 05:22 189阅读 0赞

#define STACK_INIT_SIZE 20 //栈的元素个数
    #define STACKINCREMENT 10	//增长内存的大小
    #define MAXBUFFER 10
    
    typedef double ElementType;
    typedef struct {
    	ElementType *base;//栈的基地址
    	ElementType *top;//栈顶
    	int stackSize;//栈的大小
    }sqStack;
    
    void InitStack(sqStack*s){
    	s->base=(ElementType*)malloc(STACK_INIT_SIZE * sizeof(ElementType));
    	if(!s->base)
    		exit(0);
    	s->top=s->base;//设栈顶和栈的基地址一样
    	s->stackSize=STACK_INIT_SIZE;//栈的容量大小
    }
    
    void Push(sqStack* s,ElementType e){
    	//压栈
    	if(s->top - s->base >=s->stackSize){
    		//计算栈大小是否满了
    		s->base=(ElementType*) realloc(s->base,(s->stackSize+STACKINCREMENT)* sizeof(ElementType));
    		s->top=s->base+s->stackSize;//将栈顶移到末尾
    		s->stackSize=s->stackSize+STACKINCREMENT;
    	}
    	*(s->top)=e;//存放数据
    	s->top++;
    }
    
    void Pop(sqStack* s,ElementType*e){
    	if(s->top==s->base)
    		return ;
    	*e=*--(s->top);//弹出栈,并且栈顶递减
    }
    
    int StackLen(sqStack s){
    	return (s.top-s.base);//返回栈顶的个数
    }
    
    int Main(){
    	sqStack s;
    	InitStack(&s);
    	char str[MAXBUFFER];//字符串的缓冲区
    	int i=0;
    	char c;
    	double d,e;
    	printf("请按逆波兰表达式输入待计算数据,数据与运算符用空格隔开!以#作为结束标识!");
    	while(c!='#'){
    		scanf("%c",&c);//让用户输入字符
    		while(isdigit(c) || c=='.'){//过滤数字
    			str[i++]=c;
    			str[i]='\0';
    			if(i>=10){
    				printf("出错:输入的单个数据过大!\n");
    				return -1;
    			}
    			scanf("%c",&c);
    			if(c==' '){
    				//表示该数字结束了
    				d=atof(str);
    				Push(&s,d);
    				i=0;//缓冲区索引重新初始化
    			}
    		}
    		switch(c){
    			case '+':
    				Pop(&s,&e);
    				Pop(&s,&d);
    				Push(&s,d+e);
    				break;
    			case '-':
    				Pop(&s,&e);
    				Pop(&s,&d);
    				Push(&s,d-e);
    				break;
    			case '*':
    				Pop(&s,&e);
    				Pop(&s,&d);
    				Push(&s,d*e);
    				break;
    			case '/':
    				if(e==0){
    					printf("被除数不能为0!");
    					return;
    				}
    				Pop(&s,&e);
    				Pop(&s,&d);
    				Push(&s,d/e);
    				break;
    		}
    	}
    	//打印结果
    	Pop(&s,&d);
    	printf("结果:%f",d);
    }

表达式:

5-(6+7)\*8+9/4

逆波兰输入:

5 6 7 + 8 \* - 9 4 / +

结果:

\-96.75