投稿
  1. 极客之音首页
  2. 技术随笔

数据结构表达式求值的代码实现(C语言)

小半 • • 技术随笔 • 阅读 207

导读：本篇文章讲解 数据结构表达式求值的代码实现(C语言)，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

文章目录

声明：表达式求值的实现使用的是.cpp文件。

  • 由于我使用的是vs2010，vs2010的编译器不支持函数返回值bool类型，并且不能这样定义for(int i= 0; i < 10; i++)，必须在函数的开头声明i=0。为了编写的方便，我使用的是.cpp文件，没有使用.c文件。虽然是c++文件，但是内容是c语言。如果有需要.c文件的，请自行修改这两个地方就可以了。

1. 先转为后缀表达式再计算

1.1 项目结构

在这里插入图片描述

1.2 LinkList.h

/**
* 定义一个简化版的链表，用来存放后缀表达式。
* 只实现4个功能：
*	1. 初始化链表
*	2. 销毁链表
*	3. 在队尾插入元素
*   4. 打印整个链表
*/

// 定义结点
typedef struct Node{
	char data[20];
	int flag;  // flag=1表明data是操作数，flag=0表明data是操作符
	struct Node * next;
} Node;

// 定义链表
typedef struct{
	Node head;
	Node * rear;	// 指向尾结点。因为只用到尾插，这样能够使得尾插算法复杂度为O(1)
} LinkList;


/**
* func:初始化链表
* @list：链表
* return：无
*/
void initList(LinkList * list);


/**
* func:销毁链表
* @list：链表
* return：无
*/
void destroyList(LinkList * list);


/**
* func:向链表的尾部插入结点
* @list：链表
* @x: 要添加的元素的data信息
* @flag: 要添加的元素的flag信息
* return：插入成功，则返回true，失败则返回false
*/
bool insertRearNode(LinkList * list, char * x, int flag);


/**
* func:从头到尾打印整个链表
* @list：链表
* return：无
*/
void printfList(LinkList * list);

1.3 LinkStack.h

/*
* 使用动态链表实现链式栈(不带头结点)
*/


// 1. 定义抽象数据类型
typedef struct {
	char elem[20];
} ElemType;

// 2. 定义链式栈的结点
typedef struct LNode{
	ElemType data;
	struct LNode * next;
} LNode;

// 3. 定义一些接口

/**
* func:初始化链式栈
* @head：头指针
*/
void initStack(LNode ** head);


/**
* func:销毁链式栈
* @head：头指针
*/
bool isStackEmpty(LNode * head);


/**
* func:判断栈是否为空
* @head：头指针
*/
void destroyStack(LNode ** head);


/**
* func:向栈顶压入元素
* @head：头指针
* @x：要添加的元素
*/
bool push(LNode * head, ElemType x);


/**
* func:弹出栈顶元素
* @head：头指针
* @x：存放要删除的元素
*/
bool pop(LNode * head, ElemType * x);


/**
* func:查看栈顶元素
* @head：头指针
* @x：存放要查看的元素
*/
bool selectStackTopElem(LNode * head, ElemType * x);

1.4 parseExpro.h

#include "LinkStack.h"
#include "LinkList.h"

// 函数的声明(或者叫定义接口)


/**
* func:将字符封装为抽象数据类型，方便使用之前写过的链式栈
* @x：要封装的字符
* return:封装的抽象数据类型
*/
ElemType getElem(char x);


/**
* func:得到表达式的数字部分
* @expro：表达式
* @i：从expro的i处开始获取操作数
* @list：用来存放后缀表达式的链表
* return：返回expro中该操作数后紧跟的操作符的下标
*/
int digit(char * expro, int i, LinkList * list);


/**
* func:比较两个运算符的优先级
* @a：运算符
* @b：运算符
* return：如果a大于b的优先级返回>, a等于b的优先级返回=，a小于b的优先级返回<
*/
char getPriority(char a, char b);


