数据结构实验1——数学表达式求值

全文共: 1.3k字   |   阅读时长: 6分
知识整理本科课程大二
  阅读

文章导航

大二上数据结构实验1内容，使用C语言实现数学表达式求值

一、实验题目和要求

数学表达式求值

（一） 实验目的：熟练掌握栈、队列等基本操作及其在实际问题中的应用。

（二）基本要求：实现栈的基本操作，及表达式求值的实现。

（三）内容提要：用户需要输入一个表达式。

（四）实现：

​ 1、实现栈的push、pop基本操作；

2、检测表达式的输入是否是正确的数学表达式；

3、对于正确的数学表达式求取其值。

注：1）数学表达式的判读与求值需支持加减乘除、小括号、中括号、大括号、幂运算。

2）不正确的表达式可能包括：字母、非运算符号、括号不匹配，运算符的排列不符合表达式形式等多种情况。

3）表达式通过.txt文件读取而获得。

二、按不同功能分析各程序模块

(一)包含库函数、定义常量、变量类型

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
#include<stdlib.h> 
#include<string.h> 
#include<math.h>
#include <iostream>  
#include <iomanip>  
#include <fstream>  
#include<cassert>
#define true 1 
#define false 0 
#define OPSETSIZE 12 
using namespace std; 
typedef int Status;

(二)定义运算符优先级表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
unsigned char Prior[12][12] =
{ // 运算符优先级表 
	    // '+' '-' '*' '/' '(' ')' '#' '^' '[' ']' '{' '}' 
	/*'+'*/'>','>','<','<','<','>','>','<','<','>','<','>', 
	/*'-'*/'>','>','<','<','<','>','>','<','<','>','<','>', 
	/*'*'*/'>','>','>','>','<','>','>','<','<','>','<','>',  
	/*'/'*/'>','>','>','>','<','>','>','<','<','>','<','>',  
	/*'('*/'<','<','<','<','<','=',' ','<',' ',' ',' ',' ', 
	/*')'*/'>','>','>','>',' ','>','>','>',' ','>',' ','>', 
	/*'#'*/'<','<','<','<','<',' ','=','<','<','<','<','<', 
	/*'^'*/'>','>','>','>','<','>','>','>','<','>','<','>',
	/*'['*/'<','<','<','<','<',' ',' ','<',' ','=',' ',' ',
	/*']'*/'>','>','>','>',' ',' ','>','>',' ',' ',' ','>',
	/*'{'*/'<','<','<','<','<',' ',' ','<','<',' ','<','=',
	/*'}'*/'>','>','>','>',' ',' ','>','>',' ',' ',' ','<'
};

(三)数据结构基础定义（栈的存储结构定义）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//-------------数据结构基础定义------------
typedef struct StackSymbol
{
	char c; 
	struct StackSymbol *next; 
}SC;       //运算符的节点
 
typedef struct StackData
{
	float f; 
	struct StackData *next; 
}SF;       //数字的节点
 
SC *Push(SC *s,char c)          //运算符节点入栈
{
	SC *p=(SC*)malloc(sizeof(SC)); 
	p->c=c; 
	p->next=s; 
	return p; 
} 
 
SF *Push(SF *s,float f)        //数字节点入栈
{
	SF *p=(SF*)malloc(sizeof(SF)); 
	p->f=f; 
	p->next=s; 
	return p; 
} 
 
SC *Pop(SC *s)    //运算符节点出栈
{
	SC *q=s; 
	s=s->next; 
	free(q); 
	return s; 
} 
 
SF *Pop(SF *s)      //数字节点出栈
{
	SF *q=s; 
	s=s->next; 
	free(q); 
	return s; 
}

(四)子函数定义

