目录：

前言

在这里插入图片描述
朋友们大家好，前段时间熊猫我学习了栈的相关知识，通过做题发现栈可以解决一些很有价值的事情，比如：表达式求值。
下面我会通过LeetCode上《有效的括号》这个题进行引入，讲解表达式求值的实现，希望能为大家带来帮助。

一、有效的括号

点击跳转LeetCode：有效的括号

题目描述：
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
在这里插入图片描述

（一）题目分析

本题要求我们判断括号是否有效，那么我们需要知道什么形式的括号才是有效的？
1.括号的总数量一定是偶数个，并且左右括号各占一半；
2.左括号必须和与之对应的右括号相结合，既 ‘(’ 必须和 ‘)’ 对应，‘[’ 和 ‘]’ 以及 ‘{’ 和 ‘}’ 亦然；
3.必须先有左括号再有右括号。
通过上面的分析我们可以知道，遇到左括号就入栈，出现右括号就和栈区最后一个左括号进行匹配，匹配上了就出栈，否则就是无效的括号，并且最后栈区是空的。

括号一定是成对出现的

	int sz = strlen(s);
	if (sz % 2 != 0) 
		return false;

遇到左括号就入栈，遇到右括号就出栈

char* arr = (char*)malloc(sz);
	int a = 0; // 记录栈区字符的个数
	for (int i = 0; i < sz; i++)
	{
		switch (s[i])
		{
		case '(':
		case '[':
		case '{':
			arr[a++] = s[i];
			break;
		case ')':
			if (a > 0 && arr[--a] == '(')
				break;
			else
				return false;
				
		case ']':
			if (a > 0 && arr[--a] == '[')
				break;
			else
				return false;
		case '}':
			if (a > 0 && arr[--a] == '{')
				break;
			else
				return false;
		}
	}

最后我们还需要判断栈区是否为空，防止左括号比右括号多

 if(a==0)
	return true;
    else
    return false;

（二）整体代码

示例：

bool isValid(char* s) {
	int sz = strlen(s);
	if (sz % 2 != 0)
		return false;
	char* arr = (char*)malloc(sz);
	int a = 0; // 记录栈区字符的个数
	for (int i = 0; i < sz; i++)
	{
		switch (s[i])
		{
		case '(':
		case '[':
		case '{':
			arr[a++] = s[i];
			break;
		case ')':
			if (a > 0 && arr[--a] == '(')
				break;
			else
				return false;
				
		case ']':
			if (a > 0 && arr[--a] == '[')
				break;
			else
				return false;
		case '}':
			if (a > 0 && arr[--a] == '{')
				break;
			else
				return false;
		}
	}
    if(a==0)
	return true;
    else
    return false;
}

运行实例：
在这里插入图片描述

二、表达式求值

上一个例题我们写的十分简陋，虽然说是用到了栈，不过只是用到了它的思想而没有具体实现出来，下面一个例题熊猫我会直接先把栈区的操作实现出来，让大家真真正正滴了解一下栈的操作（防止大家觉得熊猫我不够专业）。

题目描述：
以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，
我们需要实现对算术四则混合运算表达式的求值。
测试数据：
3*(7-1)；1+2+3+4；88-15；(20+2)(6/2)；6+2*(3+6)。

（一）题目分析

题目要求我们实现对算数四则混合运算表达式的求值，这里我们首先需要注意两点：
1.小括号的优先级最高，我们需要先进行括号里的表达式运算
2.乘法和除法的优先级高于加法和减法

1.栈的基本操作：

#define MALLOC(ty,num) (ty*)malloc(sizeof(ty)*(num))
#define REALLOC(block,ty,num) (ty*)realloc(block,sizeof(ty)*(num));
#define OK 1
#define ERROR 0
#define INITNUM 5	//初始化顺序表长度
#define ADDNUM 3	//之后每次增加的长度
typedef double selemtype;

typedef struct SQStack
{
	selemtype* data;
	int length;
	int maxnum;
}SQS;


void Init(SQS* p)  栈的初始化
{ 
	assert(p);
	p->data = MALLOC(selemtype, INITNUM);
	if (!p->data)
	{
		return;
	}

	p->length = 0;//顺序栈下一个元素的下标
	p->maxnum = INITNUM;
}

void Destroy(SQS* p)  // 栈的销毁
{
	assert(p);

	free(p->data);
	p->length = 0;
	p->maxnum = 0;
}

static int Judge(SQS* p)  // 判断栈区是否已满并扩容
{
	assert(p);
	if (p->length == p->maxnum)//满了
	{
		selemtype* newblock = REALLOC(p->data, selemtype, p->length + ADDNUM);
		if (newblock == NULL)
		{
			return ERROR;
		}

		p->data = newblock;
		p->maxnum = p->length + ADDNUM;
	}
	return OK;
}

