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

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

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

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

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

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

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

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

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

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

//用链表实现的栈
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;
}

测试结果：

三、后缀表达式的计算

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

//用链表实现的栈
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;
}

实现结果;

结果与预期相同！
这就是栈在表达式中的应用，当然，还可以用栈实现中缀转前缀，用前缀表达式计算，这里就不一一实现了！