（包括两两运算操作、判断字符是否为运算符、判断运算符的优先级、计算表达式）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//------------子函数定义--------------
//两两运算操作
float Operate(float a,unsigned char theta, float b)      
{
	switch(theta)
	{
	case '+': return a+b; 
	case '-': return a-b; 
	case '*': return a*b; 
	case '/': return a/b; 
	case '^': return pow(a,b); 
	default : return 0; 
	} 
}
char OPSET[OPSETSIZE]={'+','-','*','/','(',')','#','^','[',']','{','}'}; //运算符数组
//判断字符是否为运算符
Status In(char Test,char *TestOp)
{
	int Find=false; 
	for (int i=0; i< OPSETSIZE; i++)
	{
		if(Test == TestOp[i])
			Find= true; 
	} 
	return Find; 
} 
//判断字符是哪个运算符
Status ReturnOpOrd(char op,char *TestOp)
{ 
	for(int i=0; i< OPSETSIZE; i++)
	{
		if (op == TestOp[i])
			return i;
	}
}
//判断运算符的优先级a,b分别为两个运算符
char precede(char a, char b)
{ 
	return Prior[ReturnOpOrd(a,OPSET)][ReturnOpOrd(b,OPSET)]; 
} 
 //计算表达式的函数
float Calculate(char* Expression)
{ 
	// 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合 
	SC *OPTR=NULL;       // 运算符栈，字符元素 
	SF *OPND=NULL;       // 运算数栈，实数元素 
	char TempData[20]; 
	float Data,a,b; 
	char theta,*c,Dr[]={'#','\0'}; 
	OPTR=Push(OPTR,'#'); 
	c=strcat(Expression,Dr); //将一个字符串连接到另一个字符串的尾部 
	strcpy(TempData,"\0");//字符串复制函数 
	while (*c!= '#' || OPTR->c!='#')//字符串的两端用#隔开作为一个整体 
	{ 
		if (!In(*c, OPSET))
		{ 
			Dr[0]=*c; 
			strcat(TempData,Dr);           //字符串连接函数 
			c++; 
			if (In(*c, OPSET))
			{ 
				Data=atof(TempData);       //字符串转换函数(double) 
				OPND=Push(OPND, Data); 
				strcpy(TempData,"\0"); 
			} 
		} 
		else    // 不是运算符则进栈 
		{
			switch (precede(OPTR->c, *c))
			{
			case '<': // 栈顶元素优先级低 
				OPTR=Push(OPTR, *c); 
				c++; 
				break; 
			case '=': // 脱括号并接收下一字符 
				OPTR=Pop(OPTR); 
				c++; 
				break; 
			case '>': // 退栈并将运算结果入栈 
				theta=OPTR->c;OPTR=Pop(OPTR); 
				b=OPND->f;OPND=Pop(OPND); 
				a=OPND->f;OPND=Pop(OPND); 
				OPND=Push(OPND, Operate(a, theta, b)); 
				break;
			default:printf("error! \n");
				return 1; 
			} //switch
		} 
	} //while 
	return OPND->f; 
} //Calculate

(五)主函数

包括从txt文件输入表达式、调用计算函数求值、输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main(void) 
{
    char s[128];
	char s1[100] = {0};	
int len = 0; 
	FILE *fp = fopen("E://math.txt", "r");//用txt文件输入数学表达式 
	if(NULL == fp)	
	{		
	printf("failed to open dos.txt\n");	
	return 1;
	} 
	while(!feof(fp))	
	{		memset(s, 0, sizeof(s));	
	fgets(s, sizeof(s) - 1, fp); // 包含了换行符
		//printf("%s", s);
	}
 	fclose(fp);
	puts("该表达式的值为:"); 
	printf("%s\b=%g\n",s,Calculate(s));
	system("pause");
	return 0;
}

三、运行结果分析

(一)基础用例

全部通过

(二)拓展用例

表达式错误

虽然检测到了表达式错误，但是还是运算出了结果，在检测到表达式有问题时，没有跳出返回，而是继续执行，所以出现了错误。 表达式错误

通过 异常

通过

通过 表达式错误

未通过，在定义运算符优先级时，未能考虑到中括号的嵌套问题，导致没有检测出错误，运算出了结果。

通过 通过

本站总访问量次 | 您是第位访客