数据结构C语言—算术表达式求值[栈|中缀表达式法](采用双顺序栈实现)【2021-12-31】

【TDTX】

【C99】

【编译与运行环境】64位Windows操作系统,TDM-gcc 4.9.2 64bit编译。

【输入样例】36.8+69-14.5*(25.7-(45.4/2))-3.9#

【注2】采用
中缀表达式法,符合人的直觉。

【注2】采用
float atof(const char* str);函数将数字字符串转为对应的float型的值,再压入OPND栈中。即
实现了多位整数和浮点数表达式的计算

【问题描述】算术表达式求值问题。

【思路】

1.表达式求值问题中核心问题是实现算符的优先级,使用两个顺序栈分别作为操作数栈和运算符栈的运行工作栈,分别名为: OPND、OPTR。

2.两工作栈的栈底设定为数组 0 位置,栈顶设定为栈顶元素的下一个顺序位置。

【算法思想】

1.首先初始化两个工作栈,其中 OPTR 栈的栈底元素是#,即初始化后立即将#入栈到 OPTR 栈。

2.
依次读入表达式中的字符,是数字字符,将其转化为对应float,当读入到算符字符时先将此float入栈OPND

3. 若是运算符将 OPTR 栈顶的运算符与当前读入的运算符比较优先级后再执行相应的操作。其中栈顶元素优先级小于读入运算符,将该运算符入栈。

4. 若栈顶元素优先级大于读入运算符,将 OPTR 栈顶元素出栈保存在 theta 中,再让 OPND 出栈两次保存在 a 和 b 中,调用 Operate 函数执行算术运算,结果压入 OPND 中。

一、SbqzDouble.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define InitSize 100
#define StepSize 10
#define id_opnd 1
#define id_optr 2
char OP[7] = {'+','-','*','/','(',')','#'};
char tnumber[100];//保存表达式中的数字字符串,用atof函数转为float压入OPND
typedef struct SqStack_OPND
{
	double* base;
	double* top;
	int stacksize;
	int id;
}SqStack_OPND;
typedef struct SqStack_OPTR
{
	char* base;
	char* top;
	int stacksize;
	int id;
}SqStack_OPTR;

