中缀表达式转换后缀表达式

￡神魔★判官ぃ 2022-08-08 05:22 2阅读 0赞

<pre name="code" class="cpp">#include "StdAfx.h"
    #include <stdlib.h>
    
    #define STACK_INIT_SIZE 20 //栈的元素个数
    #define STACKINCREMENT 10	//增长内存的大小
    #define MAXBUFFER 10
    
    
    typedef char 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);
    	printf("请输入中缀表达式,以#作为结束标志");
    	char c,e;
    	scanf("%c",&c);
    	while(c!='#'){
    		while(c>='0' && c<='9'){//数字处理
    			printf("%c",c);
    			scanf("%c",&c);
    			if(c<'0' || c>'9')
    				printf(" ");
    		} 
    		
    		if(')'==c){
    			Pop(&s,&e);
    			while(e!='('){//除了(不打印其他都打印
    				printf("%c",e);
    				Pop(&s,&e);
    			}
    		}else if('+'==c || '-'==c){
    			if(!StackLen(s)){//当栈为空我们直接压入
    				Push(&s,c);
    			}else{
    				do{
    					Pop(&s,&e);
    					if('('==e){
    						Push(&s,e);//压入(
    					}else{
    						printf("%c ",e);
    					}
    				}while(!StackLen(s) && '('!=e);
    				Push(&s,c);//压入操作符
    			}
    		}else if('*'==c || '/'==c || '('==c){
    			Push(&s,c);//压入操作符
    		}else if('#'==c){
    			break;
    		}else{
    			printf("输入格式错误\n");
    			return -1;
    		}
    		scanf("%c",&c);
    	}
    	//最后栈不为空我们都弹栈显示全部数据
    	while(StackLen(s)){
    		Pop(&s,&e);
    		printf("%c ",e);
    	}
    	printf("pause");
    	return 0;
    }

![20150505155346890][]

[20150505155346890]: /images/20220805/a704cf6bb02f4306828501082d63e3a9.png