栈的应用 -- 表达式求值

视频链接: https://www.bilibili.com/video/BV1GV411f727?from=search&seid=9534689624618054203&spm_id_from=333.337.0.0.
部分图片来源B站 Laura柳进和懒猫老师。非常感谢！！！

表格为空输入的表示表达式错误。

这里的程序设计中在初始化时要先将“#”压入OPTR栈中，这样做
1、可以方便后入栈的运算符进行优先级比较。
2、判断什么时候运算表达式运算结束，就是“#”遇到“#”的时候。

C语言实现：

这个视频介绍的代码是C转为C++形式的，用的是结构体。所以大部分使用引用来实现的，我将其中的1、2个函数改为了用指针来实现。大部分没有改。

因为代码是C转为C++形式的，用的是结构体。所以需要构造两个栈，一个是字符栈，一个是数字栈。其实，可以用C++中的类模板来实现。

1、该代码解决了不能输入多位数字的问题。
2、该代码解决了输入错误字符的问题。
3、释放了堆内存，避免造成内存泄露

代码分为四个文件，还有继续抽象和分层的空间。

stack_opr.h

#ifndef _STACK_OPR_H_
#define _STACK_OPR_H_

#include "stack_expression.h"

//运算符栈的初始化
Status InitStackS(SqStack_optr& S);

//操作数栈的初始化
Status InitStackN(SqStack_opnd& N);

//运算符栈的入栈操作
Status PushS(SqStack_optr* S, SElemType str);

//操作数栈的入栈操作
Status PushN(SqStack_opnd* N, SElemType num);

//运算符栈的出栈操作
Status PopS(SqStack_optr& S, SElemType& str);

//操作数栈的出栈操作
Status PopN(SqStack_opnd& N, NElemType& num);

//运算符栈取栈顶元素
SElemType GetTopS(SqStack_optr& S);

//操作数栈取栈顶元素
NElemType GetTopN(SqStack_opnd& N);

void DestroyStackS(SqStack_optr& S);

void DestroyStackN(SqStack_opnd& N);

#endif

stack_opr.cpp

#include "stack_opr.h"

//运算符栈的初始化
Status InitStackS(SqStack_optr &S)
{
	S.base = new SElemType[MAXSIZE];
	//新建连续存储空间：类型是SElemType，大小是MAXSIZE(100)，然后赋值给栈底指针。
	if (!S.base)
		return ERROR;//分配失败
	S.top = S.base;//把base栈底指针的地址也赋值给栈顶指针
	S.stacksize = MAXSIZE;//栈的容量
	return OK;
}

//操作数栈的初始化
Status InitStackN(SqStack_opnd& N)
{
	N.base = new NElemType[MAXSIZE];
	//新建连续存储空间：类型是SElemType，大小是MAXSIZE(100)，然后赋值给栈底指针。
	if (!N.base)
		return ERROR;//分配失败
	N.top = N.base;//把base栈底指针的地址也赋值给栈顶指针
	N.stacksize = MAXSIZE;//栈的容量
	return OK;
}

//运算符栈的入栈操作
Status PushS(SqStack_optr* S, SElemType ch)
{
	if (S->top - S->base == S->stacksize)//栈满
		return ERROR;
	*S->top++= ch;//先入栈，top再加1
	return OK;
}

//操作数栈的入栈操作
Status PushN(SqStack_opnd* N, SElemType num)
{
	if (N->top - N->base == N->stacksize)//栈满
		return ERROR;
	*N->top++ = num;
	return OK;
}

//运算符栈的出栈操作
Status PopS(SqStack_optr &S, SElemType &ch)
{
	if (S.top == S.base)//栈空
		return ERROR;
	ch = *--S.top;//先减1，再出栈
	return OK;
}

//操作数栈的出栈操作
Status PopN(SqStack_opnd &N, NElemType &num)
{
	if (N.top == N.base )//栈空
		return ERROR;
	num = *--N.top;
	return OK;
}

//运算符栈取栈顶元素
SElemType GetTopS(SqStack_optr& S)
{
	SElemType ch;
	if (S.top == S.base)//栈空
		return ERROR;
	ch = *(S.top - 1);
	return ch;
}

//操作数栈取栈顶元素
NElemType GetTopN(SqStack_opnd& N)
{
	NElemType num;
	if (N.top == N.base)//栈空
		return ERROR;
	num = *(N.top - 1);
	return num;
}

//运算符栈的初始化
void DestroyStackS(SqStack_optr& S)
{
	delete S.base;
}

//运算符栈的初始化
void DestroyStackN(SqStack_opnd& N)
{
	delete N.base;
}

stack_expression.h

#ifndef _STACK_expression_H_
#define _STACK_expression_H_

//1.常量定义
#define OK	        1
#define ERROR       0
#define TRUE	    1
#define FALSE       0
#define MAXSIZE    100

//2.个性化设置
typedef char SElemType;
typedef int  NElemType;
typedef bool Status;