int InOP(char* OP,char c)
{
	for(int i = 0;i < 7;i++)
	{
		if(c == OP[i])
		{
			return 1;	
		}	
	}
	return 0;	
} 
int initStack_OPND(SqStack_OPND* S)
{
	S->base = (double*)malloc(sizeof(double)*InitSize);
	if(S->base == NULL)
	{
		S->base = NULL;
		S->top = NULL;
		S->stacksize = -1;
		return 0;
	}
	S->top = S->base;
	S->stacksize = InitSize;
	S->id = id_opnd;
	return 1;
}
int initStack_OPTR(SqStack_OPTR* S)
{
	S->base = (char*)malloc(sizeof(char)*InitSize);
	if(S->base == NULL)
	{
		S->base = NULL;
		S->top = NULL;
		S->stacksize = -1;
		return 0;
	}
	S->top = S->base;
	S->stacksize = InitSize;
	S->id = id_optr;
	return 1;
}
int StackLength(void* s,int id)
{
	if(id == id_opnd)
	{
		SqStack_OPND* S = (SqStack_OPND*)s;
		if(S->base == NULL)
		{
			return -1;
		}
		return S->top-S->base;
	}
	if(id == id_optr)
	{
		SqStack_OPTR* S = (SqStack_OPTR*)s;
		if(S->base == NULL)
		{
			return -1;
		}
		return S->top-S->base;
	}
	return -1;
}
int PushStack_OPND(SqStack_OPND* S,double e)
{
	if(S->base == NULL)
	{
		puts("nOPND is not exist!");
		return 0;
	}
	if(StackLength(S,S->id) >= S->stacksize)
	{
		S->base = (double*)realloc(S->base,sizeof(double)*(S->stacksize+StepSize));
		if(S->base != NULL)
		{
			S->top = S->base+S->stacksize;
			S->stacksize = S->stacksize+StepSize;
			*(S->top) = e;
			(S->top)++;
			return 1;
		}
		else
		{
			return 0;
		}
	}
	else
	{
		*(S->top) = e;
		(S->top)++;
		return 1;
	}
}
int PushStack_OPTR(SqStack_OPTR* S,char e)
{
	if(S->base == NULL)
	{
		puts("nOPND is not exist!");
		return 0;
	}
	if(StackLength(S,S->id) >= S->stacksize)
	{
		S->base = (char*)realloc(S->base,sizeof(char)*(S->stacksize+StepSize));
		if(S->base != NULL)
		{
			S->top = S->base+S->stacksize;
			S->stacksize = S->stacksize+StepSize;
			*(S->top) = e;
			(S->top)++;
			return 1;
		}
		else
		{
			return 0;
		}
	}
	else
	{
		*(S->top) = e;
		(S->top)++;
		return 1;
	}
}
int PopStack_OPND(SqStack_OPND* S,double* e)
{
	if(S->base == NULL)
	{
		return -1;
	}
	if(S->base == S->top)
	{
		return 0;
	}
	else
	{
		(S->top)--;
		*e = *(S->top);
		return 1;
	}
}
int PopStack_OPTR(SqStack_OPTR* S,char* e)
{
	if(S->base == NULL)
	{
		return -1;
	}
	if(S->base == S->top)
	{
		return 0;
	}
	else
	{
		(S->top)--;
		*e = *(S->top);
		return 1;
	}
}
int GetTopStack_OPND(SqStack_OPND* S,double* e)
{
	if(S->base == NULL)
	{
		return -1;
	}
	if(S->base == S->top)
	{
		return 0;
	}
	else
	{
		*e = *(S->top - 1);
		return 1;
	}
}
int GetTopStack_OPTR(SqStack_OPTR* S,char* e)
{
	if(S->base == NULL)
	{
		return -1;
	}
	if(S->base == S->top)
	{
		return 0;
	}
	else
	{
		*e = *(S->top - 1);
		//printf("*e = %c",*e);
		return 1;
	}
}
int TraverseStack_OPND(SqStack_OPND* S)
{
	if(S->base == NULL)
	{
		return -1;
	}
	if(S->base == S->top)
	{
		printf("栈顶指针----->0:空<-----栈底指针"); 
		return 0;
	}
	double* p;
	printf("栈顶指针----->%dn",StackLength(S,S->id)); 
	for(p = S->top;p - S->base - 1 != -1;p--)
	{
		if((p - S->base - 1) == 0)
		{
			printf("栈底指针----->0:%fn",(S->base)[0]);
		}
		else
		{
			printf("              %d:%fn",p - S->base - 1,(S->base)[p - S->base - 1]);
		}
	}
	return 1;
}
int TraverseStack_OPTR(SqStack_OPTR* S)
{
	if(S->base == NULL)
	{
		return -1;
	}
	if(S->base == S->top)
	{
		printf("栈顶指针----->0:空<-----栈底指针"); 
		return 0;
	}
	char* p;
	printf("栈顶指针----->%dn",StackLength(S,S->id)); 
	for(p = S->top;p - S->base - 1 != -1;p--)
	{
		if((p - S->base - 1) == 0)
		{
			printf("栈底指针----->0:%cn",(S->base)[0]);
		}
		else
		{
			printf("              %d:%cn",p - S->base - 1,(S->base)[p - S->base - 1]);
		}
	}
	return 1;
}
double Operate(double a,char op,double b)
{
	switch(op)
	{
		case '+':return a + b;
		case '-':return a - b;
		case '*':return a*b;
		case '/':
			if(fabs(b-0) <= 0.0000001)
			{
				return -2147483648.2147;
			}
			else
			{
				return a/b; 
			}
		default:return -2147483648.2147;
	}
}
char Precede(char t1,char t2)
{
	switch(t1)
	{
		case '+':
			switch(t2)
			{
				case '+':return '>';
				case '-':return '>';
				case '*':return '<';
				case '/':return '<';
				case '(':return '<';
				case ')':return '>';
				case '#':return '>';
			}
		case '-':
			switch(t2)
			{
				case '+':return '>';
				case '-':return '>';
				case '*':return '<';
				case '/':return '<';
				case '(':return '<';
				case ')':return '>';
				case '#':return '>';
			}
		case '*':
			switch(t2)
			{
				case '+':return '>';
				case '-':return '>';
				case '*':return '>';
				case '/':return '>';
				case '(':return '<';
				case ')':return '>';
				case '#':return '>';
			}
		case '/':
			switch(t2)
			{
				case '+':return '>';
				case '-':return '>';
				case '*':return '>';
				case '/':return '>';
				case '(':return '<';
				case ')':return '>';
				case '#':return '>';
			}
		case '(':
			switch(t2)
			{
				case '+':return '<';
				case '-':return '<';
				case '*':return '<';
				case '/':return '<';
				case '(':return '<';
				case ')':return '=';
				case '#':return '@';
			}
		case ')':
			switch(t2)
			{
				case '+':return '>';
				case '-':return '>';
				case '*':return '>';
				case '/':return '>';
				case '(':return '@';
				case ')':return '>';
				case '#':return '>';
			}
		case '#':
			switch(t2)
			{
				case '+':return '<';
				case '-':return '<';
				case '*':return '<';
				case '/':return '<';
				case '(':return '<';
				case ')':return '@';
				case '#':return '=';
			}	
		default:return '@';
	}
}
double EvaluateExpression()
{
	SqStack_OPND opnd;
	SqStack_OPTR optr;
	
	int n[1] = {0};
	int k = 0;
	char ch;
	char c;
	double pop_a;
	double pop_b;
	char theta;
	char pop_ch;
	double pop_return;
	
	initStack_OPTR(&optr);PushStack_OPTR(&optr,'#');
	initStack_OPND(&opnd);scanf("%c",&c);
	
	while(c != '#' || (GetTopStack_OPTR(&optr,&ch),ch != '#'))  
	{
		if(InOP(OP,c) == 0)
		{
			if((c >= '0' && c <= '9') || c == '.')
			{
				n[0] = 0;
				tnumber[k++] = c;
			}
			//printf("n[0] = %d,n[1] = %d,i-1 = %dn",n[0],n[1],i-1);
			//PushStack_OPND(&opnd,c-48);
			//TraverseStack_OPND(&opnd);
			//TraverseStack_OPTR(&optr);
			//puts("-------------------");
			c = getchar();
		}
		else
		{
			//printf("[c = %c,n[0] = %d]",c,n[0]);
			if(n[0] == 0)
			{
				tnumber[k] = '';
				//PushStack_OPND(&opnd,n[1]);
				PushStack_OPND(&opnd,atof(tnumber));
				n[0] = 1;
				k = 0;
				TraverseStack_OPND(&opnd);
				TraverseStack_OPTR(&optr);
			}

			GetTopStack_OPTR(&optr,&ch);
			switch(Precede(ch,c))
			{
				case '<':
					PushStack_OPTR(&optr,c);
					TraverseStack_OPND(&opnd);
					TraverseStack_OPTR(&optr);
					puts("-------------------");
					c = getchar();
					break;
				case '=':
					PopStack_OPTR(&optr,&pop_ch);
					TraverseStack_OPND(&opnd);
					TraverseStack_OPTR(&optr);
					puts("-------------------");
					c = getchar();
					break;
				case '>':
					PopStack_OPTR(&optr,&theta);
					PopStack_OPND(&opnd,&pop_a);
					PopStack_OPND(&opnd,&pop_b);
					
					if(Operate(pop_b,theta,pop_a) == -2147483648.2147)
					{
						return -2147483648.2147;
					}
					
					PushStack_OPND(&opnd,Operate(pop_b,theta,pop_a));
					TraverseStack_OPND(&opnd);
					TraverseStack_OPTR(&optr);
					puts("-------------------");
					break; 
			}
		}
	}
	GetTopStack_OPND(&opnd,&pop_return);
	free(opnd.base);
	free(optr.base);
	return pop_return;
}
int main()
{
	puts("【输入表达式以#结尾】其中运算符['+','-','*','/','(',')','#']:");
	puts("【参与运算的数字只能是整数或浮点数】"); 
	puts("【例子】:36+69-14*(25-(45/2))-3#"); 
    printf("计算结果:%fn",EvaluateExpression());
	system("pause");
	return 0;
}