/**
* func:实现中缀表达式转后缀表达式,并放入list链表中
* @expro：要求解的中缀表达式
* @list：用来存放后缀表达式的链表
* return：如果转换成功，则返回true，反之则返回false
*/
bool getAfterExpro(char * expro, LinkList * list);


/**
* func:利用栈对后缀表达式求解
* @list：用来存放后缀表达式的链表
* @result: 用来存放计算后缀表达式的结果
* return：计算成功，返回true，否则返回false
*/
bool calculation(LinkList * list, double * result);


/**
* func:对两个操作数与一个运算符，计算结果
* @a：左操作数
* @b：右操作数
* @oper：运算符
* return：返回计算的结果(double类型)
*/
double calcu(double a, double b, char oper);

1.5 LinkList.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkList.h"


/**
* func:初始化链表
* @list：链表
* return：无
*/
void initList(LinkList * list) {
	list->rear = NULL;
	list->head.next = NULL;
}


/**
* func:销毁链表
* @list：链表
* return：无
*/
void destroyList(LinkList * list) {
	Node * p = list->head.next;
	Node * t;
	while (p != NULL) {
		t = p;
		p = p->next;
		free(t);
	}
	p = t = NULL;
	// 将链表的头指针和尾指针都指为NULL
	list->head.next = list->rear = NULL;
}

/**
* func:向链表的尾部插入结点
* @list：链表
* @x: 要添加的元素的data信息
* @flag: 要添加的元素的flag信息
* return：插入成功，则返回true，失败则返回false
*/
bool insertRearNode(LinkList * list, char * x, int flag) {
	// 开辟新结点
	Node * t = (Node * )malloc(sizeof(Node));
	t->next = NULL;
	t->flag = flag;
	strcpy(t->data, x);	// 利用string.h的strcpy进行字符串复制

	// 将结点添加到链表尾部
	if (list->head.next == NULL)
		list->head.next = list->rear = t;
	else {
		list->rear->next = t;
		list->rear = t;
	}
	
	return true;
}


/**
* func:从头到尾打印整个链表
* @list：链表
* return：无
*/
void printfList(LinkList * list) {
	Node * p = list->head.next;
	while(p != NULL) {
		printf("%s ", p->data);
		p = p->next;
	}
	printf("\n");
}

1.6 LinkStack.cpp

#include <stdio.h>
#include <stdlib.h>
#include "LinkStack.h"

/**
* func:初始化链式栈
*/
void initStack(LNode ** head) {
	*head = (LNode *)malloc(sizeof(LNode));
	(*head)->next = NULL;
}


/**
* func判断栈是否为空
* @head：头指针
*/
bool isStackEmpty(LNode * head) {
	if (head->next == NULL)
		return true;
	else
		return false;
}


/**
* func:销毁链式栈
* @head：头指针
*/
void destroyStack(LNode ** head) {
	LNode * t;
	while(*head != NULL) {
		t = *head;
		*head = (*head)->next;
		free(t);
	}
	*head = t = NULL;
}


/**
* func:向栈顶压入元素
* @head：头指针
* @x：要添加的元素
*/
bool push(LNode * head, ElemType x) {
	// 先动态分配一个结点
	if (head == NULL)
		return false;
	LNode * temp = (LNode *)malloc(sizeof(LNode));
	if (temp == NULL)
		return NULL;
	// 再将该结点压入栈中
	temp->data = x;
	temp->next = head->next;
	head->next = temp;
	return true;
}


/**
* func:弹出栈顶元素
* @head：头指针
* @x：存放要删除的元素
*/
bool pop(LNode * head, ElemType * x) {
	// 判断栈是否为空
	if (isStackEmpty(head)) 
		return false;
	// 栈不为空，则删除栈顶元素
	LNode * p = head->next;
	*x = p->data;
	head->next = p->next;
	free(p);
	p = NULL;
	return true;
}


/**
* func:查看栈顶元素
* @head：头指针
* @x：存放要查看的元素
*/
bool selectStackTopElem(LNode * head, ElemType * x) {
	// 判断栈是否为空
	if (isStackEmpty(head)) 
		return false;
	// 栈不为空，则查看栈顶元素
	*x = head->next->data;
	return true;
}

