逆波兰运算符和转换中缀表达式 (C语言编写逆波兰计算器) ------- 算法笔记011

谁践踏了优雅 2023-07-04 06:11 9阅读 0赞

## 逆波兰表达式 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]

### 编程思路 ###

> 我们可以输入一段逆波兰表达式，然后程序循环读取单个字符，判断字符是数字范围的还是计算符。当读到的是数字范围时我们将其入栈，当读到的是计算字符我们将前面的两个数Pop出来进行对应的计算，最后再将其入栈。

#### Demo1实现代码 ####

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_NUM_STACK 10 
    #define error 0
    #define ok 1
    #define MAX_SIZE 10
    
    typedef double ElemType;
    typedef int Status;
    
    typedef struct stack{ 
    	
    	ElemType *top;
    	ElemType *base;
    	int stackSize;
    	
    }Stack,*stackList;
     
     
    Status Pop(Stack *stack,ElemType *e){ 
    	
    	if(stack->top==stack->base){ 
    		printf("栈空空如也!\n");
    		return error;
    	}
    	
    	*e=*(--stack->top); 
    	stack->stackSize++;
    	return ok;
    } 
    
    Status Push(Stack *stack,ElemType e){ 
    	if(stack->stackSize<=0)
    		stack->top=(ElemType *)malloc(sizeof(ElemType)*MAX_NUM_STACK);
    	
    	if(!stack->top)
    		return error;
    	
    	*stack->top=e;
    	stack->top++;		
    	stack->stackSize--;	
    	return ok;
    }
     
    Status InitStack(Stack *stack){ 
    	
    	stack->base=(ElemType *)malloc(sizeof(ElemType)*MAX_NUM_STACK);
    	if(!stack->base)
    		return error;
    	
    	stack->top=stack->base;
    	stack->stackSize=MAX_NUM_STACK;
    	return ok;
    	
    } 
     
    void PrintTitle(char*title,char*name,char*date){ 
    	printf("---------------------%s----------------------------------\n",title);
    	printf("\n");
    	printf("作者:%s\n",name);
    	printf("日期:%s\n\n",date);
    	printf("----------------------------------------------------------\n");
    	
    }
    
    int main(int argc, char *argv[]) { 
    	
    	
    	PrintTitle("逆波兰计算器","Changlon","2019-12/19");  //程序信息
    	
    	Stack stack;
    	int s=InitStack(&stack); //初始化栈内存
    	if(!s){ 
    	     printf("内存出错！");
    	     return 0;		
    	}
    	char in; //每次接受一个字符
    	char buffer[MAX_SIZE]; //定义字符串缓冲区
    	int i=0;
    	double c1,c2;
    	double e; //最终要输出的计算值
    	printf("请输入一段逆波兰表达式 (以#结束):");
    	scanf("%c",&in);
    	while(in!='#'){ 		
    		switch(in){ 
    			//当检测到计算符时，取出前面两个数进行计算，并入栈
    			case '+':
    				Pop(&stack,&c1);
    				Pop(&stack,&c2);
    				Push(&stack,c1+c2);
    				break;
    			case '-':
    				Pop(&stack,&c1);
    				Pop(&stack,&c2);
    				Push(&stack,c2-c1); 
    				break;
    			case '*':
    				Pop(&stack,&c1);
    				Pop(&stack,&c2);
    				Push(&stack,c1*c2);
    				break;
    			case '/':
    				Pop(&stack,&c1);
    				Pop(&stack,&c2);
    				Push(&stack,c2/c1);
    				break;			
    			case ' ':
    				//当检测到空字符的时候，并且缓冲区里已经有数字了
    				if(i!=0){ 
    					buffer[i]='\0';
    					e=atof(buffer);//将缓冲区里的数字字符串转变为数字类型
    					Push(&stack,e);//入栈
    					i=0;//重新开始写数字字符
    				}
    				break;
    			//输入的是数字,就先放入到缓冲区
    			default:   
    				buffer[i]=in;
    				i++;
    				break;		
    		}
    		
    	
    		scanf("%c",&in);
    	}
    	getchar(); //消除回车
    	Pop(&stack,&e);
    	printf("%.2f\n",e);
    	system("pause"); 
    
    	return 0;
    }

###### 运行结果 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70 1]

> 可以看到我们的这个小DEMO已经具备了处理逆波兰表达式的能力了，但是以人的思维每次计算的时候不可能每次都要逆波兰这种运算，不符合人的思维。那么有没有什么方法可以使得计算机能够识别我们的计算表达式，如: 1+1=2呢？答案肯定是可以的，我们只要将1+1=2这种形式转变为1 1 +\# (\#号作为结束标志)，剩下的就是将这段字符串交给计算机，如我们上面的这个demo处理就行了。

