76-实现中缀转后缀(对栈的应用)

雨点打透心脏的1/2处 2022-12-27 09:06 82阅读 0赞

首先对栈的编写

#define INITSZIE 10
    
    typedef int ElemType;
    
    typedef struct stack
    {
        
    	ElemType *data;//指向存储空间的首地址 栈底指针
    	int       top;//栈顶指针
    	int      size;//栈存储空间的大小，为了扩容准备 
    }Stack;

本程序所需要的头文件

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

以下是对编写中缀转后缀函数时需要的其他功能函数的书写

void InitStack(Stack *st)//初始化栈 
    {
        
    	if(st==NULL) exit(0);
    	st->data=(ElemType *)malloc(sizeof(ElemType)*INITSZIE);
    	if(st->data==NULL) exit(0);
    	st->top=0;//有两种设置 0 -1
    	st->size=INITSZIE; 
    }
    static bool AppendSpace(Stack *st)//申请新空间 扩容 
    {
        
    	ElemType *new_space=(ElemType *)malloc(sizeof(ElemType)*st->size*2);
    	if(new_space==NULL) return false;
    	for(int i=0;i<st->top;++i)
    	{
        
    		new_space[i]=st->data[i]; 
    	}
    	free(st->data);
    	st->data=new_space;
    	st->size*=2;
    	return true;
    }
    bool IsFull(Stack *st)//判满 
    {
        
    	return st->top==st->size;	 
    }
    bool Push(Stack *st,ElemType val)//增加数据 
    {
        
    	if(st==NULL) exit(0);
    	if(IsFull(st))
    	{
        
    		if(!AppendSpace(st))
    		{
        
    			return false;
    		}
    	}
    	st->data[st->top++]=val;
    	return true;
    }
    bool IsEmpty(Stack *st)//判空 
    {
         
    	return st->top==0; 
    }
    bool Pop(Stack *st)//取出数据 
    {
        
    	if(st==NULL) exit(0);
        if(IsEmpty(st))
        {
        
        	return false;
    	}
    	st->top--;
    	return true;
    }
    //没有通过top返回值返回栈顶元素，而是通过一个参数将栈顶元素返回 
    bool Top(Stack *st,ElemType *val)
    {
        
        if(st==NULL) exit(0);
        if(IsEmpty(st)) return false;
        *val=st->data[st->top-1];
        return true;
    }
    
    
    void DestroyStack(Stack *st)//销毁 
    {
        
    	if(st==NULL) exit(0);
    	free(st->data);
    	st->data=NULL;
    	st->size=st->top=0;
    }

## 然后是对中缀转后缀函数的书写和注释 ##

void InfixToSuffix(const char *str)
    {
        
    	if(str==NULL) exit(0);
    	Stack st;
    	InitStack(&st);
    	int tmp=0;
    	while(*str!='\0')//从左到右依次遍历中缀表达式 
    	{
        
    		if(*str==' ')//遇到空格跳过去 
    		{
        
    			str++;
    			continue;//提前结束此次循环进入下一次 
    		}
    		if(isdigit(*str))
    		//如果是数字，则直接输出 
    		{
        
    			printf("%c",*str);
    			if(!isdigit(*(str+1)))//处理两位及以上的数字 
    			{
        
    				printf(" ");
    			}
    		}
    		else if(*str=='(')
    		//如果是左括号，则直接入栈 
    		{
        
    			Push(&st,*str);
    		}
    		else if(*str==')')
    //如果是右括号，出栈并输出，直到遇到第一个左括号 
    		{
        
    			while(1)
    			{
        
    				Top(&st,&tmp);
    				Pop(&st);
    				if(tmp=='(') break;
    				printf("%c ",tmp);
    			}
    		}
    		else if(*str=='+'||*str=='-')
    //如果是+或者-，直接出栈并输出，直到栈空或者左括号(不出),然后将当前符号入栈 
    		{
        
    			while(!IsEmpty(&st))
    			{
        
    				Top(&st,&tmp);
    				if(tmp=='(') break;
    				printf("%c ",tmp);
    				Pop(&st);
    		    }
    		    Push(&st); 
    		}
    		else if(*str=='*'||*str=='/')
    //如果是*或者/，直接出栈，直到栈空或者左括号(不出),或者+，-(不出),然后将当前符号入栈 
    		{
        
    			while(!IsEmpty(&st))
    			{
        
    				Top(&st,&tmp);
    				if(tmp=='('||tmp=='+'||tmp=='-') break;
    				printf("%c ",tmp);
    				Pop(&st);
    			}
    			Push(&st,*str);
    		}
    		else//若以上的条件都不符合，则打印出错误 
    		{
        
    			printf("Infix is error\n");
    			return;
    		}
    	    str++;
        }
        while(!IsEmpty(&st))
    //中缀表达式遍历结束，将栈中的所有元素全部弹出并输出 
        {
        
        	Top(&st,&tmp);
        	printf("%c ",tmp);
        	Pop(&st);
    	}
    	printf("\n");
    }

**最后书写主函数，编译运行程序。**

int main()
    {
        
    	const char *str="9 + (3-1) * 3+ 10 / 2";
    	InfixToSuffix(str);
    	return 0;
    }

**运行结果如图所示**  
![在这里插入图片描述][20201209230623344.png_pic_center]

[20201209230623344.png_pic_center]: /images/20221120/920bfa1ed71f4c88af3e6003ae715dec.png