void Push(SQS* p, selemtype con)    //  入栈
{
	assert(p);

	Judge(p);

	p->data[p->length] = con;
	p->length++;
}

void Pop(SQS* p)   //  出栈
{
	assert(p);

	p->length--;
}

int JudgeOverflow(SQS* p)   //  判断栈区是否为空
{
	assert(p);

	if (p->length == 0)
	{
		return ERROR;
	}
	else
	{
		return OK;
	}
}

selemtype GetTop(SQS* p)    //   获取栈顶数据
{
	assert(p);

	return p->data[p->length - 1];
}

2. 大体思路：

由于小括号运算优先级最高，所以我们需要先计算括号内再计算括号外；
我们这里可以先判断小括号是否存在，如果没有遇到括号、或者遇到了左括号我们就继续进栈，直到遇到了右括号我们再出栈，
当然，出栈也有限制：
1.出到了左括号就停止出栈，这时一个括号内的表达式就计算结束了
2.如果栈空了就说明这整个表达式就计算结束了，此时我们就已经功德圆满啦（bushi）。

selemtype Expression(char* str)
{
	SQS s;
	Init(&s);

	double con = 0; // 表达式结果
	char* p = NULL; // 

	int i = 0;
	for (i = 0; str[i]; ) // 遍历字符串
	{

		if (isdigit(str[i])) // 判断是数值
		{
		 //  本函数是将字符串转为double类型数据，并且返回转换数据结束时后一个位置的地址，我们将它存放在指针p中
		 //这里不可以直接 push(str[i]);
		 //是为了防止参与运算的数值中有小数、以及不止一位数的数据
			selemtype val = strtod(&str[i], &p); 
			Push(&s, val);

			i = p - str; // 更新下标
		}
		else  // 符号
		{

			if (str[i] != ')')
			{
				Push(&s, str[i]);
			}
			else     // 如果遇到右括号我们就讲括号内的表达式进行一次求值
			{
				con = Evaluation(&s);
				Push(&s, con);   //  求得的值要继续入栈，最后需要再整体进行一次运算
			}

			i++; // 更新下标
		}
	}

	con = Evaluation(&s);    //  整体结果运算

	Destroy(&s);

	return con;
}

经过上面的理想操作，我们就可以得到想要的结果，
为了便于下面运算函数的实现，我们大家可以通过下面的图解来大致了解操作过程。
在这里插入图片描述

3.具体计算过程：

这里我们不需要考虑括号，主要考虑的是优先级的问题（还有一些特殊情况）
下面我们先来画图分析一下：
在这里插入图片描述

selemtype Evaluation(SQS* ps)
{
	selemtype con = 0;
	selemtype val1 = GetTop(ps); // 数值
	Pop(ps);
	selemtype val2 = 0;

	while (JudgeOverflow(ps)) // 栈为空就退出
	{

		switch ((char)GetTop(ps))
		{
		case'+':
		{
			Pop(ps); // 将 '+' 出栈

			val2 = GetTop(ps);
			Pop(ps);

			con += val1;
			val1 = val2;

		}
		break;

		case '-':
		{
			Pop(ps);

			if (!JudgeOverflow(ps))  //  特殊1.这个地方是要避免第一个数是负数
			{
				con -= val1;
				return con;
			}

			val2 = GetTop(ps);
			Pop(ps);

			con -= val1;
			val1 = val2;

		}
		break;

		case '*':
		{
			Pop(ps);

			val1 *= GetTop(ps);
			Pop(ps);
		}
		break;

		case '/':
		{
			Pop(ps);
			val2 = GetTop(ps);
			Pop(ps);
			if (GetTop(ps) == '/')  //  特殊2：出栈是后进先出的，因此如果出现连除情况需要特殊处理
				val1 = val1 * val2;
			else
				val1 = val2 / val1;
		}
		break;

		case '(':
			Pop(ps);
			goto end;
		}
	}

end:
	con += val1;
	return con;

}

两种特殊情况：
在这里插入图片描述

（二）整体代码

示例：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<assert.h>

#define MALLOC(ty,num) (ty*)malloc(sizeof(ty)*(num))
#define REALLOC(block,ty,num) (ty*)realloc(block,sizeof(ty)*(num));
#define OK 1
#define ERROR 0
#define INITNUM 5	//初始化顺序表长度
#define ADDNUM 3	//之后每次增加的长度
typedef double selemtype;

typedef struct SQStack
{
	selemtype* data;
	int length;
	int maxnum;
}SQS;