## 中缀表达式转为后缀表达式的算法思路 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70 2]

> 我们对图作出一些说明，比如我们就要将 （1+2)*(3+4*5) 转换成后缀表达式，运用图上的算法步骤就是  
> 第一步：读取 字符 ‘(’ ,判断其不是数字，入栈。栈内存状态：(…  
> 第二步: 读取 字符 ‘1’ ,是数字就 输出，或者输入到一个缓冲区。 缓冲区状态: 1…  
> 第三步: 读到 ‘+’ ,入栈。栈内存状态: ( +…  
> 第四步: 读到 ‘2’,输出到缓冲区，缓冲区状态: 1 2…  
> 第五步: 取到 ‘)’,此时读到’)‘说明括号里的一个表达式就已经结束了，我们依次出栈直到出栈到’('位置  
> 那么栈内存的状态现在就为空:…, 这时缓冲区的状态就为: 1 2 +…这时(1+2)这个就被我们转成了后缀表达式  
> 第六步: 如此循环往复最终我们缓冲区里的内存存的就是这些：1 2 + 3 4 5 \* + \*  
> 我们最后来验证一下是否正确：  
> 按照计算机的读取顺序  
> 读到第一个+ 1 2相加成 3  
> 读到第一个\* 4 5相乘为 20  
> 然后第二个+ 3 20相加为23  
> 最后一个\* 3 23相乘为69，与上面的表达式的计算结果相同，所以后缀表达式转换正确！  
> 我们可以转换中缀表达式了，那么可以直接输入中缀表达式让计算机计算结果，逆波兰计算器的实现思路也就不明则知了

### 最终实现逆波兰运算器的代码 ###

//修改demo1即可
    #include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>
    
    #define MAX_NUM_STACK 10 
    #define error 0
    #define ok 1
    #define MAX_SIZE 10
    #define SIZE 15 
    
    typedef double ElemType;
    typedef char ElemType2;
    typedef int Status;
    
    typedef struct stack{ 
    	
    	ElemType *top;
    	ElemType *base;
    	int stackSize;
    	
    }Stack,*stackList;
     
    typedef struct stack2{ 
    	ElemType2 *top;
    	ElemType2 *base;
    	int stackSize;
    }Stack2,*stackList2;
     
    Status Pop(Stack *stack,ElemType *e){ 
    	
    	if(stack->top==stack->base){ 
    		printf("栈空空如也!\n");
    		return error;
    	}
    	
    	*e=*(--stack->top); 
    	stack->stackSize++;
    	return ok;
    } 
    
    Status Pop2(Stack2 *stack,ElemType2 *e){ 
    	
    	if(stack->top==stack->base){ 
    		return error;
    	}
    	
    	*e=*(--stack->top); 
    	stack->stackSize++;
    	return ok;
    } 
    
    Status Push(Stack *stack,ElemType e){ 
    	if(stack->stackSize<=0)
    		stack->top=(ElemType *)malloc(sizeof(ElemType)*MAX_NUM_STACK);
    	
    	if(!stack->top)
    		return error;
    	
    	*stack->top=e;
    	stack->top++;		
    	stack->stackSize--;	
    	return ok;
    }
    
    Status Push2(Stack2 *stack,ElemType2 e){ 
    	if(stack->stackSize<=0)
    		stack->top=(ElemType2 *)malloc(sizeof(ElemType2)*MAX_NUM_STACK);
    	
    	if(!stack->top)
    		return error;
    	
    	*stack->top=e;
    	stack->top++;		
    	stack->stackSize--;	
    	return ok;
    }
     
    Status InitStack(Stack *stack){ 
    	
    	stack->base=(ElemType *)malloc(sizeof(ElemType)*MAX_NUM_STACK);
    	if(!stack->base)
    		return error;
    	
    	stack->top=stack->base;
    	stack->stackSize=MAX_NUM_STACK;
    	return ok;
    	
    } 
     
    Status InitStack2(Stack2 *stack){ 
    	
    	stack->base=(ElemType2 *)malloc(sizeof(ElemType2)*MAX_NUM_STACK);
    	if(!stack->base)
    		return error;
    	
    	stack->top=stack->base;
    	stack->stackSize=MAX_NUM_STACK;
    	return ok;
    	
    }  
    
    int compile(char stack,char elem){ 
    	
    	// + - 
    	//* / 
    	//elem ==satck elem优先级小于stack 都返回1
    	//反之都返回 0 
    	
    	
    	if(stack==elem)
    		return 1;
    	
    	if(stack=='*'||stack=='/'&& elem=='/'||elem=='*')
    		return 0;
    	
    	
    	if(elem=='+'||elem=='-'){ 
    		if(stack=='*'||stack=='/'){ 
    			return 1;
    		}
    	}	
    	
    	if(elem=='*'||elem=='/'){ 
    		if(stack=='+'||stack=='-'){ 
    			return 0;
    		}
    	}
    		
    }
    //中缀表达式转后缀表达式
    void Transform(Stack2 *stack,char *src,char *des){ 
    	int index=0;
    	int count=0;
    	ElemType2 e;
    	while(src[index]!='#'){ 
    		if(isdigit(src[index])){ 
    			//printf(" %c ",src[index]);
    			des[count++]=src[index];
    			des[count]=' ';
    			count++;
    			
    		}else{ 
    			if(src[index]=='('||src[index]==')'){ 
    				Push2(stack,src[index]);
    			}else{ 
    				if(Pop2(stack,&e)){ 
    					if(e=='('){ 
    						Push2(stack,e);
    						Push2(stack,src[index]);
    					}else if(e==')'){ 
    						
    						while(1){ 
    							
    							Pop2(stack,&e);
    							
    							if(e=='('){ 
    								break;
    							}else{ 
    								//printf(" %c ",e);
    								des[count++]=e;
    								des[count]=' ';
    								count++;
    							}
    							
    						}
    						
    						Push2(stack,src[index]);
    						
    						
    					}else{ 
    						
    						if(compile(e,src[index])){ 
    							
    							//printf(" %c ",e);
    							des[count++]=e;
    							des[count]=' ';
    							count++;
    							while(Pop2(stack,&e)){ 
    								if(e=='('){ 
    									Push2(stack,e);
    									Push2(stack,src[index]);
    									break;
    								}
    							}
    							Push2(stack,src[index]);
    							
    						}else{ 
    							Push2(stack,e);
    							Push2(stack,src[index]);
    						}
    						
    					}
    						
    				}else{ 
    					Push2(stack,src[index]);
    				}
    			}
    		}
    		index++;
    	}
    
    	while(Pop2(stack,&e)){ 
    		if(e!='('&&e!=')'){ 
    		// printf(" %c ",e);
    		des[count++]=e;	
    		des[count]=' ';	
    		count++;
    		}
    		
    	}
    	des[count]='#';
    	des[++count]='\0';
    	
    }
    
    void PrintTitle(char*title,char*name,char*date){ 
    	printf("---------------------%s----------------------------------\n",title);
    	printf("\n");
    	printf("作者:%s\n",name);
    	printf("日期:%s\n\n",date);
    	printf("----------------------------------------------------------\n");
    	
    }
    
    int main(int argc, char *argv[]) { 
    	
    	
    	PrintTitle("逆波兰计算器(终极版)","Changlon","2019-12/20");
    	
    	Stack stack;
    	InitStack(&stack);
    	char in;
    	char buffer[MAX_SIZE]; 
    	int i=0;
    	double c1,c2;
    	double e;
    	
    	printf("输入表达式 (以#结束):");
    	char *buffer2=(ElemType2 *)malloc(sizeof(ElemType2)*SIZE);
    	char *buffer3=(ElemType2 *)malloc(sizeof(ElemType2)*SIZE);
    	scanf("%s",buffer2);
    	Stack2 stack2;
    	InitStack2(&stack2);
    	Transform(&stack2,buffer2,buffer3);
    	int index=0;
    	
    	while(buffer3[index]!='#'){ 	
    		switch(buffer3[index]){ 
    			case '+':
    				Pop(&stack,&c1);
    				Pop(&stack,&c2);
    				//printf("%.1f\n",c1+c2);
    				Push(&stack,c1+c2);
    				break;
    			case '-':
    				Pop(&stack,&c1);
    				Pop(&stack,&c2);
    				Push(&stack,c2-c1); 
    				break;
    			case '*':
    				Pop(&stack,&c1);
    				Pop(&stack,&c2);
    				Push(&stack,c1*c2);
    				break;
    			case '/':
    				Pop(&stack,&c1);
    				Pop(&stack,&c2);
    				Push(&stack,c2/c1);
    				break;			
    			case ' ':
    				if(i!=0){ 
    					buffer[i]='\0';
    					e=atof(buffer);
    					Push(&stack,e);
    					//printf("%.1f\n",e);
    					i=0;
    				}
    				break;	
    			default:
    				buffer[i]=buffer3[index];
    				i++;
    				break;		
    		}
    		
    		
    		index++;
    	}
    	getchar();
    	Pop(&stack,&e);
    	printf("\n计算结果: %.2f\n\n",e);
    	system("pause"); 
    
    	return 0;
    }

###### 最终运行结果 ######

![在这里插入图片描述][20200208193435653.PNG]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200208183631996.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200208185717281.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020020819031518.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70
[20200208193435653.PNG]: https://img-blog.csdnimg.cn/20200208193435653.PNG