1.7 parseExpro.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "parseExpro.h"

// 使用先将表达式转为后缀表达式，再对表达式求解的方式


/**
* func:将字符封装为抽象数据类型，方便使用之前写过的链式栈
* @x：要封装的字符
* return:封装的抽象数据类型
*/
ElemType getElem(char x) {
	ElemType temp;
	// 将temp的elem字符数组初始化为{0}
	for (int i = 0; i < sizeof(temp.elem)/sizeof(temp.elem[0]); i++)
		temp.elem[i] = 0;
	temp.elem[0] = x;
	return temp;
}


/**
* func:得到表达式的数字部分
* @expro：表达式
* @i：从expro的i处开始获取操作数
* @list：用来存放后缀表达式的链表
* return：返回expro中该操作数后紧跟的操作符的下标
*/
int digit(char * expro, int i, LinkList * list) {
	char temp[20] = {0};
	int j = 0;
	while(expro[i] >= '0' && expro[i] <= '9' || expro[i] == '.') {
		temp[j] = expro[i];
		i++;
		j++;
	}
	insertRearNode(list, temp, 1); //将操作数放入链表中
	// 此时expro[i]对应的应该是操作符的位置
	return i;
}


/**
* func:比较两个运算符的优先级
* @a：运算符
* @b：运算符
* return：如果a大于b的优先级返回>, a等于b的优先级返回=，a小于b的优先级返回<
*/
char getPriority(char a, char b) {
	char priority[6][6] = {
	//    +    -    *    /    (    )
		{'=', '=', '<', '<', '>', '<'}, // +
		{'=', '=', '<', '<', '>', '<'}, // -
		{'>', '>', '=', '=', '>', '<'}, // *
		{'>', '>', '=', '=', '>', '<'}, // /
		{'>', '>', '>', '>', '=', '='}, // (
		{'>', '>', '>', '>', '>', '='}  // )
	};
	char * flag = "+-*/()";
	int i = 0;
	int j = 0;
	for (i = 0; flag[i] != '\0'; i++)
		if (a == flag[i])
			break;
	for (j = 0; flag[j] != '\0'; j++)
		if (b == flag[j])
			break;
	return priority[i][j];
}



/**
* func:实现中缀表达式转后缀表达式,并放入list链表中
* @expro：要求解的中缀表达式
* @list：用来存放后缀表达式的链表
* return：如果转换成功，则返回true，反之则返回false
*/
bool getAfterExpro(char * expro, LinkList * list) {
	// 这里应该先判断中缀表达式是否合法，如果不合法，则返回false（后面填上）

	// 声明一个栈
	LNode * stack;
	initStack(&stack);

	// 遍历中缀表达式，并进行转换
	for (int i = 0; expro[i] != '\0'; i++) {
		// 得到当前的操作数或运算符
		if (expro[i] >= '0' && expro[i] <= '9' || expro[i] == '.') { // 说明当前是操作数
			// 获取操作数，并将得到的操作数放入链表中
			i = digit(expro, i, list); // 此时expro[i]对应的应该是操作符的位置
			i--;	// 由于for循环的i++，所以，这里要减1，才能保证下一次的expro[i]对应的应该是操作符的位置
		} else {		// 说明当前是运算符
			ElemType t, x;
			// 判断当前运算符
			if (expro[i] == '(') {	// 如果运算符是 ( 则直接入栈
				// ( 入栈
				push(stack, getElem('('));
			} else if (expro[i] == ')') {   // 运算符为 ) ，需要不断从栈中弹出运算符，直到遇到(
				selectStackTopElem(stack, &t);
				while (t.elem[0] != '(') {
					pop(stack, &x); //弹出栈顶元素
					insertRearNode(list, x.elem, 0);
					selectStackTopElem(stack, &t);
				}
				pop(stack, &x);  // 弹出此时的 ( ，不需要加入栈中
			} else {
				char result = '=';	
				while (result != '>') {
					// 判断栈是否为空
					if (isStackEmpty(stack)) {  // 栈为空就直接将运算符压入栈中
						break;
					}
					else {	// 如果栈不为空，就判断栈顶运算符与该运算符的优先级
						selectStackTopElem(stack, &t);
						result = getPriority(expro[i], t.elem[0]);	// 查看栈顶元素,并判断运算符优先级
					
						if (result == '>') {  // 当前运算符大于栈顶运算符的优先级，则该运算符入栈
							break;
						} else {  // 当前运算符小于或等于栈顶运算符的优先级，则弹出栈顶元素，并加入到后缀表达式中
							pop(stack, &x); //弹出栈顶元素
							insertRearNode(list, x.elem, 0);
						}

					}
				}
				// 再将当前元素入栈
				push(stack, getElem(expro[i]));
			
			}

		}
	
	}
	// 判断栈是否为空
	while (false == isStackEmpty(stack)) {
		ElemType x;
		pop(stack, &x); //弹出栈顶元素
		insertRearNode(list, x.elem, 0);
	}
	return true;
}