//3.结构体类型定义
typedef struct {
	SElemType* base;
	SElemType* top;
	int stacksize;
}SqStack_optr;//OPTR运算符栈类型

typedef struct {
	NElemType* base;
	NElemType* top;
	int stacksize;
}SqStack_opnd;//OPND运算符栈类型

#endif

stack_expression.cpp

#include 
#include "stack_expression.h"
#include "stack_opr.h"

using namespace std;

Status opr = TRUE;

Status In(SElemType ch)
{
	switch (ch)//判断ch是否为运算符
	{
		case '+':case '-':case '*':case '/':case '(':case ')':case '#':
			return TRUE;
		
		case '0':case '1':case '2':case '3':case '4':
		case '5':case '6':case '7':case '8':case '9':
			return FALSE;

		default:
			opr = FALSE;
			return opr;
	}
}

//判断运算符的优先级：
//若theta1  > theta2,OPND出栈,theta1出栈,完成运算后压栈OPND;
//若theta1  < theta2,theta2入栈,
//若theta1 == theta2,则脱括号
SElemType Precede(SElemType theta1, SElemType theta2)
{
	SElemType f;

	switch (theta2)
	{
		case '+':case '-':
			if (theta1 == '(' || theta1 == '#')
				f = '<';
			else
				f = '>';
			break;
		case '*':case '/':
			if (theta1 == '(' || theta1 == '#' || theta1 == '+' || theta1 == '-')
				f = '<';
			else
				f = '>';
			break;
		case '(':
			if (theta1 == ')')//在表中,如果遇到')'，是打x的，这里直接让他为“=”,因为后续会直接让它出栈
				f = 'x';
			else
				f = '<';
			break;
		case ')':
			if (theta1 == '(')
				f = '=';
			else if (theta1 == '#')
				f = 'x';
			else 
				f = '>';
			break;
		case '#':
			if (theta1 == '(')
				f = 'x';
			else if (theta1 == '#')
				f = '=';
			else
				f = '>';
			break;
		default:
				f = 'x';
			break;
	}
	return f;
}

NElemType Operate(NElemType a, SElemType theta, NElemType b)
{
	NElemType ret ;
	cout << "a=" << a << ";"<<"b=" << b << endl;
	switch (theta)
	{
		case '+':
			ret = a + b;
			break;
		case '-':
			ret = a - b;
			break;
		case '*':
			ret = a * b;
			break;
		case '/':
			ret = a / b;
			break;
		default:
			opr = FALSE;
			return opr;
			break;
	}
	return ret;
}

// 两个栈 -- 两套东西
NElemType evaluateexpression()
{
	SqStack_optr OPTR;
	SqStack_opnd OPND;
	SElemType ch,x,theta;
	NElemType a, b,tmp,t,e,result;
	Status isnum = FALSE;
	//这个很有意思。
	//isnum指的是上一个变量是不是数字

	InitStackS(OPTR);
	PushS(&OPTR,'#');
	InitStackN(OPND); 
	cin >> ch;
	while (ch != '#' || GetTopS(OPTR) != '#')
	{
		if (!In(ch))
		{
			if (!opr)
				break;
			else
			{ 
				if(isnum == TRUE)//上一个字符的状态是数字
				{ 
					PopN(OPND,e);
					t = ch - '0';
					PushN(&OPND, e*10+t);
					isnum = TRUE;//表示当前这个字符的状态是数字
					cin >> ch;
				}
				else
				{
					PushN(&OPND, ch - '0');
					isnum = TRUE;		   //表示当前这个字符的状态是数字
					cin >> ch;
				}
			}
		}
		else
		{	
			isnum = FALSE;
			switch (Precede(GetTopS(OPTR), ch))//比较优先权
			{
				case '<'://当前字符ch压入OPTR栈，读入下一个字符ch
					PushS(&OPTR, ch);
					cin >> ch;
					break;
				case '>'://弹出OPTR栈顶的运算符运算，并将运算结果入栈
					PopS(OPTR, theta);
					PopN(OPND, b);
					PopN(OPND, a);
					tmp = Operate(a, theta, b);
					if (!opr)
						break;
					else
						PushN(&OPND, tmp);
					break;
				case '='://脱括号并接收下一个字符
					PopS(OPTR, x);
					cout << x<> ch;
					break;
				case 'x':
					opr = FALSE;
					return opr;
					break;
				default:
					opr = FALSE;
					return opr;
					break;
			}
		}
	}
	result = GetTopN(OPND);
	DestroyStackN(OPND);
	DestroyStackS(OPTR);

	return result;
}

int main()
{
	cout<<"请输入算数表达式，并以#结束."< 
以下是视频中对部分代码的注释：
 
 
 由于时间的原因，没有用C++重构这个代码。如果要用C++重构该代码，可以看懒猫老师对该部分的讲解。

栈的应用 -- 表达式求值

C/C++/C#相关栏目本月热门文章