二、EvaluateExpression()流程图

在这里插入图片描述

三、 函数模块清单

(1)int InOP(char* OP,char c);
(2)initStack_OPND(SqStack_OPND* S);
(3)initStack_OPTR(SqStack_OPTR* S);
(4)int StackLength(void* s,int id);
(5)int PushStack_OPND(SqStack_OPND* S,double e);
(6)int PushStack_OPTR(SqStack_OPTR* S,char e);
(7) int PopStack_OPND(SqStack_OPND* S,double* e);
(8) int PopStack_OPTR(SqStack_OPTR* S,char* e);
(9) int GetTopStack_OPND(SqStack_OPND* S,double* e);
(10) int GetTopStack_OPTR(SqStack_OPTR* S,char* e);
(11) int TraverseStack_OPND(SqStack_OPND* S);
(12) int TraverseStack_OPTR(SqStack_OPTR* S);
(13) double Operate(double a,char op,double b);
(14) char Precede(char t1,char t2);
(15) double EvaluateExpression();

三、 运行结果示例

3.1 36.8+69-14.5*(25.7-(45.4/2))-3.9#

在这里插入图片描述

3.2 36+69-14*(25-(45/2))-3#

在这里插入图片描述

3.3 动态图形式展示结果

在这里插入图片描述


------------------------------------------------------第九次发文章有点激动啊!-----------------------------------------------------
-----------------------------------------------------【数据结构代码自编练习】------------------------------------------------------
----------------------------------------------------------------【TDTX】-----------------------------------------------------------------

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇

)">
下一篇>>