栈应用：后缀表达式求值

布满荆棘的人生 2022-06-01 07:15 226阅读 0赞

在上一篇博客 **[栈应用：中缀表达式转后缀表达式][Link 1] **中我们知道**如何通过栈将中缀表达式转为后缀表达式**，这次我们继续用栈 来实现后缀表达式求值，结合上一篇博客。

**上一篇博客中是用c语言实现的，由于c语言中不支持模板函数模板类，当我们遇到不同数据类型那么我们用结构体定义栈结构需要同时定义多个，那么对应的栈操作也需要定义多个，为了方便，我们将栈的实现用c++ 来实现，因为c++中有模板呀，可以很方便的构造不同数据类型的栈**。

# 后缀表达式计算规则 #

摘自 **大话数据结构**中的定义。后缀表达式计算规则**：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到是符号，就将处于栈顶2个数字出栈，进行运算，运算结果进栈，一直到最终获取结果**。

# 后缀表达式规则分析 #

比较中缀表达式转后缀表达式的规则，后缀表达式的计算规则简单的多，就是**后缀表达式中数值的入栈出栈问题**。

**遇到数字就进栈，遇到符号，就将栈顶2个元素进行弹栈，然后进行相应的符号计算，将计算结果入栈。**

**当整个表达式计算完毕，此时值栈中的只有1个数值，它就是整个表达式的值。**

# 后缀表达式值计算局部代码 #

/*
    通过栈对后缀表达式进行求值
    */
    double GetResultAfterExp(const char* afterExp)
    {
    	if (NULL == afterExp)
    	{
    		return 0;
    	}
    	// a b 是表达式中的2个操作数
    	double a = 0;
    	double b = 0;
    	int k = 0;// afterExp 下标
    	char ch = 0;//后缀表达式中的字符
    
    	char numBuf[10] = { 0 };//连续的数字不能超过10位，也就是后缀表达式中数字不能超过10位
    	int numIndex = 0;//numBuf 下标
    
    
    	SeqStack<double> stack;
    	InitStack(&stack);
    	while (afterExp[k])
    	{
    		ch = afterExp[k++];
    		//是数值
    		if (ch >= '0'&&ch <= '9')
    		{
    			while (((ch >= '0'&&ch <= '9') || ch == '.') && numIndex < 10)
    			{
    				numBuf[numIndex++] = ch;
    				ch = afterExp[k++];
    			}
    			numBuf[numIndex] = 0;
    			double num = atoi(numBuf);
    			push(&stack, num);
    
    		}
    
    		//是符号或者空格
    		if (ch< '0' || ch > '9')
    		{
    			numIndex = 0;//进入这个if 数字肯定不连续了，下标重置为0
    			// 是空格
    			if (' ' == ch)
    			{
    				continue;
    			}
    			else
    			{
    				double c = 0;
    				switch (ch)
    				{
    				case '+':
    					pop(&stack, &a);
    					pop(&stack, &b);
    					c = b + a;
    					push(&stack,c);
    					break;
    				case '-':
    					pop(&stack, &a);
    					pop(&stack, &b);
    					c = b - a;
    					push(&stack, c);
    					break;
    				case '*':
    					pop(&stack, &a);
    					pop(&stack, &b);
    					c = b * a;
    					push(&stack, c);
    					break;
    				case '/':
    					pop(&stack, &a);
    					pop(&stack, &b);
    					c = b / a;
    					push(&stack, c);
    					break;
    				default:
    					//throw "后缀表达式错误";
    					//printf("后缀表达式错误\n");
    					return 0;
    					break;
    				}
    			}
    		}
    		afterExp++;
    
    	}
    	//计算完毕 将计算结果从栈中弹出
    	if (IsEmptyStack(&stack))
    	{
    		//throw "后缀表达式错误";
    		printf("后缀表达式错误\n");
    		return 0;
    	}
    	pop(&stack, &a);
    		
    	return a;
    }

