基于栈的后缀算术表达式求值实验

发布于：2023-10-25 ⋅ 阅读:(145) ⋅ 点赞:(0)

目录

0 前言

1 实验介绍

2 实验环境

3 实验提示

3.1 栈

3.2 表达式求值相关算法

4 实验代码

4.1 中缀表达式转化为后缀表达式代码

4.2 计算后缀算术表达式代码

4.3 基于栈的后缀算术表达式求值代码

5 实验总结

0 前言

        本次实验是严蔚敏《数据结构》第2版的第三个实验，通过本次实验，读者可以学会将中缀表达式转换为后缀表达式和计算后缀表达式的代码编写。

1 实验介绍

        基于栈的后缀算术表达式求值，是另一种重要的表达式求值算法。与基于栈的中缀算术表达式求值实验的不同在于，本次实验要求读者先将中缀表达式转换为后缀表达式，进而对后缀表达式求值，而不是直接对中缀表达式求值。

2 实验环境

        本次实验的实验环境为Microsoft Visual Studio 2019，读者新建一个实验三的项目后，在生成的解决方案下新建两个项目，分别完成中缀表达式转换为后缀表达式的代码编写和计算后缀表达式的代码编写。然后，在主项目中完成基于栈的后缀算术表达式求值的代码编写。

3 实验提示

        这一节介绍本次实验的相关注意事项，以及代码编写相关提示。

3.1 栈

        本次实验用到了栈，顺序栈及其相关操作的实现与第二次实验的一样，在使用顺序栈完成实验之后，读者可以将代码稍作修改，就可以实现链栈的实验代码。

3.2 表达式求值相关算法

        在第二次实验中的表达式求值算法中调用的3个函数，可以用到本次实验中。在本次实验的三个项目中，均需要用到这些函数中的部分或全部。

4 实验代码

        这一节给出本次实验的代码，在本次实验中，读者需要编写三份代码，分别完成中缀表达式转化为后缀表达式、计算后缀表达式以及将这两部分综合起来的基于栈的后缀算术表达式求值。

4.1 中缀表达式转化为后缀表达式代码

        关于中缀表达式转化为后缀表达式的方法，在数据结构实验指导书中给出了手算的方法和代码编写实现的方法。对于代码的编写，读者可以参考实验指导书中第3章选择题40题的答案解析部分，通过此处的步骤描述，读者可以比较轻松地将其转换为代码。

        这一部分代码，用到了字符栈，没有用到数栈，在代码编写完成之后，读者可以在OJ上提交，代码如下。

