C语言数据结构之栈在表达式值的应用

ゝ一世哀愁。 2022-12-04 05:24 75阅读 0赞

## C语言数据结构之栈在表达式中的应用 ##

tips：前些天学习了数据结构，今天来总结一下数据结构知识栈的应用。

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

##### 一、前缀表达式，中缀表达式，后缀表达式的介绍 #####

*  前缀表达式（波兰表达式）：运算符在两个操作数之前的表达式；
 *  中缀表达式：运算符在两个操作数中间的表达式；
 *  后缀表达式（逆波兰表达式）：运算符在两个操作数之后的表达式；

可以了解到表达式的区别在于运算符的位置不同。从这里可以看出，中缀表达式就是我们正常书写的表达式。

**下面来看一个例子，加深一下对这三种表达式的理解与转换过程。**

<table> 
 <thead> 
  <tr> 
   <th>中缀表达式</th> 
   <th>后缀表达式</th> 
   <th>前缀表达式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>a+b</td> 
   <td>ab+</td> 
   <td>+ab</td> 
  </tr> 
  <tr> 
   <td>a+b-c</td> 
   <td>ab+c-</td> 
   <td>-+abc</td> 
  </tr> 
  <tr> 
   <td>a+b-c*d</td> 
   <td>ab+cd*-</td> 
   <td>-+ab*cd</td> 
  </tr> 
 </tbody> 
</table>

**注意：同一个中缀表达式有可能转换成不同的前缀表达式和后缀表达式（即前缀和后缀表达式表示不唯一）。**

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

下面来看一下中缀表达式与后缀表达式的转换

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

##### 二、中缀表达式转后缀表达式 #####

首先定义栈，实现栈的各种操作，以及各种辅助函数，如下;

//用链表实现的栈
    typedef struct node
    {
        
    	char c;//元素
    	struct node *pNext;
    }Node,*pNode;
    
    //定义栈
    typedef struct
    {
        
    	pNode phead;//链表的头指针
    	int size;//栈的大小
    }Stack,*pStack;
    
    //栈的初始化
    void InitStack(pStack s);
    
    //入栈
    void push(pStack s, char c);
    
    //出栈,出栈的元素用elem保存
    void pop(pStack s, char *elem);
    
    //判断栈是否为空
    int StackEmpty(pStack s);
    
    //打印栈元素
    void print_stack(pStack s);
    
    //获取运算符优先级
    int getPriority(char c);

//获取运算符优先级
    int getPriority(char c)
    {
        
    	if (c == '*' || c == '/')
    		return 2;
    	if (c == '+' || c == '-')
    		return 1;
    }

**1、中缀表达式转后缀表达式的方法**

*  首先确定中缀表达式中各个运算符的顺序；
 *  选择下一个运算符，按照\[**左操作数 右操作数 运算符**\]的方式组合成一个新的操作数；
 *  直到所有的运算符都被处理完成；

我们在上面提到过，**中缀表达式转后缀表达式的结果不唯一**，但是我们计算机是肯定不能处理不确定的值的，所以在计算机中就新增了一条限制，让中缀表达式可以唯一转成后缀表达式：

**左优先原则**：左边的运算符能够先运算就先运算；

根据这一个例子来体会一下左优先原则：

中缀表达式：
     3 2  1  5 4 
    A+B*(C-D)-E/F
    
    根据左优先原则可以确定如上运算符顺序，因此我们可以得到唯一的后缀表达式：
    ABCD-*+EF/-

**2 、中缀表达式转后缀表达式机算实现（借助栈）**

**注意：入栈的总是运算符，不是操作数！**

*  初始化一个栈，用于保存暂时还不能确定顺序的运算符；
 *  从左到右处理各个元素，直到末尾：  
    \- 遇到操作数，直接加入后缀表达式；  
    \- 遇到界限符，例如"("，则直接把"(“入栈；遇到”)"，则依次弹出栈内运算符，并将其加入后缀表达式，知道弹出"(“为止。注意：”()“是不加入后缀表达式的；  
    \- 遇到运算符，依次弹出栈中**优先级高于或等于**当前运算符的所有运算符，并将其加入后缀表达式。若碰到”("或栈空则停止。**之后再把当前运算符入栈**。
 *  按上述方法处理完所有字符后，将栈中剩余的运算符依次弹出，并加入后缀表达式；

具体实现：

//中缀表达式转后缀表达式
    int main()
    {
        
    	Stack stack;
    	pStack s = &stack;
    
    	memset(s, 0, sizeof(Stack));
    
    	char arr_in[N];//输入表达式数组
    	char arr_out[N];//输出表达式数组
    	int i;
    	int j = 0;
    	char c;//入栈的元素
    	char elem=' ';//用来保存出栈的元素
    
    	printf("请输入表达式：");
    	gets(arr_in);
    	//处理中缀表达式，转成后缀表达式
    	for (i = 0; i < strlen(arr_in); i++)
    	{
        
    		if (arr_in[i] >= 'A'&&arr_in[i] <= 'Z' || arr_in[i] >= 'a'&&arr_in[i] <= 'z') 
    		{
        
    			//遇到操作数直接加入后缀表达式
    			arr_out[j] = arr_in[i];
    			j++;
    		}
    		else if (arr_in[i] == '(')
    		{
        
    			//遇到界限符'('，将界限符入栈
    			push(s, arr_in[i]);
    		}
    		else if (arr_in[i] == ')')
    		{
        
    			while (StackEmpty(s) != 1 && s->phead->c != '(') 
    			{
        
    				//遇到界限符')'，依次弹出栈内运算符，并加入后缀表达式，直到弹出'('为止
    				pop(s, &elem);
    				if (elem != '(')
    				{
        
    					arr_out[j] = elem;
    					j++;
    				}		
    			}
    			//将'('出栈
    			pop(s, &elem);
    		}
    		else
    		{
        
    			//遇到运算符,依次弹出栈中优先级高于或等于当前运算符的所有运算符，并将其加入后缀表达式
    			while (StackEmpty(s) != 1 && elem != '('&&getPriority(arr_in[i]) <= getPriority(s->phead->c)) 
    			{
        
    				pop(s, &elem);
    				if (elem != '(')
    				{
        				
    					arr_out[j] = elem;
    					j++;
    				}	
    			}
    			//将当前运算符入栈
    			push(s, arr_in[i]);
    		}
    	}
    	//处理完所有字符出栈栈中所有元素
    	while (StackEmpty(s) != 1)
    	{
        
    		pop(s, &elem);
    		arr_out[j] = elem;
    		j++;
    	}
    
    	arr_out[j] = '\0';//加入结束符
    	printf("----------------------------\n");
    	puts(arr_out);
    	printf("%c", arr_out[j]);
    	
    	return 0;
    }

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]

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