/**
* func:利用栈对后缀表达式求解
* @list：用来存放后缀表达式的链表
* @result: 用来存放计算后缀表达式的结果
* return：计算成功，返回true，否则返回false
*/
bool calculation(LinkList * list, double * result) {
	// 1. 声明一个栈, 并初始化
	LNode * stack;
	initStack(&stack);

	// 2. 对后缀表达式求解
	ElemType x, a, b;
	Node * p = list->head.next;
	while (p != NULL) {
		if (p->flag == 1) {	// 说明是操作数，需要入栈
			strcpy(x.elem, p->data);
			push(stack, x);
		} else { // 如果是运算符，就从栈中弹出两个操作数,如果后缀表达式正确，此时栈一定会有两个操作数
			// 1. 取出两个操作数
			if (isStackEmpty(stack))
				return false;
			pop(stack, &b);
			if (isStackEmpty(stack))
				return false;
			pop(stack, &a);
			// 2. 两个操作数与一个运算符，计算结果
			double temp = calcu(atof(a.elem), atof(b.elem), p->data[0]); // atof是<stdlib.h>里的函数：将字符串转为double
			// 3. 将计算的结果压入栈中
			sprintf(x.elem,"%lf", temp);
			push(stack, x);
		}
		p = p->next;
	}
	// 最后，弹出计算的结果
	if (isStackEmpty(stack))
		return false;
	pop(stack, &x);
	*result = atof(x.elem);
	return true;
}


/**
* func:对两个操作数与一个运算符，计算结果
* @a：左操作数
* @b：右操作数
* @oper：运算符
* return：返回计算的结果(double类型)
*/
double calcu(double a, double b, char oper) {
	double result = 0;
	switch (oper) {
		case '+':{
			result = a + b;
			break;
		}
		case '-':{
			result = a - b;
			break;
		}
		case '*':{
			result = a * b;
			break;
		}
		case '/':{
			result = a / b;
			break;
		}
	}
	return result;
}

1.8 main.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "parseExpro.h"


void main() {
	char expro[255];
	double result = -1;
	printf("=============【表达式求值】=============\n");
	printf("1.支持运算符：+、-、*、/\n");
	printf("2.支持括号（）\n");
	printf("3.支持浮点数。\n");
	printf("请输入表达式，按回车结束!\n");
	printf("例如：5*(3+4)/2\n");
	printf("表达式：");
	scanf("%s", expro);

	// 声明链表，用来存放后缀表达式
	LinkList list;
	initList(&list);

	getAfterExpro(expro, &list);
	printf("后缀表达式为：");
	printfList(&list);

	double t = 0;
	calculation(&list, &t);
	printf("后缀表达式的计算结果为：%lf\n", t);
}

1.9 运行截图

在这里插入图片描述
在这里插入图片描述

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/84618.html

赞 (0)
小半的头像小半
0 0

相关推荐

极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！