#include <iostream>
#include <iomanip>
using namespace std;
//函数结果状态代码
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//------顺序栈的存储结构------
#define MAXSIZE 100  //顺序栈存储空间的初始分配量
typedef char SElemType;
typedef struct
{
	SElemType *base; //栈底指针
	SElemType *top;  //栈顶指针
	int stacksize;   //栈可用的最大容量
}SqStack;
//Status是函数返回值类型，其值是函数结果状态代码
typedef int Status;
Status InitStack(SqStack &S);
Status Push(SqStack &S, SElemType e);
Status Pop(SqStack &S, SElemType &e);
SElemType GetTop(SqStack S);
//表达式求值相关算法
bool In(SElemType ch);
SElemType Precede(SElemType optr, SElemType ch);
//中缀表达式转化为后缀表达式
string ztoh(char ch);
int main() {
	char ch;
	while (true) {
		cin >> ch;
		if ('=' == ch) {
			break;
		}
		string res = ztoh(ch);
		cout << res << endl;
	}
	return 0;
}
string ztoh(char ch)
{
	SqStack OPTR;
	InitStack(OPTR);
	Push(OPTR, '#');
	string Postfix = "";
	//表达式未读完 或 OPTR栈有运算符
	while (ch != '=' || GetTop(OPTR) != '#')
	{
		if (!In(ch)) {
			Postfix.push_back(ch);
			cin >> ch;
		}
		else {
			switch (Precede(GetTop(OPTR), ch))
			{
			case '<':
				Push(OPTR, ch); cin >> ch;
				break;
			case '>':
				char theta;
				Pop(OPTR, theta);
				Postfix.push_back(theta);
				break;
			case '=':
				char x;
				Pop(OPTR, x); cin >> ch;
				break;
			}
		}
	}
	return Postfix;
}
//判定读入的字符ch是否为运算符的函数
bool In(SElemType ch)
{
	if (ch == '+' || ch == '-' || ch == '*' || ch == '/' ||
		ch == '(' || ch == ')' || ch == '=') {
		return true;
	}
	return false;
}
//判定运算符栈的栈顶元素与读入的运算符之间优先关系的函数
SElemType Precede(SElemType optr, SElemType ch)
{
	//规则（1）先乘除，后加减
	if ((optr == '+' || optr == '-') && (ch == '*' || ch == '/')) {
		return '<';
	}
	else if ((optr == '*' || optr == '/') && (ch == '+' || ch == '-')) {
		return '>';
	}
	//规则（2）从左算到右
	if (((optr == '+' || optr == '-') && (ch == '+' || ch == '-')) ||
		((optr == '*' || optr == '/') && (ch == '*' || ch == '/'))) {
		return '>';
	}
	//规则（3）先括号内，后括号外
	//optr不会出现右括号
	if (optr == '+' || optr == '-' || optr == '*' || optr == '/') {
		if (ch == '(') {
			return '<';
		}
		else if (ch == ')' || ch == '=') {
			return '>';
		}
	}
	else if (optr == '(') {
		if (ch == ')') {
			return '=';
		}
		else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(') {
			return '<';
		}
	}
	//optr中只有'#'的情况
	if (optr == '#' &&
		(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(')) {
		//ch肯定不是'='
		return '<';
	}
}
Status InitStack(SqStack &S)
{
	S.base = new SElemType[MAXSIZE];
	if (!S.base) exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}
Status Push(SqStack &S, SElemType e)
{
	if (S.top - S.base == S.stacksize) return ERROR;
	*S.top++ = e;
	return OK;
}
Status Pop(SqStack &S, SElemType &e)
{
	if (S.top == S.base) return ERROR;
	e = *--S.top;
	return OK;
}
SElemType GetTop(SqStack S)
{
	if (S.top != S.base) {
		return *(S.top - 1);
	}
}

4.2 计算后缀算术表达式代码

        对后缀表达式进行计算的具体步骤，在实验指导书中关于此实验的部分已经说明，在完成实验二之后，编写出代码比较容易。

        这一部分的代码，既用到了字符栈，也用到了数栈，在完成代码之后，读者可以在OJ上提交，代码如下。

#include <iostream>
#include <iomanip>
using namespace std;
//函数结果状态代码
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//Status是函数返回值类型，其值是函数结果状态代码
#define MAXSIZE 100  //顺序栈存储空间的初始分配量
typedef int Status;
typedef char SElemType;
typedef struct
{
	SElemType *base; //栈底指针
	SElemType *top;  //栈顶指针
	int stacksize;   //栈可用的最大容量
}SqStack;
Status InitStack(SqStack &S);
Status Push(SqStack &S, SElemType e);
Status Pop(SqStack &S, SElemType &e);
SElemType GetTop(SqStack S);
typedef double SdElemType;
typedef struct
{
	SdElemType *base; //栈底指针
	SdElemType *top;  //栈顶指针
	int stacksize;   //栈可用的最大容量
}SqStackd;
Status InitStackd(SqStackd &S);
Status Pushd(SqStackd &S, SdElemType e);
Status Popd(SqStackd &S, SdElemType &e);
SdElemType GetTopd(SqStackd S);
//表达式求值相关函数
bool In(SElemType ch);
SElemType Precede(SElemType optr, SElemType ch);
SdElemType Operate(SdElemType x, SElemType theta, SdElemType y);
//计算后缀表达式
double calh(SElemType ch);
int main() {
	SElemType ch;
	while (true) {
		cin >> ch;
		if ('=' == ch) {
			break;
		}
		double res = calh(ch);
		//保留小数点后面2位
		cout << fixed << setprecision(2) << res << endl;
	}
	return 0;
}
double calh(SElemType ch)
{
	SqStackd OPND;
	InitStackd(OPND);
	while (ch != '=')
	{
		if (!In(ch)) {
			//读入的数没有多位数、小数
			Pushd(OPND, double(ch) - 48);
		}
		else {
			double x, y;
			Popd(OPND, y);
			Popd(OPND, x);
			Pushd(OPND, Operate(x, ch, y));
		}
		cin >> ch;
	}
	return GetTopd(OPND);
}
//判定读入的字符ch是否为运算符的函数
bool In(SElemType ch)
{
	if (ch == '+' || ch == '-' || ch == '*' || ch == '/' ||
		ch == '(' || ch == ')' || ch == '=') {
		return true;
	}
	return false;
}
//判定运算符栈的栈顶元素与读入的运算符之间优先关系的函数
SElemType Precede(SElemType optr, SElemType ch)
{
	//规则（1）先乘除，后加减
	if ((optr == '+' || optr == '-') && (ch == '*' || ch == '/')) {
		return '<';
	}
	else if ((optr == '*' || optr == '/') && (ch == '+' || ch == '-')) {
		return '>';
	}
	//规则（2）从左算到右
	if (((optr == '+' || optr == '-') && (ch == '+' || ch == '-')) ||
		((optr == '*' || optr == '/') && (ch == '*' || ch == '/'))) {
		return '>';
	}
	//规则（3）先括号内，后括号外
	//optr不会出现右括号
	if (optr == '+' || optr == '-' || optr == '*' || optr == '/') {
		if (ch == '(') {
			return '<';
		}
		else if (ch == ')' || ch == '=') {
			return '>';
		}
	}
	else if (optr == '(') {
		if (ch == ')') {
			return '=';
		}
		else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(') {
			return '<';
		}
	}
	//optr中只有'#'的情况
	if (optr == '#' &&
		(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(')) {
		//ch肯定不是'='
		return '<';
	}
}
//进行二元运算的函数
SdElemType Operate(SdElemType x, SElemType theta, SdElemType y)
{
	double z;
	switch (theta)
	{
	case '+':
		z = x + y;
		break;
	case '-':
		z = x - y;
		break;
	case '*':
		z = x * y;
		break;
	case '/':
		z = x / y;
		break;
	default:
		z = 0;
	}
	return z;
}
Status InitStack(SqStack &S)
{
	S.base = new SElemType[MAXSIZE];
	if (!S.base) exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}
Status Push(SqStack &S, SElemType e)
{
	if (S.top - S.base == S.stacksize) return ERROR;
	*S.top++ = e;
	return OK;
}
Status Pop(SqStack &S, SElemType &e)
{
	if (S.top == S.base) return ERROR;
	e = *--S.top;
	return OK;
}
SElemType GetTop(SqStack S)
{
	if (S.top != S.base) {
		return *(S.top - 1);
	}
}
Status InitStackd(SqStackd &S)
{
	S.base = new SdElemType[MAXSIZE];
	if (!S.base) exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}
Status Pushd(SqStackd &S, SdElemType e)
{
	if (S.top - S.base == S.stacksize) return ERROR;
	*S.top++ = e;
	return OK;
}
Status Popd(SqStackd &S, SdElemType &e)
{
	if (S.top == S.base) return ERROR;
	e = *--S.top;
	return OK;
}
SdElemType GetTopd(SqStackd S)
{
	if (S.top != S.base) {
		return *(S.top - 1);
	}
}

4.3 基于栈的后缀算术表达式求值代码

        这一小节完成实验指导书中关于输入输出的实现，即前面两个小节的综合，代码如下。

#include <iostream>
#include <iomanip>
using namespace std;
//函数结果状态代码
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//Status是函数返回值类型，其值是函数结果状态代码
#define MAXSIZE 100  //顺序栈存储空间的初始分配量
typedef int Status;
typedef char SElemType;
typedef struct
{
	SElemType *base; //栈底指针
	SElemType *top;  //栈顶指针
	int stacksize;   //栈可用的最大容量
}SqStack;
Status InitStack(SqStack &S);
Status Push(SqStack &S, SElemType e);
Status Pop(SqStack &S, SElemType &e);
SElemType GetTop(SqStack S);
typedef double SdElemType;
typedef struct
{
	SdElemType *base; //栈底指针
	SdElemType *top;  //栈顶指针
	int stacksize;   //栈可用的最大容量
}SqStackd;
Status InitStackd(SqStackd &S);
Status Pushd(SqStackd &S, SdElemType e);
Status Popd(SqStackd &S, SdElemType &e);
SdElemType GetTopd(SqStackd S);
//表达式求值相关函数
bool In(SElemType ch);
SElemType Precede(SElemType optr, SElemType ch);
SdElemType Operate(SdElemType x, SElemType theta, SdElemType y);
//中缀表达式 转 后缀表达式
string ztoh(SElemType ch);
//计算后缀表达式
int calh(string res);
int main() {
	char ch;
	while (true) {
		cin >> ch;
		if ('=' == ch) {
			break;
		}
		string res = ztoh(ch);
		cout << res << endl;
		int r = calh(res);
		cout << r << endl;
	}
	return 0;
}
string ztoh(SElemType ch)
{
	SqStack OPTR;
	InitStack(OPTR);
	Push(OPTR, '#');
	string Postfix = "";
	while (ch != '=' || GetTop(OPTR) != '#')
	{
		if (!In(ch)) {
			Postfix.push_back(ch);
			cin >> ch;
		}
		else {
			switch (Precede(GetTop(OPTR), ch))
			{
			case '<':
				Push(OPTR, ch); cin >> ch;
				break;
			case '>':
				char theta;
				Pop(OPTR, theta);
				Postfix.push_back(theta);
				break;
			case '=':
				char x;
				Pop(OPTR, x); cin >> ch;
				break;
			}
		}
	}
	return Postfix;
}
int calh(string res)
{
	SqStackd OPND;
	InitStackd(OPND);
	int i = 0;
	char ch = res[i++];
	while (ch != '\0')
	{
		if (!In(ch)) {
			Pushd(OPND, double(ch) - 48);
		}
		else {
			double x, y;
			Popd(OPND, y);
			Popd(OPND, x);
			Pushd(OPND, Operate(x, ch, y));
		}
		ch = res[i++];
		//cin >> ch;
	}
	return GetTopd(OPND);
}
//判定读入的字符ch是否为运算符的函数
bool In(SElemType ch)
{
	if (ch == '+' || ch == '-' || ch == '*' || ch == '/' ||
		ch == '(' || ch == ')' || ch == '=') {
		return true;
	}
	return false;
}
//判定运算符栈的栈顶元素与读入的运算符之间优先关系的函数
SElemType Precede(SElemType optr, SElemType ch)
{
	//规则（1）先乘除，后加减
	if ((optr == '+' || optr == '-') && (ch == '*' || ch == '/')) {
		return '<';
	}
	else if ((optr == '*' || optr == '/') && (ch == '+' || ch == '-')) {
		return '>';
	}
	//规则（2）从左算到右
	if (((optr == '+' || optr == '-') && (ch == '+' || ch == '-')) ||
		((optr == '*' || optr == '/') && (ch == '*' || ch == '/'))) {
		return '>';
	}
	//规则（3）先括号内，后括号外
	//optr不会出现右括号
	if (optr == '+' || optr == '-' || optr == '*' || optr == '/') {
		if (ch == '(') {
			return '<';
		}
		else if (ch == ')' || ch == '=') {
			return '>';
		}
	}
	else if (optr == '(') {
		if (ch == ')') {
			return '=';
		}
		else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(') {
			return '<';
		}
	}
	//optr中只有'#'的情况
	if (optr == '#' &&
		(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(')) {
		//ch肯定不是'='
		return '<';
	}
}
//进行二元运算的函数
SdElemType Operate(SdElemType x, SElemType theta, SdElemType y)
{
	double z;
	switch (theta)
	{
	case '+':
		z = x + y;
		break;
	case '-':
		z = x - y;
		break;
	case '*':
		z = x * y;
		break;
	case '/':
		z = x / y;
		break;
	default:
		z = 0;
	}
	return z;
}
Status InitStack(SqStack &S)
{
	S.base = new SElemType[MAXSIZE];
	if (!S.base) exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}
Status Push(SqStack &S, SElemType e)
{
	if (S.top - S.base == S.stacksize) return ERROR;
	*S.top++ = e;
	return OK;
}
Status Pop(SqStack &S, SElemType &e)
{
	if (S.top == S.base) return ERROR;
	e = *--S.top;
	return OK;
}
SElemType GetTop(SqStack S)
{
	if (S.top != S.base) {
		return *(S.top - 1);
	}
}
Status InitStackd(SqStackd &S)
{
	S.base = new SdElemType[MAXSIZE];
	if (!S.base) exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}
Status Pushd(SqStackd &S, SdElemType e)
{
	if (S.top - S.base == S.stacksize) return ERROR;
	*S.top++ = e;
	return OK;
}
Status Popd(SqStackd &S, SdElemType &e)
{
	if (S.top == S.base) return ERROR;
	e = *--S.top;
	return OK;
}
SdElemType GetTopd(SqStackd S)
{
	if (S.top != S.base) {
		return *(S.top - 1);
	}
}

5 实验总结

        本次实验完成了三个代码文件，通过本次实验，我进一步明确了表达式求值相关算法的使用，提高了自己的代码编写能力。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布