##### 三、后缀表达式的计算 #####

先定义好栈，实现栈的功能，如下：

//用链表实现的栈
    typedef struct node
    {
        
    	int val;//元素
    	char c;//运算符 ps:这里val和c不同时有效
    	struct node *pNext;
    }Node, *pNode;
    
    //定义栈
    typedef struct
    {
        
    	pNode phead;//链表的头指针
    	int size;//栈的大小
    }Stack, *pStack;
    
    //用来当结构体数组
    typedef struct
    {
        
    	int val;
    	char c;
    }Arr,*pArr;
    
    //入栈
    void push(pStack s, int val, char c);
    
    //出栈,出栈的元素用elem保存
    void pop(pStack s);
    
    //判断栈是否为空
    int StackEmpty(pStack s);

**1、后缀表达式转中缀表达式的方法**

从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合并为一个操作数；

例如下面后缀表达式
    20 8 1 6 + - /
         -----
       ---------
    ---------------
    对应的中缀表达式如下：
    20/(8-(1+6))
    记录下这里结果是20，方便后面的机算检验！

**2、后缀表达式的计算，机算实现（借助栈）**

**注意：入栈的是操作数，不是运算符！**

*  从左往右依次扫描下一个元素，直到所有元素被处理完成；
 *  若扫描到操作数，则压入栈，继续从左往右扫描下一个元素；
 *  若扫描到运算符，则弹出栈顶两个元素（**先出栈的是右操作数**），执行相应运算，**运算结果入栈**，继续从左往右扫描下一个元素；

具体实现：

//后缀表达式20 8 1 6 + - /的计算
    int main()
    {
        
    	Stack stack;
    	pStack s = &stack;
    
    	memset(s, 0, sizeof(Stack));
    
    	int i,result;
    
    	Arr arr[] = {
         20,' ',8,' ',1,' ',6,' ',0,'+',0,'-',0,'/' };//' '和0表示无效数据
    	for (i = 0; i < 7; i++)
    	{
        
    		//扫描到运算符,先出栈的是右操作数
    		if (arr[i].c == '+')
    		{
        
    			int num1 = s->phead->val;//右操作数
    			pop(s);
    			int num2 = s->phead->val;//左操作数
    			pop(s);
    			//将两个栈顶元素运算，并压入栈
    			push(s, num2 + num1, ' ');
    		}
    		else if (arr[i].c == '-')
    		{
        
    			int num1 = s->phead->val;
    			pop(s);
    			int num2 = s->phead->val;
    			pop(s);
    			//将两个栈顶元素运算，并压入栈
    			push(s, num2 - num1, ' ');
    		}
    		else if (arr[i].c == '*')
    		{
        
    			int num1 = s->phead->val;
    			pop(s);
    			int num2 = s->phead->val;
    			pop(s);
    			//将两个栈顶元素运算，并压入栈
    			push(s, num2 * num1, ' ');
    		}
    		else if (arr[i].c == '/') 
    		{
        
    			int num1 = s->phead->val;
    			pop(s);
    			int num2 = s->phead->val;
    			pop(s);
    			//将两个栈顶元素运算，并压入栈
    			push(s, num2 / num1, ' ');
    		}
    		else
    		{
        
    			//扫描到操作数,入栈
    			push(s,arr[i].val,arr[i].c);
    		}
    
    	}
    	result = s->phead->val;
    	printf("最终结果：%d\n", result);
    
    	return 0;
    }

实现结果;  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center 1]  
结果与预期相同！  
这就是栈在表达式中的应用，当然，还可以用栈实现中缀转前缀，用前缀表达式计算，这里就不一一实现了！

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

tips：忙于采集的蜜蜂，无暇在人前高谈阔论。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/c145df17fe2242b888449e3bd5e4cd2c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/db9fc6e2560c437cb45887df82a0b35a.png