void Init(SQS* p)
{
	assert(p);
	p->data = MALLOC(selemtype, INITNUM);
	if (!p->data)
	{
		return;
	}

	p->length = 0;//顺序栈下一个元素的下标
	p->maxnum = INITNUM;
}

void Destroy(SQS* p)
{
	assert(p);

	free(p->data);
	p->length = 0;
	p->maxnum = 0;
}

static int Judge(SQS* p)
{
	assert(p);
	if (p->length == p->maxnum)//满了
	{
		selemtype* newblock = REALLOC(p->data, selemtype, p->length + ADDNUM);
		if (newblock == NULL)
		{
			return ERROR;
		}

		p->data = newblock;
		p->maxnum = p->length + ADDNUM;
	}
	return OK;
}

//入栈
void Push(SQS* p, selemtype con)
{
	assert(p);

	Judge(p);

	p->data[p->length] = con;
	p->length++;

}

void Pop(SQS* p)
{
	assert(p);

	p->length--;
}

int JudgeOverflow(SQS* p)
{
	assert(p);

	if (p->length == 0)
	{
		return ERROR;
	}
	else
	{
		return OK;
	}
}

selemtype GetTop(SQS* p)
{
	assert(p);

	return p->data[p->length - 1];
}

selemtype Evaluation(SQS* ps)
{
	selemtype con = 0;
	selemtype val1 = GetTop(ps); // 数值
	Pop(ps);
	selemtype val2 = 0;

	while (JudgeOverflow(ps))
	{

		switch ((char)GetTop(ps))
		{
		case'+':
		{
			Pop(ps); // 将 '+' 出栈

			val2 = GetTop(ps);
			Pop(ps);

			con += val1;
			val1 = val2;

		}
		break;

		case '-':
		{
			Pop(ps);

			if (!JudgeOverflow(ps))
			{
				con -= val1;
				return con;
			}

			val2 = GetTop(ps);
			Pop(ps);

			con -= val1;
			val1 = val2;

		}
		break;

		case '*':
		{
			Pop(ps);

			val1 *= GetTop(ps);
			Pop(ps);
		}
		break;

		case '/':
		{
			Pop(ps);
			val2 = GetTop(ps);
			Pop(ps);
			if (GetTop(ps) == '/')
				val1 = val1 * val2;
			else
				val1 = val2 / val1;
		}
		break;

		case '(':
			Pop(ps);
			goto end;
		}
	}

end:
	con += val1;
	return con;

}

selemtype Expression(char* str)
{
	SQS s;
	Init(&s);

	double con = 0; // 表达式结果
	char* p = NULL; // 

	int i = 0;
	for (i = 0; str[i]; ) // 遍历字符串
	{

		if (isdigit(str[i])) // 数值
		{
			selemtype val = strtod(&str[i], &p);
			Push(&s, val);

			i = p - str; // 更新下标
		}
		else  // 符号
		{

			if (str[i] != ')')
			{
				Push(&s, str[i]);
			}
			else
			{
				con = Evaluation(&s);
				Push(&s, con);
			}

			i++; // 更新下标
		}
	}

	con = Evaluation(&s);

	Destroy(&s);

	return con;
}

int main()
{
	while (1)
	{
		printf("请输入表达式：");
		char str[100] = { 0 };
		scanf("%s", str);

		selemtype con = 0;//表达式结果
		con = Expression(str);
		printf("表达式结果为：%.2lf\n\n", con);
	}
	return 0;
}

运行实例：

在这里插入图片描述

总结

以上就是表达式求值的全部内容，熊猫这边建议大家在学习的过程中可以尝试着做一些有趣的东西，这样不仅能够提高自己的学习积极性，对自己的实力也能做到很好的打磨，何乐而不为呢~。
那么今天就讲解到这里，如果有什么疑问或者建议都可以在评论区留言，感谢大家对在这里插入图片描述的支持。

# leetcode # 算法 # c语言 # c++
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

OpenLoong项目通过技术监督委员会（TOC）评审

OpenLoong项目通过技术监督委员会（TOC）评审

avatar 开放原子开发者工作坊

开发者谈开源：KWDB开源数据库的未来路径与生态构建实践

开发者谈开源：KWDB开源数据库的未来路径与生态构建实践

avatar 开放原子开发者工作坊

开发者谈开源：洞悉协作创新背后的机遇与挑战

近日，在2024开放原子开发者大会暨首届开源技术学术大会开幕式上，开放原子开源基金会与openKylin、EasyAda、KWDB开源项目举行捐赠签约仪式。 一场捐赠签约仪式，让三个开源项目及其背后的开发者们受到瞩目。本次，我们与“龘”（EasyAda）核心维护者王伶卓开启了对话。

avatar 开放原子开发者工作坊