# 后缀表达式值计算完整代码 #

**代码结构和 [栈应用：中缀表达式转后缀表达式][Link 1] 中的代码结构一致，将中缀表达式转后缀表达式整合进来了，将c代码改成c++代码了**。

#define _CRT_SECURE_NO_WARNINGS
    #include <cstdio>
    #include <cstdlib>
    #include <math.h>
    #include <memory.h>
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define STACK_INIT_SIZE 20	 // 栈初始容量
    #define STACK_INCREMENT 10   //栈满后，每次扩充的容量
    #define EXPRESS_MAX 1024 //后缀表达式 长度不能超过1024
    typedef int Status;
    
    template<class EleType>
    struct SeqStack
    {
    	EleType* top;//栈顶指针
    	EleType* base;//栈底指针
    	int stackSize;//栈容量
    };
    
    //初始化栈
    template<class EleType>
    Status InitStack(SeqStack<EleType>* stack)
    {
    	//开辟空间
    	stack->base = stack->top = (EleType*)malloc(STACK_INIT_SIZE * sizeof(EleType));
    	if (!stack->base)
    	{
    		exit(0);
    	}
    	stack->stackSize = STACK_INIT_SIZE;
    	return OK;
    }
    //压栈
    template<class EleType>
    Status push(SeqStack<EleType>* stack, EleType e)
    {
    	if (stack == NULL)
    	{
    		return ERROR;
    	}
    	//压栈之前检测容量是否足够
    	if (stack->top - stack->base == stack->stackSize)
    	{
    		//超出容量 进行扩容，使用realloc函数，会拷贝原内存内容
    		stack->base = (EleType*)realloc(stack->base, stack->stackSize + STACK_INCREMENT);
    		if (!stack->base)
    		{
    			exit(0);
    		}
    		stack->top = stack->base + stack->stackSize;
    		stack->stackSize += STACK_INCREMENT;
    	}
    	*stack->top = e;
    	stack->top++;
    	return OK;
    }
    //弹栈
    template<class EleType>
    Status pop(SeqStack<EleType>* stack, EleType *e)
    {
    	if (stack == NULL || e == NULL)
    	{
    		return ERROR;
    	}
    	//空栈
    	if (stack->top == stack->base)
    	{
    		return ERROR;
    	}
    	*stack->top--;
    	*e = *stack->top;
    	return OK;
    }
    /*
    获取栈顶元素
    */
    template<class EleType>
    Status GetTop(SeqStack<EleType>* stack, EleType *e) {
    	if (NULL == stack) {
    		return ERROR;
    	}
    	*e = *(stack->top - 1);
    	return OK;
    }
    /*
    判断栈是否为空
    */
    template<class EleType>
    int IsEmptyStack(SeqStack<EleType>* stack) {
    	if (NULL == stack) {
    		return ERROR;
    	}
    	if (stack->top == stack->base) {
    		return TRUE;
    	}
    	return FALSE;
    }
    /*
    销毁栈
    */
    template<class EleType>
    Status DestroyStack(SeqStack<EleType>* stack)
    {
    	if (NULL == stack) {
    		return ERROR;
    	}
    	//销毁栈 是释放栈在内存中占用的空间资源
    	if (!stack->base)
    	{
    		free(stack->base);
    	}
    	stack->top = stack->base = NULL;
    	stack->stackSize = 0;
    	return OK;
    }
    
    char* MidExpToAfterExp(const char* midExp)
    {
    	//后缀表达式
    	char* afterExp = (char*)malloc(sizeof(char)*EXPRESS_MAX);
    	memset(afterExp, 0, EXPRESS_MAX);
    	int j = 0;//afterExp下标
    	int k = 0;//preExp下标
    
    	SeqStack<char> stack;// + - * / ( ）符号栈
    	InitStack(&stack);
    
    	char numBuf[10] = { 0 };//连续的数字不能超过10位，也就是中缀表达式中数字不能超过10位
    	char ch = 0;
    	int numIndex = 0;//numBuf 下标
    	while (midExp[k])
    	{
    		ch = midExp[k++];
    		//忽略中缀表达式中的空格
    		if (ch == ' ')
    		{
    			continue;
    		}
    		//回车代表中缀输入完毕
    		if ('\n' == ch)
    		{
    			break;
    		}
    		//1、若是数字就输出
    		if (ch >= '0' && ch <= '9')
    		{
    			//如果输入连续的数字，不是连续的数字 循环完毕 会走 2、非数字
    			while (((ch >= '0' && ch <= '9') || '.' == ch) && numIndex < 10)
    			{
    				numBuf[numIndex++] = ch;
    				afterExp[j++] = ch;
    				ch = midExp[k++];
    			}
    			numBuf[numIndex] = 0;
    			afterExp[j++] = ' ';
    		}
    		//回车代表中缀输入完毕
    		if ('\n' == ch)
    		{
    			break;
    		}
    		//忽略中缀表达式中的空格
    		else if (' ' == ch)
    		{
    			continue;
    		}
    		//2、非数字
    		else if (ch < '0' || ch > '9')
    		{
    			numIndex = 0;//进入这个if 数字肯定不连续了，下标重置为0
    						 //右括号一定弹栈
    			if (')' == ch)
    			{
    				int flag = 1;//判断中缀表达式中括号是否匹配,如果成对出现
    				while (!IsEmptyStack(&stack))
    				{
    					pop(&stack, &ch);
    					if ('(' == ch)
    					{
    						flag = 0;//走到这里说明是()括号成对出现
    						break;
    					}
    					afterExp[j++] = ch;
    					afterExp[j++] = ' ';
    				}
    				if (flag)
    				{
    					printf("中缀表达式输入错误\n");
    					//exit(0);
    					return	NULL;
    				}
    
    			}
    			// + - 符号是优先级最低的，一定是先依次弹栈再压栈。
    			else if ('+' == ch || '-' == ch)
    			{
    				char top;
    				GetTop(&stack, &top);
    				//栈空或者栈顶为左括号 直接压栈
    				if (IsEmptyStack(&stack) || '(' == top)
    				{
    					push(&stack, ch);
    				}
    				else
    				{
    					char cur = ch;
    					while (!IsEmptyStack(&stack))
    					{
    						pop(&stack, &ch);
    						if ('(' == ch)
    						{
    							//不是因为)右括号而弹栈，多弹的(左括号压回去
    							push(&stack, ch);
    							break;
    						}
    						afterExp[j++] = ch;
    						afterExp[j++] = ' ';
    					}
    
    					push(&stack, cur);
    				}
    			}
    			// * / 符号优先级只比 + -高，栈空或栈顶为(+-符号栈才直接压栈，其他情况先依次弹栈再压栈
    			else if ('*' == ch || '/' == ch)
    			{
    				char top;
    				GetTop(&stack, &top);
    				//栈空或者栈顶为左括号同样直接压栈
    				if (IsEmptyStack(&stack) || '(' == top || '-' == top || '+' == top)
    				{
    					push(&stack, ch);
    				}
    				else if ('*' == top || '/' == top)
    				{
    					char cur = ch;
    					while (!IsEmptyStack(&stack))
    					{
    						pop(&stack, &ch);
    						if ('(' == ch || '-' == ch || '+' == ch)
    						{
    							//不是因为)右括号而弹栈 * / 优先级高于栈顶 + - 就不弹栈了，多弹的压回去
    							push(&stack, ch);
    							break;
    						}
    						afterExp[j++] = ch;
    						afterExp[j++] = ' ';
    					}
    					push(&stack, cur);
    				}
    			}
    			else if ('(' == ch)
    			{
    				push(&stack, ch);
    			}
    			else
    			{
    				printf("中缀表达式输入错误\n");
    				//exit(0);
    				return	NULL;
    			}
    		}
    
    	}
    	//符号栈内容不为空 依次出栈并打印
    	while (!IsEmptyStack(&stack))
    	{
    		pop(&stack, &ch);
    		afterExp[j++] = ch;
    		afterExp[j++] = ' ';
    	}
    
    	return afterExp;
    }
    /*
    通过栈对后缀表达式进行求值
    */
    double GetResultAfterExp(const char* afterExp)
    {
    	if (NULL == afterExp)
    	{
    		return 0;
    	}
    	// a b 是表达式中的2个操作数
    	double a = 0;
    	double b = 0;
    	int k = 0;// afterExp 下标
    	char ch = 0;//后缀表达式中的字符
    
    	char numBuf[10] = { 0 };//连续的数字不能超过10位，也就是后缀表达式中数字不能超过10位
    	int numIndex = 0;//numBuf 下标
    
    
    	SeqStack<double> stack;
    	InitStack(&stack);
    	while (afterExp[k])
    	{
    		ch = afterExp[k++];
    		//是数值
    		if (ch >= '0'&&ch <= '9')
    		{
    			while (((ch >= '0'&&ch <= '9') || ch == '.') && numIndex < 10)
    			{
    				numBuf[numIndex++] = ch;
    				ch = afterExp[k++];
    			}
    			numBuf[numIndex] = 0;
    			double num = atoi(numBuf);
    			push(&stack, num);
    
    		}
    
    		//是符号或者空格
    		if (ch< '0' || ch > '9')
    		{
    			numIndex = 0;//进入这个if 数字肯定不连续了，下标重置为0
    			// 是空格
    			if (' ' == ch)
    			{
    				continue;
    			}
    			else
    			{
    				double c = 0;
    				switch (ch)
    				{
    				case '+':
    					pop(&stack, &a);
    					pop(&stack, &b);
    					c = b + a;
    					push(&stack,c);
    					break;
    				case '-':
    					pop(&stack, &a);
    					pop(&stack, &b);
    					c = b - a;
    					push(&stack, c);
    					break;
    				case '*':
    					pop(&stack, &a);
    					pop(&stack, &b);
    					c = b * a;
    					push(&stack, c);
    					break;
    				case '/':
    					pop(&stack, &a);
    					pop(&stack, &b);
    					c = b / a;
    					push(&stack, c);
    					break;
    				default:
    					//throw "后缀表达式错误";
    					//printf("后缀表达式错误\n");
    					return 0;
    					break;
    				}
    			}
    		}
    		afterExp++;
    
    	}
    	//计算完毕 将计算结果从栈中弹出
    	if (IsEmptyStack(&stack))
    	{
    		//throw "后缀表达式错误";
    		printf("后缀表达式错误\n");
    		return 0;
    	}
    	pop(&stack, &a);
    		
    	return a;
    }
    
    int main(int argc, char *argv[])
    {
    	while (1)
    	{
    		printf("请输入中缀表达式(#表示退出)：");
    
    		//中缀表达式
    		char* midExp = (char*)malloc(sizeof(char)*EXPRESS_MAX);
    		
    		memset(midExp, 0, EXPRESS_MAX);
    		fgets(midExp, 1024, stdin);//midExp 包含换行符
    		if ('#' == midExp[0])
    		{
    			break;
    		}
    		SeqStack<char> charStack;
    		//后缀表达式
    		char* afterExp = MidExpToAfterExp(midExp);
    		printf("对应的后缀表达式：%s\n", afterExp);
    
    		double result = GetResultAfterExp(afterExp);
    		printf("表达式计算结  果：%.2f\n", result);
    
    
    
    	}
    
    	return 0;
    }

# 验证结果 #

![Center][]

[Link 1]: http://blog.csdn.net/qq_29542611/article/details/79134163
[Center]: /images/20220601/52b44ced23f2436f86306c21e2f1177b.png