后缀表达式求解

小鱼儿 2022-04-04 19:08 160阅读 0赞

## 原理 ##

*  规则：

遍历字符串

1. 对于数字：直接进栈  
2. 对于符号：  
    （1）从栈中弹出右操作数  
    （2）从栈中弹出左操作数  
    （3）根据符号进行运算  
    （4）将运算结果压栈

遍历结束：栈中唯一的数字作为计算结果

例子：

输入：831-5*+         相当于求：8+（3-1）*5
    输出：18

--------------------

## 代码 ##

stack.h

#ifndef __STACK_H
    #define __STACK_H
    
    #define MAX_SIZE 1024
    
    
    
    typedef struct STACK
    { 
    	void* Stack_Sqe[MAX_SIZE];
    	int size;				
    }Stack;
    
    
    
    Stack* Init_Stack(void);
    
    void Push_Stack(Stack* stack, void* data);
    void Pop_Stack(Stack* stack);
    
    void* Top_Stack(Stack* stack);
    
    void Clear_Stack(Stack* stack);
    void Free_Stack(Stack* stack);
    
    int Size_Stack(Stack* stack);
    
    
    #endif

stack.c

#include "../include/stack.h"
    #include <stdlib.h>
    
    
    Stack* Init_Stack(void)
    { 
    	Stack* stack = (Stack*)malloc(sizeof(Stack));
    	stack->size =0;		
    				
    	for(int i=0; i<MAX_SIZE; i++)
    	{ 
    		stack->Stack_Sqe[i]=NULL;				
    	}
    	return stack;		
    }
    
    
    void Push_Stack(Stack* stack, void* data)
    { 
    	if(stack == NULL) return;
    	if(data == NULL) return;
    	stack->Stack_Sqe[stack->size++] = data;			
    }
    
    
    
    void Pop_Stack(Stack* stack)
    { 
    	if(stack == NULL) return;
    	if(stack->size==0) return;
    	stack->Stack_Sqe[stack->size-1]=NULL;
    	stack->size--;		
    }
    
    
    void* Top_Stack(Stack* stack)
    { 
    	if(stack == NULL)return NULL;
    	return stack->Stack_Sqe[stack->size-1];			
    }
    
    
    
    void Clear_Stack(Stack* stack)
    { 
    	if(stack == NULL)return;
    	for(int i=0; i<stack->size; i++)
    	{ 
    			stack->Stack_Sqe[i]=NULL;				
    	}		
    }
    
    
    
    
    void Free_Stack(Stack* stack)
    { 
    	if(stack == NULL)
    	    return;
    	free(stack);			
    }
    
    
    
    int Size_Stack(Stack* stack)
    { 
    	return stack->size;		
    }

mian.c

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include "../include/stack.h"
    
    
    
    
    int CalculateSuffix(char* str)
    { 
    
    	Stack* stack = Init_Stack();
    	int tmp[64]={ 0};
    
    	int len = strlen(str);
    	for(int i=0; i<len; i++)
    	{ 
    		if(str[i]>47 && str[i]<58)//数字
    		{ 
    			tmp[i]= (int)(str[i]-48);
    			Push_Stack(stack,&tmp[i]);
    		}
    		else
    		{ 
    			switch(str[i])
    			{ 
    				case '-':
    					{ 
    						int* c1 = Top_Stack(stack);
    						int cc1 = *c1;
    						int right1 = cc1;
    						Pop_Stack(stack);
    
    						int* d1 = Top_Stack(stack);
    						int dd1 = *d1;
    						int left1 = dd1;
    						Pop_Stack(stack);
    
    						int res1 = left1-right1;
    						Push_Stack(stack,&res1);
    						break;
    
    					}
    				case '+':
    					{ 
    						int* c2 = Top_Stack(stack);
    						int cc2 = *c2;
    						int right2 = cc2;
    						Pop_Stack(stack);
    
    						int* d2 = Top_Stack(stack);
    						int dd2 = *d2;
    						int left2 = dd2;
    						Pop_Stack(stack);
    
    						int res2 = left2+right2;
    						Push_Stack(stack,&res2);
    						break;
    					}
    					
    				case '*':
    					{ 
    						int* c3 = Top_Stack(stack);
    						int cc3 = *c3;
    						int right3 = cc3;
    						Pop_Stack(stack);
    
    						int* d3 = Top_Stack(stack);
    						int dd3 = *d3;
    						int left3 = dd3;
    						Pop_Stack(stack);
    
    						int res3 = left3*right3;
    						Push_Stack(stack,&res3);
    						break;
    					}
    
    				case '/':
    					{ 
    						int* c4 = Top_Stack(stack);
    						int cc4 = *c4;
    						int right4 = cc4;
    						Pop_Stack(stack);
    
    						int* d4 = Top_Stack(stack);
    						int dd4 = *d4;
    						int left4 = dd4;
    						Pop_Stack(stack);
    
    						int res4 = left4/right4;
    						Push_Stack(stack,&res4);
    						break;
    
    					}	
    				default:
    					printf("error ");
    					break;
    					
    			}
    		}
    
    	}
    
    
    	int* result = Top_Stack(stack);
    	return *result;
    
    }
    
    int main(void)
    { 
    
    	char str[64]={ 0};
    	int result=0;
    	printf("input:");
    	scanf("%s",str);
    
    	result =CalculateSuffix(str);
        printf("output:");
    	printf("%d\n",result);
    									
    									
    	return 0;
    									
    }

结果：  
![在这里插入图片描述][20181218192039480.png]

[20181218192039480.png]: /images/20220404/4d8a578f315043dfb7d586d9691bcbb9.png